一類非光滑多目標(biāo)規(guī)劃問題的最優(yōu)性條件

周軒偉

（浙江樹人大學(xué)基礎(chǔ)部，浙江杭州310015）

?

一類非光滑多目標(biāo)規(guī)劃問題的最優(yōu)性條件

周軒偉

（浙江樹人大學(xué)基礎(chǔ)部，浙江杭州310015）

研究了一類非光滑多目標(biāo)規(guī)劃問題.這類多目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)為錐凸函數(shù)與可微函數(shù)之和，其約束條件是Euclidean空間中的錐約束.在滿足廣義Abadie約束規(guī)格下，利用廣義Farkas引理和多目標(biāo)函數(shù)標(biāo)量化，給出了這一類多目標(biāo)規(guī)劃問題的錐弱有效解最優(yōu)性必要條件.

非光滑多目標(biāo)規(guī)劃；廣義Abadie約束規(guī)格；廣義Farkas引理；最優(yōu)性必要條件

O221.6

§1　引　言

考慮下列的非光滑多目標(biāo)規(guī)劃問題：

（MPP）其中f =（f1，···，fp）: Rn→Rp，g =（g1，···，gm）: Rn→Rm. f和g是Rn上的可微多目標(biāo)函數(shù)，?=（?1，···，?p）: Rn→Rp是Rn上有限值K-凸函數(shù)；K，K1分別是Rp，Rm中的尖閉凸錐且intK /=?，intK1/=?，C是Rn中的凸子集.

對問題（MPP），當(dāng)?i（x）= s（x|Di）（i = 1，···，p），其中s（x|Di）是Rn中的緊子集Di（i = 1，···，p）的支撐函數(shù)，C是Rn的開子集時，文［1-2］給出了問題（MPP）的最優(yōu)性條件和對偶定理. 當(dāng)?i（x）=（xTBx）1/2，其中B是n×n對稱半正定矩陣，f是Rn上的可微函數(shù)，C = Rn，p = 1時，文［3］首先提出了問題（MPP），并在滿足一種較復(fù)雜的約束規(guī)格條件下，得到了該問題的最優(yōu)性必要條件.然后，文［4］證明了Slater約束規(guī)格蘊含前文中的約束規(guī)格.后來，文［5］將文［3］的問題推廣到分式規(guī)劃.文［6-7］再將該問題推廣到極小極大分式規(guī)劃.在文［3］的約束規(guī)格下，文［6-7］給出了相應(yīng)的最優(yōu)性必要條件.在這些必要條件的基礎(chǔ)上，上述論文也討論了最優(yōu)性充分條件或Wolfe型對偶.在問題（MPP）中，當(dāng)K = Rp+，K = Rm+和C = Rn時，文［8］在問題（MPP）滿足Kuhn-Tucker約束規(guī)格或Arrow-Hurwicz-Uzawa約束規(guī)格（［9］）時，得到了弱有效解的Kuhn-Tucker型必要條件.當(dāng)C?Rn為一般凸集，p = 1時，文［10］引進了廣義的Kuhn-Tucker約束規(guī)格和廣義的Arrow-Hurwicz-Uzawa約束規(guī)格，得到了最優(yōu)解的Kuhn-Tucker型必要條件.當(dāng)C?Rn為一般凸集，p＞1時，文［11］在文［10］的約束規(guī)格下，得到了Pareto弱有效解的Kuhn-Tucker型必要條件.

本文研究了非光滑多目標(biāo)規(guī)劃問題（MPP）.其目標(biāo)函數(shù)為錐凸函數(shù)與可微函數(shù)之和，約束條件是錐約束.在滿足廣義Abadie約束規(guī)格下，利用廣義Farkas引理和多目標(biāo)函數(shù)標(biāo)量化，給出了這一類多目標(biāo)規(guī)劃問題的錐弱有效解最優(yōu)性必要條件.本文將文［10］和［11］的結(jié)果從Pareto弱有效解推廣到錐弱有效解，并且將有限個不等式約束推廣到錐約束.由于錐約束相當(dāng)于無限個不等式約束，因此本文的結(jié)果是文［10］和［11］的結(jié)果在多目標(biāo)規(guī)劃中的本質(zhì)推廣.本文中的定理3.1和定理3.2是文［11］中定理3.1和定理3.2的推廣.

§2　預(yù)備知識

給出本文涉及的基本概念，定義和引理.

定義2.1設(shè)S是Rn中的非空子集，點x0∈clS.設(shè)點列｛xk｝?S，xk→x0（k→+∞），正數(shù)

數(shù)列｛tk｝，tk→+∞（k→+∞）.若極限d =）存在，則稱d是點x0處關(guān)于S的切向量.集合T（S，x0）=稱為是S在x0處的切錐.

定義2.2設(shè)K?Rn.若

設(shè)C是Rn的子集，affC表示C的仿射包，riC表示C的相對內(nèi)部，

其中U是Rn中的單位球.

定義2.3設(shè)X =｛x∈Rn|g（x）∈-K1｝，g在x?∈X∩C滿足廣義Abadie約束條件，若

其中

定義2.4設(shè)K?Rn是具有非空內(nèi)部的尖凸錐，x0∈Rn.若x?D，使得

則稱x0為多目標(biāo)規(guī)劃（MPP）的K-弱有效解，其中D =｛x∈C|g（x）∈-K1｝.

定義2.5設(shè)K?Rn是具有非空內(nèi)部的閉凸錐，若?x1，x2∈Rn，以及λ∈［0，1］均有

則稱f（x）為K-凸函數(shù).

其中domh =｛x|h（x）＜+∞｝.集合

引理2.1［3］設(shè)C是Rn的凸子集，假若riC /=?，（affC）（riC）/=?，則對于任意的x?∈

（clC）（riC），有

§3　主要結(jié)論

在滿足廣義Abadie約束條件下，給出多目標(biāo)規(guī)劃問題（MPP）的錐弱有效解最優(yōu)性必要條件. 記

引理3.1若x?是（MPP）的K-弱有效解，g在x?處滿足廣義Abadie約束條件，?是Rn上有限值K-凸函數(shù)，并且對任意的x，y∈Rn有‖?（x）-?（y）‖≤L‖x - y‖（L＞0）.如果Z（x?）∩riC /=?，則廣義不等式組

在riC內(nèi)無解.

證假設(shè)存在ˉx∈riC滿足（1），則ˉx∈Z（x?）即ˉx∈Z（x?）∩riC.因為g在x?處滿足廣義Abadie約束條件，由其定義有

所以存在xk?X∩（affC）和｛tk｝?R+，tk→+∞（k→+∞）使得

下面分兩種情況證明:存在k1，當(dāng)k≥k1時，xk∈riC.

當(dāng)x?∈riC時.由ri（riC）= riC，aff（riC）= affC，知

所以存在ˉε＞0使得（x?+ˉεU）∩（affC）?riC.因為xk→x?，于是知存在k1，當(dāng)k≥k1時有xk∈x?+ˉεU，從而xk∈riC.

當(dāng)x?∈C iC?clC iC時，假設(shè)結(jié)論不成立，即不存在k1，當(dāng)k≥k1時，xk∈riC，則存在序列｛ki｝，ki→+∞（i→+∞）使得xki∈affC iC，則由（2）式，有tki（xki-x?）→ˉx - x?（i→+∞），從而ˉx - x?∈T（（affC）（riC），x?）.由引理2.1，對于x?∈clC iC有

又因為ˉx - x?∈T（（affC）（riC），x?），所以ˉx - x?/∈（riC -｛x?｝），即ˉx /∈riC，矛盾.所以由上述證明可知，存在k1，當(dāng)k≥k1時，xk∈riC.

由于ˉx滿足（1）式，可知ˉx /= x?.由（2）式知，存在k2使得k≥k2，tk≥1.

由于?（x）是Rn上的K-凸函數(shù)，所以?u∈［0，1］有

從而有

因為tk≥1（k≥k2）有有

因為對任意的x，y∈Rn有

所以

又由

得

由上式和（3）式知，當(dāng)k≥k2時有

又ˉx滿足廣義不等式組（1）有▽f（x?）T（ˉx - x?）+?（ˉx）-?（x?）∈-intK.于是存在k3使得當(dāng)k≥k3時，有

由（4）式，（5）式得

因為εk→0（k→+∞），故存在k4，當(dāng)k≥k4時有，

取ˉk = max｛k1，k2，k3，k4｝，則當(dāng)k≥ˉk時，有

即

因為xk∈X∩C（k≥ˉk），所以（6）式與x?是（MMP）的K-弱有效解矛盾，從而廣義不等式組（1）在riC內(nèi)無解.

引理3.2設(shè)D?Rn為凸集，K?Rp為凸錐，且intK /=?，f（x）∈Rp為K-凸函數(shù).若廣義不等式組

無解，則存在λ∈K?｛0｝，使得?x∈D，有

先證明Y為凸集.設(shè)

則存在x1∈D，x2∈D，有

由于K為凸集，故intK為凸集，因此

現(xiàn)在

因為f（x）為K-凸函數(shù)，以及intK為凸錐，故

由μ1+ f（x1）∈-intK，μ2+ f（x2）∈-intK，不妨設(shè)α＞0，1 -α＞0，故

從而有

因此

由于D為凸集，故

因此

故Y為凸集.

下面用凸集分離定理證明本引理的結(jié)論.因為

無解，故0 /∈Y .因為Y為凸集，由凸集分離定理，存在λ∈Rp｛0｝，使得?μ∈Y，有

證記

由于?ˉμ∈-intK，?α＞0和?x∈D有

故

因此，?α＞0有

即?α＞0有

因此必有

即

故

在（7）式中令α→0，得知?x∈D，有

引理3.3（廣義Farkas引理）設(shè)C是Rn的凸子集，F(xiàn) : C→R是在C上的凸函數(shù).同時假設(shè)

分別為給定的向量和標(biāo)量.設(shè)A =（a1，···，ap），b =（b1，···，bp）T，K?Rp為閉凸錐，

若S∩riC /=?以及∪λ∈K?epi（λTG）?是Rp×R中的閉集，其中

并且F（x）≥0，?x∈S∩C.則存在μ∈K?，使得

證考慮Rn×R的凸子集A1和A2，定義如下：

利用假設(shè)條件?x∈S∩C都有F（x）≥0，可知A1和A2不相交，而A1是凸集且ri（A1）/=?，A2是一個閉凸集.因此，根據(jù)文［12］的命題3.5.1，存在向量（ξ，β）∈｛Rn×R｝｛0｝，使得

根據(jù)A1的定義，可知β≥0，否則（8）式的右邊就可以減少到負(fù)無窮.現(xiàn)在證明β＞0.采用反證法，假設(shè)β= 0.令ˉx∈S∩riC，令ˉw滿足（ˉx，ˉw）∈A1，由（8）可得

從而線性函數(shù)ξTy在A1上的最小值可以在點（ˉx，ˉw）取得，且由于ˉx∈riC，故點（ˉx，ˉw）是A1的一個相對內(nèi)點.因此，根據(jù)文［13］的命題B.19（a），ξTy在A1上是常數(shù)，但這與（9）式矛盾，這一矛盾是由β= 0的假設(shè)引起的.因此，必有β＞0，且通過將（ξ，β）歸一化，可以假設(shè)β= 1 .

利用S的定義及（8）式，得到

由于S非空，上式左邊的線性規(guī)劃問題具有有限的最優(yōu)值，故該問題具有最優(yōu)解x?.

即

由上式可得

因此，

因為λ∈K?，Ax?- b∈-K，所以

結(jié)合（11）式和（12）式，得到

由（11）式和（13）式得

這就證明了所需要的結(jié)論.

定理3.1若x?是（MPP）的K-弱有效解，g在x?處滿足廣義Abadie約束條件，?是Rn上有限值K-凸函數(shù)，并且對任意的如果中的閉集，其中，那么存在λ∈使得

證由引理3.1，知

在riC內(nèi)無解.顯然Z（x?）∩riC是非空凸集，由引理3.2，知存在λ∈K?｛0｝，使得

在riC內(nèi)無解.由引理3.3，知存在μ∈K?1，使得

因為riC /=?且C為凸集，所以

在（17）式中，令x = x?，則有μTg（x?）≥0.又因為

從而有

所以，μTg（x?）= 0，于是（16）式成立，代入（17）式，有

即

從而（15）成立.定理得證.

考慮下列的問題：

（MPP1）

其中

f和g是Rn上上的可微多目標(biāo)函數(shù)，?（x）=（?1，···，?p）: Rn→Rp是Rn上有限值K-凸函數(shù)，h =（h1，···，hr）: Rn→Rr是Rn上有限值K2-凸函數(shù)；K，K1，K2分別是Rp，Rm，Rr的尖閉凸錐且intK /=?，intK1/=?，intK2/=?.

定理3.2若x?是（MPP1）的K-弱有效解，g在x?處滿足廣義Abadie約束條件，?是Rn上有限值K-凸函數(shù)，h是Rn上有限值K2-凸函數(shù)，并且對任意的x，y∈Rn有

如果Z（x?）∩｛x∈Rn|h（x）∈-intK2｝/=?，∪λ∈K?epi（λTˉG）?是Rp×R中的閉集，其中

證設(shè)

由條件

知｛x∈Rn|h（x）∈-intK2｝/=?.又有K2是Rp的尖閉凸錐且intK2/=?，容易證明

中的閉集”，是廣義Farkas引理成立的正則性條件，有時稱為“閉錐條件”，該條件在文［14-19］均有詳細(xì)討論.在無限維空間中，該條件為“是弱*閉的”.特別地，在有限維空間中，當(dāng)ˉG是Rn→ Rp的線性映射顯然是閉集.因此，在有限個不等式約束條件中，“閉錐條件”自然成立.

注3.2在定理3.1中用到的條件“Z（x?）∩riC /=?”，即不等式

在riC中有解.因為C是凸集，所以riC /=?.例如:設(shè)

則

顯然Z（x?）∩riC = C /=?.文［10］和文［11］都用到了條件“Z（x?）∩riC /=?”，文［13］在第507-510頁上詳細(xì)討論該條件的必要性.

［1］Yang Xinmin，Yang Xiaoqi，Teo K L. Higher-order generalized convexity and duality in nondifferentiable multiobjective mathematical programming［J］. J Math Anal Appl，2004，297: 48-55.

［2］Bae D B，Kim D S. Optimality and duality theorems in nonsmooth multiobjective optimization［J］. Fixed Point Theory and Appl，2011，2011: 42.

［3］Mond B. A class of nondifferentiable mathematical programming problems［J］. J Math Anal Appl，1974，46: 169-174.

［4］Mond B，Schechter M A. On a constraint qualification in a nonlinear programming problems［J］. New Res Logic Quart，1976，23: 611-613.

［5］Aggarwal S A，Saxena P C. A class of fractional functional programming problems［J］. New Zealand Oper Res，1979，7: 79-90.

［6］Singh C. Optimality conditions for fractional minimax programming［J］. J Math Anal Appl，1984，100: 409-415.

［7］Lai Hangchin，Liu Jianchuan，Tanaka K. Necessary and sufficient conditions for minimax fractional programming［J］. J Math Anal Appl，1999，230: 311-328.

［8］Luo Hezhi，Wu Huixian. K-T necessary conditions for a class of nonsmooth multiobjective programming［J］. OR Transactions，2003，7: 62-68.

［9］Mangsarian O L. Nonlinear Programming［M］. New York: McGraw-Hill Book Company，1969.

［10］Xu Zengkun. Constraint qualifications in a class of nondifferentiable mathematical programming problems［J］. J Math Anal Appl，2005，302: 282-290.

［11］Wu Huixian and Luo Hezhi. Necessary optimality conditions for a class of nonsmooth vector optimization problems［J］. Acta Math Appl Sinica（English Series），2009，25（1）: 87-94.

［12］Bertsekas D P，Nedi′c A，Ozdaglar A E. Convex Analysis and Optimization［M］. Belmont，MA：Athena Scientific，2003.

［13］Bertsekas D P. Nonlinear Programming，2nd Ed.［M］. Belmont，MA：Athena Scientific，2004.

［14］Jeyakumar V，Lee G M. Complete characterizations of stable Farkas'lemma and coneconvex programming duality［J］. Math Prog，Ser A，2008，114: 335-347.

［15］Bot R I，Wanka G. An alternative formulation for a new closed cone constraint qualification［J］. Nonlinear Anal Theory Methods Appl，2006，64（6）: 1367-1381.

［16］Dinh N，Jeyakumar V，Lee G M. Sequential Lagrangian conditions for convex programs with applications to semidefinite programming［J］. J Optim Theory Appl，2005，125: 85-112.

［17］Gwinner J. Results of Farkas type［J］. Numer Funct Anal Optim，1987，9: 471-520.

［18］Jeyakumar V，Lee G M，Dinh N. Characterization of solution sets of convex vector minimization problems［J］. Eur J Oper Res，2006，174: 1380-1395.

［19］Gwinner J，Pomerol J C. On weak* closedness，coerciveness，and inf-sup theorems［J］. Arch Math，1989，52: 159-167.

MR Subject Classification: 90C32

Optimality conditions for a class of nonsmooth multi-objective programming problems

ZHOU Xuan-wei
（Dept. of Basic Courses，Zhejiang Shuren Univ.，Hangzhou 310015，China）

In this paper，a class of nonsmooth multi-objective programming problems is studied. By using generalized Farkas lemma and scalarization of multi-objective function，the optimality conditions of cone weakly efficient solution are given for the problem of minimizing a multi-objective function，where the multi-objective function is the sum of a differentiable multi-objective function and a cone convex multi-objective function，subject to a set of differentiable nonlinear functions with a controlled cone on a convex subset of a finite dimensional Euclidean space，under the conditions similar to the Abadie constraint qualification.

nonsmooth multi-objective programming；generalized Abadie constraint qualification；generalized Farkas lemma；optimality conditions

A

1000-4424（2016）01-0063-10

2015-10-08

2016-01-19