组合同伦内点算法求解一类非凸无界优化问题

蔡志丹,赵立芹,苏孟龙

(1.长春理工大学 理学院,长春 130022;2.吉林大学 学报编辑部,长春 130012;3.洛阳师范学院 数学学院,河南 洛阳 471022;4.吉林大学 符号计算与知识工程教育部重点实验室,长春 130012)

0 引 言

考虑一般的非线性最优化问题:

其中f,gi是三次连续可微的函数.Ω={x∈n:gi(x)≤0,i=1,2,…,m}称为问题(1)的可行集;Ω0={x∈n:gi(x)<0,i=1,2,…,m}称为问题(1)的严格可行集;∂Ω=ΩΩ0为Ω的边界.此外,和分别表示m维欧式空间的非负和正象限,

B(x)={i∈{1,2,…,m}:gi(x)=0},g(x)=(g1(x),…,gm(x))∈m.

(2)

系统(2)称为问题(1)的K-K-T条件.若(x*,y*)满足式(2),则x*称为问题(1)的K-K-T点,y*称为对应于x*的Lagrange乘子向量.如果f(x)和g(x)都是凸的,则x*为问题(1)的解当且仅当x*是问题(1)的K-K-T点.

冯果忱等[1]针对系统(2)构造了如下同伦方程:

(3)

林正华等[8]把文献[1]的结果进一步推广到更一般的非凸集合上,并构造了如下同伦方程:

(4)

其中ξi(x,μ)=(1-μ)gi(x)+μηi(x),i=1,2,…,m,ηi(x)为二次连续可微函数.记ξ(x,μ)=(ξ1(x,μ),…,ξm(x,μ)),η(x)=(η1(x),…,ηm(x)).

文献[8]的结果是在Ω有界的假设下取得的,本文通过引入文献[5]中无穷远解的思想去掉了文献[8]的有界性假设,给出计算无界非凸优化问题的组合同伦内点算法.在适当的条件下,对无界非凸区域内部几乎所有给定的点,本文给出了连接该点与非凸优化K-K-T点同伦路径存在性的构造性证明,从而得到了组合同伦内点算法的全局收敛性结果,为计算无界非凸优化问题提供了一种全局收敛性算法.此外,与通常的延拓法相比,本文利用参数化Sard定理回避了横截性,即解曲线非退化性的讨论.

1 主要结果

利用无穷远解的概念,做如下基本假设:

(H1)Ω0非空;

(H3) 非凸优化问题没有无穷远解;

因此,可得如下不等式:

‖x-α‖2-‖x(0)-α‖2≤2(x-α)T(x-x(0)).

(5)

利用同伦方程(4),有

(1-μk)(f(x(k))+ξ(x(k),μk)y(k))+μk(x(k)-x(0))=0,

(6)

Y(k)g(x(k))-μkY(0)g(x(0))=0.

(7)

在式(6)两边同乘以(x(k)-α)T,则有

(1-μk)(x(k)-α)T[f(x(k))+ξ(x(k),μk)y(k)]=-μk(x(k)-α)T(x(k)-x(0)).

(8)

由式(5),(8)得

再由式(9)得

(α-x(k))T[

(10)

若‖x(k)‖→∞,则对式(10)两端同时取极限得

(11)

这与假设(H3)矛盾.证毕.

对任意给定的w(0),把H(w,w(0),μ)改写成Hw(0)(w,μ).下面给出本文的主要结果.

H(w(s),w(0),μ(s))=0, (w(0),μ(0))=(w(0),1),

(12)

并且当μ(s)→0时,w(s)趋于一点w*=(x*,y*).特别地,w*在曲线Γw(0)上的分量x*是问题(1)的K-K-T点.

根据一维光滑流形分类定理,Γw(0)或者微分同胚于单位圆或者微分同胚于单位区间(0,1].易验证∂Hw(0)(w(0),1)/∂w是非奇异的,因此Γw(0)微分同胚于单位区间.

设(w*,μ*)是Γw(0)上的极限点,则有可能发生下列情形:

(i) 当μ*=1时,由同伦方程(4)的第一个等式得

(14)

(ii) 当μ*<1时,由同伦方程(4)的第一个等式得

(15)

(16)

综上可知,情形1)是唯一情形,因此x*是问题(1)的K-K-T点.证毕.

[1] FENG Guo-chen,LIN Zheng-hua,YU Bo.Existence of Interior Pathway to the Karush-Kuhn-Tucker Point of a Nonconvex Programming Problem [J].Nonlinear Anal:Theory,Methods &Applications,1998,32(6):761-768.

[2] LIN Zheng-hua,YU Bo,FENG Guo-chen.A Combined Homotopy Interior Point Method for Convex Nonlinear Programming [J].Appl Math Comput,1997,84(2/3):193-211.

[3] YU Bo,XU Qing,FENG Guo-chen.On the Complexity of a Combined Homotopy Interior Method for Convex Programming [J].Journal of Computational and Applied Mathematics,2007,200(1):32-46.

[4] LIU Qing-huai,YU Bo,FENG Guo-chen.An Interior Point Path-Following Method for Nonconvex Programming with Quasi-normal Cone Condition [J].Advances in Mathematics,2000,19(4):281-282.

[5] XU Qing,LIN Zheng-hua.The Combined Homotopy Convergence in Unbounded Set [J].Acta Mathematicae Applicatae Sinica,2004,27(4):624-631.

[6] XU Qing,DANG Chuang-yin,ZHU Dao-li.Generalizations of Fixed Point Theorems and Computation [J].Journal of Mathematical Analysis and Applications,2009,354(2):550-557.

[7] SU Meng-long,YU Bo,SHI Shao-yun.A Boundary Perturbation Interior Point Homotopy Method for Solving Fixed Point Problems [J].Journal of Mathematical Analysis and Applications,2011,377(2):683-694.

[8] LIN Zheng-hua,SONG Dai-cai,ZHAO Li-qin.A Continuation Method for Solving the K-K-T Point of General Nonconvex Programming Problems [J].Appl Math J Chinese Univ:Ser A,2002,17(2):217-224.(林正华,宋岱才,赵立芹.连续化方法求解一般非凸规划的K-K-T点 [J].高校应用数学学报:A辑,2002,17(2):217-224.)

[9] SUN Wen-juan,LIU Qing-huai,WANG Cai-ling.Homotopy Method for Getting a Local Minimum of a Class of Non-convex Programming [J].Journal of Jilin University:Science Edition,2008,46(3):469-471.(孙文娟,刘庆怀,王彩玲.同伦方法求解一类非凸规划问题的局部极小 [J].吉林大学学报:理学版,2008,46(3):469-471.)

[10] Allgower E L,Georg K.Introduction to Numerical Continuation Algorithms Methods [M].New York:Society for Industried and Applied Mathematics,2003.