西南大学学报 (自然科学版)  2018, Vol. 40 Issue (10): 107-111.  DOI: 10.13718/j.cnki.xdzk.2018.10.018
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    欧小庆
    李金富
    刘佳
    廖霞
    陈加伟
    欢迎关注西南大学期刊社
     

  • 一类多目标优化问题弱有效解的必要最优性条件    [PDF全文]
    欧小庆1, 李金富2, 刘佳2, 廖霞2, 陈加伟2     
    1. 重庆人文科技学院 管理学院, 重庆 401524;
    2. 西南大学 数学与统计学院, 重庆 400715
    摘要:标量化方法是研究多目标优化问题的最优性条件与算法的重要手段,最优性理论是优化理论的重要研究内容之一.建立了一类标量化函数的相关性质,并借助标量化技巧与Clarke次微分,在假设次微分约束规格成立的条件下,建立了一类非光滑多目标优化问题的局部弱有效解的Karush-Kuhn-Tucker必要最优性条件.
    关键词多目标优化    局部弱有效解    必要最优性条件    约束规格    

    弱有效解是经济、决策理论、多目标优化理论以及最优控制与博弈论中的重要概念之一.关于多目标优化问题弱有效解的研究常常涉及目标函数与约束函数的凸性[1-5].众所周知,最优性必要条件对研究多目标优化问题的对偶性与算法设计起着至关重要的作用.非光滑优化问题的Lagrange乘子规则已经被许多作者依据不同的次微分广泛地研究了[4-9]. Clarke次微分[6](也被称作Clarke广义梯度)是导出非光滑优化问题优化条件的重要工具.各种次微分,比如Michel-Penot次微分[10]、Mordukhovich次微分[11]、凸化集[9],都是在非光滑优化中建立优化条件的好工具.文献[12-13]研究了带有一般不等约束的非光滑标量优化问题的约束规格与Lagrange乘子的性质,并在适当的约束限定性条件下通过Clarke次微分得到了最优性条件.本文将利用Clarke次微分研究非光滑约束多目标优化的局部弱有效的必要最优化性条件.

    1 预备知识

    X为实Banach空间,X*为其拓扑对偶空间,Y为有限维空间,CD分别是XY中的非空闭凸子集,K${\mathbb{R}^n}$中的点凸锥并且int K$\emptyset $K的对偶锥定义为

    $ {K^*} = \left\{ {\xi \in {X^*}:\left\langle {\xi ,v} \right\rangle \ge 0} \right\} $

    特别地,K*是一个弱*闭凸锥,记K的凸包为co K$\mathbb{R}_ + ^n$ ={x=(x1x2,…,xn):xi≥0,i=1,2,…,n}和$\mathbb{R}_{{\rm{ + + }}}^n$={x=(x1x2,…,xn):xi>0,i=1,2,…,n}.设fX${\mathbb{R}^n}$gXY为向量值映射.

    hX$\mathbb{R}$xX处为局部Lipschitz连续函数,hxX处沿方向vX的Clarke广义导数[6]定义为

    $ {h^0}\left( {\bar x;v} \right) = \mathop {{\rm{lim}}\;{\rm{sup}}}\limits_{x \to \bar x,t \to 0 + } \frac{{h\left( {x + tv} \right) - h\left( x \right)}}{t} $

    hx0处的Clarke次微分定义为

    $ \partial h\left( {{x_0}} \right) = \left\{ {\xi \in {X^*}:\left\langle {\xi ,v} \right\rangle \le {h^0}\left( {x_0},v \right),\forall v \in X} \right\} $

    特别地,Clarke广义导数与次微分满足

    $ {h^0}\left( {x;v} \right) = \max \left\{ {\left\langle {\zeta ,v} \right\rangle ,\zeta \in \partial h\left( x \right)} \right\} $

    集合CXx0C处的Clarke法锥定义为

    $ N\left( {C;{x_0}} \right) = \left\{ {\xi \in {X^*}:\left\langle {\xi ,v} \right\rangle \le 0,\forall v \in T\left( {C;{x_0}} \right)} \right\} $ (1)

    其中T(Cx0)为集合Cx0C处的Clarke切锥,

    T(Cx0)={vX:对∀tn↓0,∀xnx0xnC,存在vnv使得xn+tnvnC}

    本文考虑如下(MP)约束多目标优化问题:求最小的f(x),使得g(x)∈D(xC).

    记问题(MP)的可行集为M.易知,M=g-1(D)∩C,其中

    $ {g^{ - 1}}\left( D \right) = \left\{ {x \in X:g\left( x \right) \in D} \right\} $

    如果存在一个数δ>0,使得

    $ \left( {f\left( {M \cap B\left( {{x_0};\delta } \right)} \right) - f\left( {{x_0}} \right)} \right) \cap \left( { - {\mathop{\rm int}} K} \right) = \emptyset $

    则称x0M为问题(MP)的一个局部弱Pareto有效解,其中B(x0δ)是以x0为球心,δ为半径的开球.如果将B(x0δ)替换为$\mathbb{R}^n$,则可以得到弱有效解的定义.假设fg都在x0M处局部Lipschitz连续.

    定义1[13]  如果对于∀y*N(Dg(x0))\{0},有

    $ 0 \notin \partial \left( {{y^*} \circ g} \right)\left( {{x_0}} \right) + N\left( {C,{x_0}} \right) $

    则称问题(MP)在x0M处满足次微分约束规格(CQ).

    命题1[4, 7]  对于e∈int K,函数ξK(y)=inf{t$\mathbb{R}$yte-K}在$\mathbb{R} ^n$上是连续、正齐次与次可加的,ξK(0)=0,并且严格int K单调的(即如果y2-y1∈int K,则ξK(y1)<ξK(y2)).

    由文献[8]的定理3.1,我们可以得到如下结论:

    命题2  x0M是问题(MP)的一个弱有效解当且仅当ξK(f(x)-f(x0))≥0(∀xM).

    2 主要结果

    借助标量化函数ξK与Clarke次微分,讨论一类非光滑约束多目标优化问题的局部弱有效解的Karush-Kuhn-Tucker必要最优性条件.

    定理1  设x0是问题(MP)的一个局部弱有效解,并且问题(MP)在x0处满足次微分约束规格(CQ).则存在μN(Dg(x0)),使得

    $ 0 \in \partial \varphi \left( {{x_0}} \right) + \partial \left( {\bar \mu \circ g} \right)\left( {{x_0}} \right) + N\left( {C,{x_0}} \right) $ (2)

    其中φ(x)=ξK(f(x)-f(x0)).

      因为x0是问题(MP)的一个局部弱有效解,则由命题2知

    $ \begin{array}{*{20}{c}} {{\xi _K}\left( {f\left( y \right) - f\left( {{x_0}} \right)} \right) \ge 0}&{\forall y \in M \cap B\left( {{x_0};\delta } \right)} \end{array} $

    由于φ(x0)=0,故x0为优化问题的一个局部解:$\mathop {\min }\limits_{x \in M} \varphi \left( x \right)$.应用文献[10]的定理3.2(ⅰ)可得(2)式.

    下面研究命题1中函数ξK的一些性质.

    命题3  ξK0(0;v)=ξK(v)(∀v$\mathbb{R} ^n$).

      由于ξK是正齐次与次可加的,则它是凸函数.故ξK是Clarke正则的,并且有

    $ \xi _K^0\left( {0;v} \right) = {{\xi '}_K}\left( {0;v} \right)\mathop {\lim }\limits_{t \to {0^ + }} \frac{{{\xi _K}\left( {0 + tv} \right) - {\xi _K}\left( 0 \right)}}{t} = {\xi _K}\left( v \right) $

    ξK0(0;v)=ξK(v)(∀v$\mathbb{R} ^n$).

    命题4  $\partial {\xi _K}\left( 0 \right) \subset {K^ * }$.

      假设存在ξ$\partial {\xi _K}\left( 0 \right)$,并且$\xi \notin {K^ * }$.存在vK使得〈ξv〉<0,并且有

    $ \left\langle {\xi , - v} \right\rangle > 0 $ (3)

    因为ξ$\partial {\xi _K}\left( 0 \right)$,结合命题3可得到

    $ \left\langle {\xi , - v} \right\rangle \le {\xi _K}\left( { - v} \right) - {\xi _K}\left( 0 \right) = {\xi _K}\left( { - v} \right) $ (4)

    由于ξK(-v)=inf{t$\mathbb{R}$:-vte-K}与vK,则有v∈0·e-K.因此ξK(-v)≤0.结合(4)式,可得到〈ξ,-v〉≤0,与(3)式矛盾.

    下面我们通过一个例子说明命题3与命题4.

    例1  设K=$\mathbb{R}_ + ^2$e=(1,1).于是有ξK(v1v2)=max{v1v2},故

    $ \partial {\xi _K}\left( 0 \right) = \left\{ {\left( {{\alpha _1},{\alpha _2}} \right) \in {\mathbb{R}^2}:{\alpha _1}{v_1} + {\alpha _2}{v_2} \leqslant \max \left\{ {{v_1},{v_2}} \right\}} \right\} $

    断言

    $ \partial {\xi _K}\left( 0 \right) = \left\{ {\left( {{\alpha _1},{\alpha _2}} \right) \in {\mathbb{R}^2}:{\alpha _1}{\alpha _2} \geqslant 0,{\alpha _1} + {\alpha _2} = 1} \right\} $

    事实上,若α=(α1α2)∈$\partial {\xi _K}\left( 0 \right)$,则有

    $ {\alpha _1}{v_1} + {\alpha _2}{v_2} \le \max \left\{ {{v_1},{v_2}} \right\} $

    v1=v2=1,得到α1+α2≤1;取v1=v2=-1,得到-α1-α2≤-1.故α1+α2≥1,从而α1+α2=1.

    断言α1α2≥0.反之,不失一般性,假设α1<0.取v=(-1,0),则有

    $ {\alpha _1}{v_1} + {\alpha _2}{v_2} = - {\alpha _1} > 0 = \max \left\{ {{v_1},{v_2}} \right\} $

    α=(α1α2)∈$\partial {\xi _K}\left( 0 \right)$矛盾!故α1α2≥0,从而$\partial {\xi _K}\left( 0 \right) \subset {K^ * } = \mathbb{R}_ + ^2$.易知(1,0),(0,1)∈$\partial {\xi _K}\left( 0 \right)$.对∀v=(v1v2)∈${\mathbb{R}^2}$,有

    $ \xi _K^0\left( {0;v} \right) = \mathop {\max }\limits_{\alpha \in \partial {\xi _K}\left( 0 \right)} \left( {{\alpha _1}{v_1} + {\alpha _2}{v_2}} \right) = \max \left\{ {{v_1},{v_2}} \right\} = {\xi _K}\left( v \right) $

    定理2  设x0为问题(MP)的一个局部弱有效解,并且问题(MP)在x0处满足次微分约束规格(CQ).则存在λ=(λ1,…,λn)∈K*λ≠0,μN(Dg(x0)),使得

    $ 0 \in \sum\limits_{i = 1}^n {{{\bar \lambda }_i}\partial {f_i}\left( {{x_0}} \right)} + \partial \left( {\bar \mu \circ g} \right)\left( {{x_0}} \right) + N\left( {C,{x_0}} \right) $ (5)

      因为x0是问题(MP)的局部弱有效解,由定理1可知,存在μN(Dg(x0)),使得

    $ 0 \in \partial \varphi \left( {{x_0}} \right) + \partial \left( {\bar \mu \circ g} \right)\left( {{x_0}} \right) + N\left( {C,{x_0}} \right) $ (6)

    其中φ(x)=ξK(f(x)-f(x0)).由于ξK为凸函数,故它是Clarke正则的.结合文献[6]的定理2.3.9,我们得到

    $ \partial \varphi \left( {{x_0}} \right) \subset {\rm{co}}\left\{ {\sum\limits_{i = 1}^n {{\alpha _i}{\xi _i}:\alpha } = \left( {{\alpha _1}, \cdots ,{\alpha _n}} \right) \in \partial {\xi _K}\left( 0 \right),{\xi _i} \in \partial {f_i}\left( {{x_0}} \right)} \right\} $ (7)

    再由(6)式可知,存在γ$\partial \varphi \left( {{x_0}} \right)$,使得

    $ 0 \in \bar \gamma + \partial \left( {\bar \mu \circ g} \right)\left( {{x_0}} \right) + N\left( {C,{x_0}} \right) $ (8)

    并且

    $ \bar \gamma \in {\rm{co}}\left\{ {\sum\limits_{i = 1}^n {{\alpha _i}{\xi _i}} :\alpha \in \partial {\xi _K}\left( 0 \right),{\xi _i} \in \partial {f_i}\left( {{x_0}} \right)} \right\} $

    因此,存在η1,…,ηm≥0,$\sum\limits_{i = 1}^m {{\eta _k} = 1} $,使得

    $ \bar \gamma = \sum\limits_{i = 1}^m {{\eta _k}} \left( {\sum\limits_{i = 1}^n {\alpha _i^{\left( k \right)}\xi _i^{\left( k \right)}} } \right) $

    其中

    $ \begin{array}{*{20}{c}} {{\alpha ^{\left( k \right)}} = \left( {\alpha _1^{\left( k \right)}, \cdots ,\alpha _n^{\left( k \right)}} \right) \in \partial {\xi _K}\left( 0 \right)}&{\xi _i^{\left( k \right)} \in \partial {f_i}\left( {{x_0}} \right)} \end{array} $

    $ \bar \gamma \in \sum\limits_{k = 1}^m {{\eta _k}} \left( {\sum\limits_{i = 1}^n {\alpha _i^{\left( k \right)}\partial {f_i}\left( {{x_0}} \right)} } \right) = \sum\limits_{i = 1}^n {\left( {\sum\limits_{k = 1}^m {{\eta _k}\alpha _i^{\left( k \right)}} } \right)\partial {f_i}\left( {{x_0}} \right)} $ (9)

    不妨设${\overline \lambda _i} = \sum\limits_{k = 1}^m {{\eta _k}\alpha _i^{\left( k \right)}} $,则有

    $ \bar \lambda = \left( {{{\bar \lambda }_1}, \cdots ,{{\bar \lambda }_n}} \right) = \sum\limits_{k = 1}^m {{\eta _k}} \left( {\alpha _1^{\left( k \right)}, \cdots ,\alpha _n^{\left( k \right)}} \right) = \sum\limits_{k = 1}^m {{\eta _k}{\alpha ^{\left( k \right)}}} \in \partial {\xi _K}\left( 0 \right) $

    由于$\partial {\xi _K}\left( 0 \right)$是凸的,结合(8),(9)式可以得到

    $ 0 \in \sum\limits_{i = 1}^n {{{\bar \lambda }_i}\partial {f_i}\left( {{x_0}} \right)} + \partial \left( {\bar \mu \circ g} \right)\left( {{x_0}} \right) + N\left( {C,{x_0}} \right) $

    结合命题4,有$\partial {\xi _K}\left( 0 \right) \subset {K^ * }$,从而λK*.因为λ$\partial {\xi _K}\left( 0 \right) \subset {K^ * }$,我们有

    $ \begin{array}{*{20}{c}} {\left\langle {\bar \lambda ,v} \right\rangle \leqslant {\xi _K}\left( v \right) - {\xi _K}\left( 0 \right) = {\xi _K}\left( v \right)}&{\forall v \in {\mathbb{R}^n}} \end{array} $

    v=-e,得到-e∈-1·e-K.由于

    $ {\xi _K}\left( { - e} \right) = {\text{inf}}\left\{ {t \in \mathbb{R}: - e \in te - K} \right\} $

    于是有ξK(-e)≤-1,则〈λ,-e〉≤ξK(-e)≤-1,故λ≠0.综上所述,存在λ=(λ1,…,λn)∈K*λ≠0与μN(Dg(x0)),使得(5)式成立.

    特别地,如果$\mathbb{R}_{\rm{ + }}^n \subset K$,下面的结论成立:

    推论1  设x0是问题(MP)的局部弱有效解,问题(MP)在x0处满足次微分约束规格(CQ),并且$\mathbb{R}_{\rm{ + }}^n \subset K$.则存在λ=(λ1,…,λn)∈K*$ \subset \mathbb{R}_{\rm{ + }}^n$λ≠0和μN(Dg(x0)),使得(5)式成立.

    在条件$\mathbb{R}_{\rm{ + }}^n \subset {\mathop{\rm int}} \;K\; \cup \left\{ 0 \right\}$下,我们得到问题(MP)的强Kasush-Kuhn-Tucker必要最优性条件:

    定理3  设x0是问题(MP)的局部弱有效解,问题(MP)在x0处满足次微分约束规格(CQ),并且$\mathbb{R}_{\rm{ + }}^n \subset {\mathop{\rm int}} \;K\; \cup \left\{ 0 \right\}$,则存在λ=(λ1,…,λn)∈$\mathbb{R}_{{\rm{ + + }}}^n$μN(Dg(x0)),使得

    $ 0 \in \sum\limits_{i = 1}^n {{{\bar \lambda }_i}\partial {f_i}\left( {{x_0}} \right)} + \partial \left( {\bar \mu \circ g} \right)\left( {{x_0}} \right) + N\left( {C,{x_0}} \right) $ (10)

      由定理2可知,存在λ=(λ1,…,λn)∈K*λ≠0,μN(Dg(x0)),使得(10)式成立.下面我们说明λi>0(∀i=1,…,n).断言K*$ \subset \mathbb{R}_{{\rm{ + + }}}^n \cup \left\{ 0 \right\}$.假设存在α=(α1,…,αn)∈K*kj,使得αk=0,αj>0.因为$\mathbb{R}_{\rm{ + }}^n \subset {\mathop{\rm int}} \;K\; \cup \left\{ 0 \right\}$,则有K*$ \subset \mathbb{R}_{\rm{ + }}^n$.用εk表示第k个分量为1的单位向量(k=1,…,n).因为$\mathbb{R}_{\rm{ + }}^n \subset {\mathop{\rm int}} \;K\; \cup \left\{ 0 \right\}$,故εk∈int K成立(k=1,…,n).因此,存在充分小的t>0,使得

    $ v = {\varepsilon _k} - t{\varepsilon _j} \in K $

    并且

    $ \left\langle {v,\bar \alpha } \right\rangle = \left\langle {{\varepsilon _k},\bar \alpha } \right\rangle - t\left\langle {{\varepsilon _j},\bar \alpha } \right\rangle = - t{{\bar \alpha }_j} < 0 $

    K*的定义矛盾.故K*$ \subset \mathbb{R}_{{\rm{ + + }}}^n \cup \left\{ 0 \right\}$.由于λ$\partial {\xi _K}\left( 0 \right) \subset {K^ * }$λ≠0,于是有λ$\mathbb{R}_{{\rm{ + + }}}^n$.

    参考文献
    [1] 陈加伟, 李军, 王景南. 锥约束非光滑多目标优化问题的对偶及最优性条件[J]. 数学物理学报, 2012, 32(1): 1-12. DOI:10.3969/j.issn.1003-3998.2012.01.001
    [2] 周志昂. 强G-预不变凸向量优化问题的最优性条件[J]. 西南大学学报(自然科学版), 2013, 35(1): 65-68.
    [3] 欧小庆, 李金富, 刘佳, 等. 一类约束多目标优化问题弱有效解的一个择一定理[J]. 西南大学学报(自然科学版), 2017, 39(1): 109-113.
    [4] 赵克全, 戎卫东, 杨新民. 新的非线性分离定理及其在向量优化中的应用[J]. 中国科学(数学), 2017, 47(4): 533-544.
    [5] CHEN J W, CHO Y J, KIM J, et al. Multiobjective Optimization Problems with Modified Objective Functions and Cone Constraints and Applications[J]. J Glob Optim, 2011, 49(1): 137-147. DOI:10.1007/s10898-010-9539-3
    [6] CLARKE F H. Optimization and Nonsmooth Analysis[M]. New York: Wiley Interscience, 1983.
    [7] KHAN A A, TAMMER C, ZALINESCU C. Set-valued Optimization:An Introduction with Applications[M]. Berlin: Springer, 2015.
    [8] GONG X H. Scalarization and Optimality Conditions for Vector Equilibrium Problems[J]. Nonlinear Anal, 2010, 73(11): 3598-3612. DOI:10.1016/j.na.2010.07.041
    [9] JEYAKUMAR V, LUC D T. Nonsmooth Calculus, Minimality, and Monotonicity of Convexificators[J]. J Optim Theory Appl, 1999, 101(3): 599-621. DOI:10.1023/A:1021790120780
    [10] MICHEL P, PENOT J P. Calcul Sous-Différentiel Pour Des Fonctions Lipschitziennes et Nonlipschitziennes[J]. C R Math Acad Sci, 1984, 298(12): 269-272.
    [11] MORDUKHOVICH B S, SHAO Y. On Nonconvex Subdifferential Calculus in Banach Spaces[J]. J Convex Anal, 1995(2): 211-227.
    [12] JOURANI A, THIBAULT L. Approximations and Metric Regularity in Mathematical Programming in Banach Spaces[J]. Math Oper Res, 1993, 18(2): 390-401. DOI:10.1287/moor.18.2.390
    [13] JOURANI A. Constraint Qualifications and Lagrange Multipliers in Nondifferentiable Programming Problems[J]. J Optim Theory Appl, 1994, 81(3): 533-548. DOI:10.1007/BF02193099
    Necessary Optimality Conditions for a Class of Nonsmooth Constrained Multiobjective Optimization Problems
    OU Xiao-qing1, LI Jin-fu2, LIU Jia2, LIAO Xia2, CHEN Jia-wei2     
    1. College of Management, Chongqing College of Humanities, Science & Technology, Chongqing 401524, China;
    2. School of Mathematics and Statistics, Southwest University, Chongqing 400715, China
    Abstract: The scalarization method is an important means for the study of optimality and algorithms of multi-objective optimization problems, and optimality theory is one of the important contents in the optimization theory. In this paper, we first establish some properties of a class of scalarization functions. Then, with the scalarization method and Clarke subdifferentials, we establish the Karush-Kuhn-Tucker necessary optimality conditions for the local weakly efficient solution of a nonsmooth constrained multi-objective optimization problem under the assumption of subdifferential constraint qualification.
    Key words: multiobjective optimization    local weakly efficient solution    necessary optimality condition    constraint qualification    
    X