一類優化問題的動約束組合同倫算法

王 艷, 王秀玉, 劉慶懷

(長春工業大學 基礎科學學院, 長春 130012)

同倫算法由于具有大范圍收斂性而成為證明非線性問題解存在的有效方法之一, 同倫算法不僅能獲得解的存在性, 而且能進行求解計算, 既適用于凸優化問題, 也適用于非凸、 非線性優化問題. 文獻[1-2]利用同倫方法得到了互補問題有解的條件; 文獻[3-4]對多目標優化和變分不等式問題分別構造了同倫方程, 并獲得了問題的解; 文獻[5-7]研究了非線性優化問題的組合同倫算法; 文獻[8-9]研究了光滑非凸優化的動約束組合同倫算法. 但利用組合同倫方法求解非凸、 非線性優化問題, 還需要條件： 可行域滿足法錐條件, 或者滿足擬法錐條件, 或者滿足偽法錐條件. 當可行域不滿足各類法錐條件時, 利用組合同倫方法求解非凸非線性優化問題的研究結果目前較少. 本文利用文獻[9]中的動約束技術, 給出了當可行域不滿足各類法錐條件時, 一類優化問題的動約束組合同倫算法.

1 預備知識

設φ:D?Rm→Rn是光滑映射, 對任意的y∈Rn, 記φ-1(y)={x∈Dφ(x)=y}為y在映射φ下的逆像. 如果φ在x(0)∈D處的Jacobi矩陣?φ(x(0))/?x行滿秩, 則稱x(0)是映射φ的正則點; 否則稱x(0)是φ的臨界點. 如果對所有的x(0)∈φ-1(y(0))都是映射φ的正則點, 則稱y(0)是映射φ的正則值; 否則稱y(0)是φ的臨界值.

引理1(參數化的Sard定理)[10]設V?Rn,U?Rm均為開集,φ:V×U→Rp是Cr映射, 這里r>max{0,m-p}. 如果0∈Rp是φ的一個正則值, 則對幾乎所有a∈V,0是φ(a,·)的一個正則值.

引理2(逆映像定理)[11]如果0是映射φ(a,·)的正則值, 則逆映射φ-1(a,·)由有限條一維光滑流形組成.

引理3(一維流形分類定理)[11]一維帶邊光滑流形的每個連通分支, 或者微分同胚于單位圓周, 或者微分同胚于區間(0,1]或(0,1)或[0,1].

考慮問題(P)：

記I(x)={i∈M:gi(x)=0},g(x)=(g1(x),g2(x),…,gm(x))T, ▽g(x)=(▽g1(x),▽g2(x),…,▽gm(x)),Ω={x∈Rn:gi(x)≤0,i∈M},Ω0={x∈Rn:gi(x)<0,i∈M}, ?Ω=ΩΩ0.

假設條件如下:

(H1)f,gi(i∈M)∈Cr(r≥3);

(H2)Ω0非空且Ω有界連通;

(H3) 對任意的x∈?Ω, {▽g(x)i∈(x)}是正獨立的.

記gi(x,u)=gi(x),i∈M;Ω(μ)={x∈Rngi(x,μ)≤0,i∈M∪{m+1}};Ω0(μ)={x∈Rngi(x,μ)<0,i∈M<∪{m+1}};g(x,μ)=(g1(x),g2(x),…,gm(x),gm+1(x,μ))T. 通過選取一個適當的動約束函數gm+1(x,u), 使得如下假設成立：

無解, 其中: ?Ω(μ)=Ω(μ)Ω0(μ);I(x,μ)={i∈M∪{m+1}gi(x,μ)=0};

(H5)gm+1(x,μ)關于x及μ充分光滑, ?μ∈[0,1]θ,Ω0(μ)非空,Ω(μ)有界且Ω(0)=Ω, ?x∈?Ω(μ), {▽xgi(x,μ)i∈I(x,μ)}正獨立;

2 主要結果

(1)

其中:y=(y1,y2,…,ym,ym+1)T;g(x,μ)=(g1(x,μ),g2(x,μ),…,gm+1(x,μ))T;

(2)

問題(P)的K-K-T方程為

(3)

方程(2) 的解必為方程(3)的解, 且顯然有H(ω(0),ω(0),1)=0.

證明:H(ω,ω(0),μ)的Jocobi矩陣記為H′(ω,ω(0),μ),

從而H′(ω,ω(0),μ)行滿秩, 由引理1知,0是H(ω,ω(0),μ)的正則值. 又由引理2知,H-1(0)所含曲線是光滑的, 且H(ω(0),ω(0),1)=0, 因而, 存在一條起始于(ω(0),1)的光滑曲線, 記為Γω(0).

證明: 用反證法. 假設光滑曲線Γω(0)無界, 則必存在點列(x(k),y(k),μk)∈Γω(0), 使得‖(x(k),y(k),μk)‖→∞(k→∞). 由同倫方程(1)的第二式得

(4)

(5)

將式(5)整理如下：

情形1)μ*=1. 式(6)兩邊取極限得

與(H6)矛盾.

式(7)兩邊取極限得

(8)

證明:Γω(0)的存在性及有界性由引理4和引理5可知. 又由引理3知,Γω(0)或微分同胚于單位圓周, 或微分同胚于單位區間(0,1]. 因為

其中:

3)μ*=0, (x(*),y(*))∈Ω×R+, ‖y(*)‖<∞.

3 路徑跟蹤算法及算例

算法1Euler-Newton法[12].

輸入ω(0), 選取初始步長h0>0, 正數J1=2,J2=5及小正數ε1,ε2,α,β∈(0,1), 并且令μ0=1,k=0.

2) 計算預估點(ω(k+1,0),μk+1,0)=(ω(k),μk)+αlhkη(k), 其中l是使得(ω(k+1,0)μk+1,0)∈Ω0×(0,1]成立的最小正整數.

3) 計算校正點(ω(k+1),μk+1): 若使(ω(k+1,0),μk+1,0)∈Ω0×(0,1]成立的最小正整數j≤J2, 且‖H(ω(k+1, j),μk+1, j)‖>ε1, 則

(ω(k+1, j),μk+1, j)=(ω(k, j-1),μk, j-1)-βl(H′(ω(k, j-1),μk, j-1))+H(ω(k, j-1),μk, j-1),

其中l是使得(ω(k+1, j),μk+1, j)∈Ω0×(0,1]成立的最小正整數,j∶=j+1.

若‖H(ω(k+1, j),μk+1, j)‖≤ε1, 且j≤J1, 則令(ω(k+1),μk+1)=(ω(k+1, j),μk+1, j),hk+1=min{h0,1.25hk}, 轉4);

若‖H(ω(k+1, j),μk+1, j)‖>ε1,hk+1=0.75hk,k∶=k+1, 則轉3).

4)μk+1≤ε2, 則停; 否則置k=k+1, 轉1).

在算法的步驟3)中, (H′(ω,μ))+=H′(ω,μ)T(H′(ω,μ)H′(ω,μ)T)-1是H′(ω,μ)的Moore-Penrose逆.

例1

可行域不滿足偽錐條件, 構造動約束函數如下：

[1] YU Qian, HUANG Chong-chao, WANG Xian-jia. A Combined Homotopy Interior Point Method for the Linear Complementarity Problem [J]. Applied Mathematics and Computation, 2006, 179(2): 696-701.

[2] DING Jun-di, YIN Hong-you. A New Homotopy Method for Nonlinear Complementarity Problems [J]. Numericla Mathematics: A Journal of Chinese Universities (English Series), 2007, 16(2): 155-163.

[3] Song W, Yao G M. Homotopy Method for a General Multiobjective Programming Problem [J]. J Optim Theory Apply, 2008, 138(1): 139-153.

[4] XU Qing, YU Bo, FENG Guo-chen. Homotopy Method for Solving Variational Inequalities in Unbounded Sets [J]. Journal of Global Optimization, 2005, 31(1): 121-131.

[5] 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.

[6] LIU Qing-huai, YU Bo, FENG Guo-chen. The Homotopy Interior-Point Method for Nonconvex Nonlinear Programming Problem Based on Quasi-normal Cone Condition [J]. Acta Mathematicae Applicatae Sinica, 2003, 26(2): 372-377. (劉慶懷, 于波, 馮果忱. 基于擬法錐條件的非凸非線性規劃問題的同倫內點法 [J]. 應用數學學報, 2003, 26(2): 372-377.)

[7] LIN Zheng-hua, LI Yong, YU Bo. A Combined Homotopy Interior Point Method for General Nonlinear Programming Problems [J]. Appl Math Comput, 1996, 80(2/3): 209-226.

[8] SHANG Yu-feng, YU Bo. Boundary Moving Combined Homotopy Method for Nonconvex Nonlinear Programming and Its Convergence [J]. Journal of Jilin University: Science Edition, 2006, 44(3): 357-361. (商玉鳳, 于波. 凸規劃的動邊界組合同倫方法及其收斂性 [J]. 吉林大學學報: 理學版, 2006, 44(3): 357-361.)

[9] SHANG Yu-feng. Constraint Shifting Combined Homotopy Method for Solving Nonlinear Programming, Equilibrium Programming and Variational Inequality [D]: [Ph D Thesis]. Changchun: Jilin University, 2006. (商玉鳳. 解非線性規劃、 均衡規劃和變分不等式問題的動約束組合同倫方法 [D]: [博士學位論文]. 長春: 吉林大學, 2006.)

[10] Allgor E L, Georg K. Numerical Continuation Method: An Introduction [M]. Berlin: Springer-Verlag, 1990.

[11] Naber G L. Topological Method in Euclidean Space [M]. London: Cambridge University Press, 1980.

[12] FAN Xiao-na, YU Bo. A Smoothing Homotopy Method for Solving Variational Inequalities [J]. Nonlinear Analysis: Theory, Method & Applications, 2009, 70(1): 211-219.