擬凸多目標規(guī)劃問題解的最優(yōu)性條件

陳榮波，高 英，李美術(shù)

(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,重慶 401331)

?

擬凸多目標規(guī)劃問題解的最優(yōu)性條件

陳榮波，高 英*，李美術(shù)

(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,重慶 401331)

考慮約束集為凸集,目標函數(shù)為擬凸函數(shù)的多目標規(guī)劃問題,利用次微分為工具研究擬凸多目標規(guī)劃問題的最優(yōu)性條件.在擬凸單目標規(guī)劃問題最優(yōu)性條件的基礎(chǔ)上,在一定約束條件下,利用標量化方法得到擬凸多目標規(guī)劃問題的最優(yōu)性條件.

多目標規(guī)劃;擬凸函數(shù);次微分;最優(yōu)性條件

在擬凸規(guī)劃問題中,最優(yōu)性條件是一個被廣泛應(yīng)用的概念,最優(yōu)性條件對于研究向量優(yōu)化問題的解有著重要理論指導(dǎo)意義.擬凸規(guī)劃是現(xiàn)代數(shù)學(xué)規(guī)劃中的一個重要研究領(lǐng)域.在工程技術(shù)、環(huán)境污染以及機器人運行軌道設(shè)計等工業(yè)問題中都有著廣泛應(yīng)用.文獻[1]首次提出關(guān)于一類凸極值規(guī)劃問題的解集特征和最優(yōu)性條件的概念,隨后一些學(xué)者將凸規(guī)劃問題中的結(jié)論推廣到一些其它類型的規(guī)劃問題.如文獻[2-3]研究了無限維凸規(guī)劃問題的最優(yōu)性條件,文獻[4-6]研究了廣義凸規(guī)劃問題的最優(yōu)性條件,文獻[7]研究了凸向量規(guī)劃問題的最優(yōu)性條件,文獻[1,8]研究了擬凸單目標規(guī)劃問題的最優(yōu)性條件.文獻[9]利用SlaterCQ研究了擬凸半無限規(guī)劃問題的最優(yōu)性條件.近年來,國內(nèi)外越來越多的學(xué)者開始致力于擬凸規(guī)劃問題的理論研究,但是關(guān)于擬凸多目標規(guī)劃問題最優(yōu)性條件的研究并不多.

本文研究了如下形式的擬凸多目標規(guī)劃問題：

這里fi是Rn上的擬凸函數(shù),i∈I={1,2,…,p},擬凸函數(shù)是指?x1,x2∈S,λ∈(0,1)總有f[λx1+(1-λ)x2]≤max{f(x1),f(x2)}成立.可行集S是Rn的凸子集.

本文在文獻[4,10]的基礎(chǔ)上,在一定約束品性下研究了一類擬凸多目標規(guī)劃問題的最優(yōu)性條件和解集特征.具體結(jié)構(gòu)如下:在第2節(jié),給出了一些基本概念和結(jié)論,并介紹了幾種次微分.在第3節(jié),利用文獻[4]和文獻[10]在一定約束條件下,利用標量化的思想給出了擬凸多目標規(guī)劃問題的有效解、弱有效解、真有效解和最優(yōu)性條件.

1 預(yù)備知識

設(shè)x=(x1,x2,…,xn)T,y=(y1,y2,…,yn)T∈Rn,定義向量x,y的序關(guān)系:

xy?

定義1[10]點z∈S稱作問題(MOP)的弱有效解當且僅當找不到x∈S使得:

fi(x)

定義2[10]點z∈S稱作問題(MOP)的有效解當且僅當找不到x∈S使得:

fi(x)≤fi(z),?i∈I,

fs(x)

定義3[4]g:Rn→R∪{±},假設(shè)g在x0∈S處是有限的.g在x0處水平集和嚴格水平集的定義如下：

[g≤g(x0)]={x∈X:g(x)≤g(x0)},[g

定義4[11]經(jīng)典Greenberg-Pierskalla次微分定義如下:

定義6[12]凸集C?Rn在x0處的法錐定義如下:

很顯然,

?g(x0)=N([g

當g在[g

且x0是g的最優(yōu)解當且僅當0∈?*g(x0)或?*g(x0)=Rn或?g(x0)=Rn.

另外一類在廣義凸性理論下閉的且完全不同的經(jīng)典次微分形式如下.

定義7[13]Gutierrez次微分定義如下:

定義8[14]Plastria下次微分定義如下:

x0是g的最優(yōu)解當且僅當0∈?≤g(x0),0∈?

顯然,有:

?≤g(x0)??

文獻[4]針對(MOP)問題中p=1時的情況,利用Greenberg-Pierskalla次微分給出擬凸單目標規(guī)劃問題的最優(yōu)性充分條件.

引理1[4]設(shè)存在x0∈S都有?*f1(x0)∩(-N(S,x0))≠?,則x0是f1在S上的最優(yōu)解.

文獻[10]中研究了一類帶有線性不等式約束的非光滑向量偽凸多目標規(guī)劃問題(NMOP).

其中aj∈Rn,bj∈R.且fi:K→R,i∈I={1,2,…,p}是開凸集K上的局部Lipschitz偽凸線性函數(shù).

引理3[12]設(shè)S是Rn上非空開凸集,f:S→R在S上可微的偽凸函數(shù),則f也是嚴格擬凸和擬凸函數(shù).

2 最優(yōu)性必要條件

在擬凸單目標規(guī)劃問題的最優(yōu)性條件的基礎(chǔ)上,將結(jié)論推廣到擬凸多目標規(guī)劃問題的最優(yōu)性充分條件.

定理1對于(MOP)問題,若存在x0∈S,使得:

(1)

則x0是f在S上的弱有效解，其中λi≥0,且至少有一個λi>0,i∈I.

證明反證.假設(shè)x0不是(MOP)的弱有效解,則存在x∈S使得:f(x)

即〈y0,x-x0〉<0,又由于y0∈-N(S,x0),則?x∈S，有〈y0,x-x0〉≥0,矛盾.從而f(x0)為原問題的弱有效解.

定理2對于(MOP)問題,若存在x0∈S,使得:

(2)

則x0是f在S上的有效解，其中λi≥0,i∈I且至少存在一個i∈Ix0?I,使λi>0,Ix0={i|fi(x)

〈y0,x-x0〉<0,

又:

y0∈-N(S,x0).

這表明?x∈S:

〈-y0,x-x0〉≤0.

矛盾,故x0是f在S上的有效解.

定理3對于(MOP)問題,若存在x0∈S使得:

(3)

則x0是f在S上的真有效解,其中λi>0,i∈I.

證明由引理2和引理3顯然成立.

推論1假設(shè)存在x0∈S使得f在[f

?f(x0)∩(-N(S,x0))≠{0}.

(4)

證明在假設(shè)條件下,由?f(x0)=?*f(x0)∪{0},則式(4)能推出式(2).

推論2假設(shè)f在[f

(5)

則x0是f在S上的有效解.

證明在可微條件下,f的次梯度和梯度向量是等價的,由定理1可知:

則上式成立.

下面舉例說明在上面兩個推論的證明中上半連續(xù)這個條件是非常關(guān)鍵的.

圖1 f2的函數(shù)圖像Fig.1 Function plot for f2

例1令X=R2,S=R-×R,f=(f1,f2),其中f1(r,s)=r,

但是x0不是f在S上的有效解.

一些限制條件的提出是為了滿足式(1)必要性的成立,注意到即使在凸性條件下,為了得到必要性條件也必須要滿足一些限制條件.下面給出了證明.

定理4設(shè)x0是(MOP)問題的有效解,但是x0不是f在X的局部有效解,則:

證明集合G=[f

〈y0,w-x0〉≥r≥〈y0,u-x0〉,?w∈F,?u∈G.

取w=x0,得到r≤0,有:

y0∈?fi(x0),

存在λi>0,i∈I使得:

當G是開集時,有:

y0∈?*fi(x0),

存在λi>0,i∈I使得:

假設(shè)x0不是f在X上的局部有效解,存在任意靠近x0的點u∈G使得r=0,即:

-y0∈N(F,x0).

下面的例子為了說明x0不是局部有效解這個條件不可省略.

例2設(shè)f=(f1,f2):R→R定義如下,其中f1(x)=x,

令S=[0,1],對于x0=0,它不是f的局部有效解.

?*f1(x0)=?*f2(x0)=(0,+),-N(S,x0)=R+,

然而對于x0=1,?*f1(x0)=?*f2(x0)=(0,+),-N(S,x0)=R+,對任意λi>0都不會成立.但x0=1是f的局部有效解.

推論3設(shè)f是擬凸函數(shù),S是X的凸子集,x0∈S不是f在X的局部有效解.假設(shè)f在[f≤f(x0)]上每一點都是上半連續(xù),則x0是f在S上的有效解當且僅當:

其中λi>0,i∈I.

證明由?fi(x0)∩(-N(S,x0))≠?,i=1,2,…,p,

推論4設(shè)f在X上是連續(xù)擬凸函數(shù),X上的局部有效解就是全局有效解,令inff(S)>inff(X).假設(shè)f在[f≤inff(S)]上是Lipschitzian,則下面的結(jié)論在x0∈S上是等價:

i)x0是f在S上的有效解;

ii)?≤f(x0)∩(-N(S,x0))≠?;

iii)?

證明證明方法同推論3一樣.

[1] MANGASARIAN O L.A simple characterization of solution sets of convex programs[J].OperationsResearch Letters,1988,7(1):21-26.

[2] JEYAKUMAR V,WOLKOWICZ H.Generalizations of Slater′s constraint qualification for infinite convexprograms[J].Mathematical Programming,1992,57(1/2/3):85-101.

[3] JEYAKUMAR V.Infinite-dimensional convex programming with applications to constrained approximation[J].Journal of Optimization Theory & Applications,1992,75(3):569-586.

[4] PENOT J P.Characterization of Solution Sets of QuasiconvexPrograms[J].Journal of OptimizationTheory & Applications,2003,117(3):627-636.

[5] JEYAKUMAR V,YANG X Q.Convex composite multi-objective nonsmoothprogramming[J].MathematicalProgramming,1993,59(1/3):325-343.

[6] JEYAKUMAR V,LEE G,DINH N.Lagrange Multiplier Conditions Characterizing the Optimal SolutionSets of Cone-Constrained Convex Programs[J].Journal of Optimization Theory & Applications,2004,123(1):83-103.

[7] JEYAKUMAR V,LEE G M,DINH N.Characterizations of solution sets of convex vector minimizationproblems[J].European Journal of Operational Research,2006,174(3):1380-1395.

[8] QUYENT.Optimality conditions in quaiconvex vector optimization[J].Southeast-Asian J,2014,3(1):24-32.

[9] KANZI N,SOLEIMANI-DAMANEH M.SLATER CQ.Optimality and duality for quasiconvex semi-infiniteoptimization problems[J].Journal of Mathematical Analysis & Applications,2016,434(1):638-651.

[10] MISHRA S,UPADHYAY B,AN L.Lagrange Multiplier Characterizations of Solution Sets of ConstrainedNonsmoothPseudolinear Optimization Problems[J].Journal of Optimization Theory & Applications,2014,160(3):763-777.

[11] PENOT J P.Are Generalized Derivatives Sseful for Generalized Convex Functions?[M].Springer US:Generalizedconvexity,generalized monotonicity:recent results,1998:3-59.

[12] CLARK F H.Optimization and NonsmoothAnalysis[M].New York:Wiley-Interscience,1983.

[13] GUTIERREZ J M.Infragradientes y direcciones de decrecimiento[J].Revista de la Real Academia de Ciencias Exactas Fisicas y Naturales,Madrid,1984,78(4):523-532.

[14] PLASTRIA F.Lower subdifferentiable functions and their minimization by cutting planes[J].Journalof Optimization Theory and Applications,1985,46(1):37-53.

責任編輯：高 山

Optimality Conditions in Quasiconvex Multiobjective Programs

CHEN Rongbo，GAO Ying*，LI Meishu

(College of Mathematics Science，Chongqing Normal University，Chongqing 401331，China)

In this paper,we consider a quasiconvex multiobjective programming problem where the objective is quasiconvex and constraint set is convex.By using subdifferential as a tool.we study the optimality conditions in quasiconvex multiobjective programming. Based on the optimality conditions in quasiconvex multiobjective programming problem and under certain constraint conditions,optimality conditions of quasiconvex multiobjective programming problem are derived.

Multiobjective programming;Quasiconvex function;subdifferentials;optimality conditions

2016-10-21.

重慶市教委科學(xué)技術(shù)研究項目(KJ1500309，KJ1400519)；重慶市基礎(chǔ)與前沿研究計劃項目(cstc2015jcyjA00005).

陳榮波(1992- ),男,碩士生,主要從事多目標規(guī)劃的研究；*

高英(1982- ),女(蒙古族),博士,副教授,主要從事最優(yōu)化理論與方法的研究.

1008-8423(2016)04-0386-05

10.13501/j.cnki.42-1569/n.2016.12.006

O221.6

A