組合同倫內點算法求解一類非凸無界優化問題

蔡志丹,趙立芹,蘇孟龍

(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.