劉 巍, 薛冬梅
(1.吉林化工學(xué)院 理學(xué)院, 吉林 吉林 132022; 2.吉林大學(xué) 數(shù)學(xué)學(xué)院, 長(zhǎng)春 130012)
(xk+1,yk+1)=(xk,yk)+λk((Δ xk,Δ yk));
研究快報(bào)
法錐條件下非凸規(guī)劃組合同倫算法的復(fù)雜性分析
劉 巍1,2, 薛冬梅1
(1.吉林化工學(xué)院 理學(xué)院, 吉林 吉林 132022; 2.吉林大學(xué) 數(shù)學(xué)學(xué)院, 長(zhǎng)春 130012)
考慮非凸規(guī)劃組合同倫算法的復(fù)雜性問(wèn)題, 假設(shè)目標(biāo)函數(shù)在一個(gè)相當(dāng)大的范圍內(nèi)有界, 避免了可行域非凸情形下算法產(chǎn)生的迭代點(diǎn)列不在可行域內(nèi)的情形, 并證明了可行域滿(mǎn)足法錐條件時(shí)非凸規(guī)劃組合同倫算法的復(fù)雜性, 得到了相應(yīng)的估計(jì)結(jié)果.
非凸規(guī)劃; 同倫算法; 復(fù)雜性分析
算法復(fù)雜度是衡量一個(gè)算法優(yōu)劣的重要標(biāo)準(zhǔn), 目前已有許多研究結(jié)果[1-7].徐慶等[8]在自和諧條件下, 估計(jì)凸非線(xiàn)性規(guī)劃組合同倫內(nèi)點(diǎn)法的多項(xiàng)式復(fù)雜性, 得到了與原有內(nèi)點(diǎn)法類(lèi)似的復(fù)雜度估計(jì).本文在法錐條件下分析非凸規(guī)劃問(wèn)題組合同倫算法的復(fù)雜性.
考慮如下非凸規(guī)劃問(wèn)題:
記M={1,2,…,m}, 可行集合Ω={x∈n|g(x)≤0}, 嚴(yán)格可行集Ω0={x∈n|g(x)<0},Ω的邊界集?Ω=ΩΩ0,I(x)={i∈M|gi(x)=0}.
假設(shè)條件:
(H1)f,gi(i∈M)至少三次連續(xù)可微(在Θ上);
(H2)Ω0非空,Ω有界連通;
(H3) ?x∈?Ω, {gi(x)|i∈I(x)}正獨(dú)立;
(H4)Ω滿(mǎn)足法錐條件: ?x∈?Ω,
記同倫方程中的第二個(gè)方程為
引理1對(duì)任給的a,b∈1和μ>0, 若記Φμ(a,b)=-μln(e-a/μ+e-b/μ), 則有
引理2由式(1)和式(2)顯然有
定理1序列{xk},{y(k)}有界.
證明: 情形1)μ=1.將式(1)改寫(xiě)為
即-ln(e-yi+e-gi(x0))=0,yi=-ln(1-e-gi(x0))>0,i∈M解唯一.
情形2)μ=0.此時(shí)式(1)變?yōu)?/p>
由式(4)有
將式(3)改寫(xiě)為
這與(H3)矛盾.故{y(k)}有界.
證明: 利用一維流形分類(lèi)定理可證.
算法1
初始化: 設(shè)μ0>0,β>0.給定ω=(x,y), (x0,y0)∈n+m, 使得(x0,y0)∈N(β,μ0), 選取δi∈(0,1],αi∈(0,1],i=1,2.取
步驟:
1) 計(jì)算Newton方向, 設(shè)Δωk=(Δxk,Δyk)是如下方程組的解:
H(ωk,μk)+ωH(ωk,μk)TΔωk=0;
2) 計(jì)算迭代點(diǎn), 如果‖H(ωk,μk)‖∞=0, 則取ωk+1=ωk, 即(xk+1,yk+1)=(xk,yk); 否則, 設(shè)λk是使
‖H(ωk+λkΔωk,μk)‖∞≤(1-δ1λk)‖H(ωk,μk)‖∞
(xk+1,yk+1)=(xk,yk)+λk((Δxk,Δyk));
引理3若假設(shè)(H1),(H2)成立, 則?C>0(C為常數(shù)), 對(duì)?ω∈Θ,
證明: 利用Taylor展開(kāi)式即得.
假設(shè)條件:
(H5) 對(duì)?ω∈Θ,ωH(ω,μ)可逆, 且‖ωH(ω,μ)-T‖∞≤k.
定理3設(shè)0≤λ≤1, Δω是方程組
的解, 且
‖H(ω,μ)‖∞≤βμH(ω,μ)+ωH(ω,μ)TΔω=0,
則
‖H(ω+λΔω,μ)‖∞≤(1-δ1λ)‖H(ω,μ)‖∞.
證明: 由式(8)及
有
證明: 由
有
綜上, 本文在法錐條件下, 通過(guò)假設(shè)可行域在整個(gè)大的鄰域內(nèi)有界, 考慮用一個(gè)大球(凸集)把非凸區(qū)域罩上的思想, 避免了在求解非凸規(guī)劃問(wèn)題時(shí)算法有些迭代點(diǎn)跳出不在可行域內(nèi)的情形, 并證明了相應(yīng)算法具有多項(xiàng)式復(fù)雜性.
[1]BIAN Wei, CHEN Xiaojun.Smoothing SQP Algorithm for Non-Lipschitz Optimization with Complexity Analysis [J/OL].2012-02-06.http://www.polyu.edu.hk/ama/staff/xjchen/SQP4Feb.pdf.
[2]Cartis C, Gould N I M, Toint Ph L.On the Evaluation Complexity of Composite Function Minimization with Applications to Nonconvex Nonlinear Programming [J].SIAM J Optim, 2011, 21(4): 1721-1739.
[3]Cartis C, Gould N I M, Toint Ph L.On the Complexity of Steepest Descent, Newton’s and Regularized Newton’s Methods for Nonconvex Unconstrained Optimization [J].SIAM J Optim, 2010, 20(6): 2833-2852.
[4]GE Dongdong, JIANG Xiaoye, YE Yinyu.A Note on the Complexity ofLpMinimization [J].Math Program: Ser B, 2011, 129(2): 285-299.
[5]周俊萍, 姜蘊(yùn)暉, 殷明浩.最壞情況下X2SAT問(wèn)題的上界 [J].計(jì)算機(jī)研究與發(fā)展, 2014, 51(3): 598-605.(ZHOU Junping, JIANG Yunhui, YIN Minghao.New Worst-Case Upper Bounds for X2SAT [J].Journal of Computer Research and Development, 2014, 51(3): 598-605.)
[6]ZHANG Cunhui.Nearly Unbiased Variable Selection under Minimax Concave Penalty [J].Ann Statist, 2010, 38(2): 894-942.
[7]CHEN Xiaojun.Smoothing Methods for Nonsmooth, Novonvex Minimization [J].Math Program, 2012, 134(1): 71-99.
[8]XU Qing, YU Bo.Homotopy Method for Non-convex Programming in Unbounded Set [J].Northeast Math J, 2005, 21(1): 25-31.
ComplexityAnalysisfortheHomotopyMethodofNon-convexProgrammingunderNormalConeConditions
LIU Wei1,2, XUE Dongmei1
(1.SchoolofScience,JilinInstituteofChemicalTeachnology,Jilin132022,JilinProvince,China;
2.CollegeofMathematics,JilinUniversity,Changchun130012,China)
The complexity of the case of non-convex programming problem homotopy algorithm was researched.We assumed the objective function to be bounded in a fairly large range so as to avoid the non-convex case of feasible region.The algorithm generated iterate column is not in the feasible domain.We proved the complexity of non-convex cone planning group homotopy algorithm when the feasible region satisfied the normal cone conditions and got the corresponding estimates.
non-convex programming; homotopy method; complexity analysis
2014-07-11.
劉 巍(1984—), 女, 漢族, 博士研究生, 從事應(yīng)用數(shù)學(xué)的研究, E-mail: 1084258210@qq.com.通信作者: 薛冬梅(1980—), 女, 漢族, 碩士, 講師, 從事應(yīng)用數(shù)學(xué)的研究, E-mial: boots119@163.com.
吉林省自然科學(xué)基金(批準(zhǔn)號(hào): 201215128).
O224
A
1671-5489(2014)06-1203-04
10.13413/j.cnki.jdxblxb.2014.06.18
趙立芹)