法錐條件下非凸規(guī)劃組合同倫算法的復(fù)雜性分析

劉 巍, 薛冬梅

(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

趙立芹)