法锥条件下非凸规划组合同伦算法的复杂性分析

刘 巍, 薛冬梅

(1.吉林化工学院 理学院, 吉林 吉林 132022； 2.吉林大学 数学学院, 长春 130012)

(xk+1,yk+1)=(xk,yk)+λk((Δ xk,Δ yk));

研究快报

法锥条件下非凸规划组合同伦算法的复杂性分析

刘 巍1,2, 薛冬梅1

(1.吉林化工学院 理学院, 吉林 吉林 132022； 2.吉林大学 数学学院, 长春 130012)

考虑非凸规划组合同伦算法的复杂性问题, 假设目标函数在一个相当大的范围内有界, 避免了可行域非凸情形下算法产生的迭代点列不在可行域内的情形, 并证明了可行域满足法锥条件时非凸规划组合同伦算法的复杂性, 得到了相应的估计结果.

非凸规划； 同伦算法； 复杂性分析

算法复杂度是衡量一个算法优劣的重要标准, 目前已有许多研究结果[1-7].徐庆等[8]在自和谐条件下, 估计凸非线性规划组合同伦内点法的多项式复杂性, 得到了与原有内点法类似的复杂度估计.本文在法锥条件下分析非凸规划问题组合同伦算法的复杂性.

考虑如下非凸规划问题:

记M={1,2,…,m}, 可行集合Ω={x∈n|g(x)≤0}, 严格可行集Ω0={x∈n|g(x)<0},Ω的边界集∂Ω=ΩΩ0,I(x)={i∈M|gi(x)=0}.

假设条件:

(H1)f,gi(i∈M)至少三次连续可微(在Θ上);

(H2)Ω0非空,Ω有界连通;

(H3) ∀x∈∂Ω, {gi(x)|i∈I(x)}正独立;

(H4)Ω满足法锥条件： ∀x∈∂Ω,

记同伦方程中的第二个方程为

引理1对任给的a,b∈1和μ>0, 若记Φμ(a,b)=-μln(e-a/μ+e-b/μ), 则有

引理2由式(1)和式(2)显然有

定理1序列{xk},{y(k)}有界.

证明： 情形1)μ=1.将式(1)改写为

即-ln(e-yi+e-gi(x0))=0,yi=-ln(1-e-gi(x0))>0,i∈M解唯一.

情形2)μ=0.此时式(1)变为

由式(4)有

将式(3)改写为

这与(H3)矛盾.故{y(k)}有界.

证明： 利用一维流形分类定理可证.

算法1

初始化: 设μ0>0,β>0.给定ω=(x,y), (x0,y0)∈n+m, 使得(x0,y0)∈N(β,μ0), 选取δi∈(0,1],αi∈(0,1],i=1,2.取

步骤:

1) 计算Newton方向, 设Δωk=(Δxk,Δyk)是如下方程组的解：

H(ωk,μk)+ωH(ωk,μk)TΔωk=0;

2) 计算迭代点, 如果‖H(ωk,μk)‖∞=0, 则取ωk+1=ωk, 即(xk+1,yk+1)=(xk,yk); 否则, 设λk是使

‖H(ωk+λkΔωk,μk)‖∞≤(1-δ1λk)‖H(ωk,μk)‖∞

(xk+1,yk+1)=(xk,yk)+λk((Δxk,Δyk));

引理3若假设(H1),(H2)成立, 则∃C>0(C为常数), 对∀ω∈Θ,

证明: 利用Taylor展开式即得.

假设条件：

(H5) 对∀ω∈Θ,ωH(ω,μ)可逆, 且‖ωH(ω,μ)-T‖∞≤k.

定理3设0≤λ≤1, Δω是方程组

的解, 且

‖H(ω,μ)‖∞≤βμH(ω,μ)+ωH(ω,μ)TΔω=0,

则

‖H(ω+λΔω,μ)‖∞≤(1-δ1λ)‖H(ω,μ)‖∞.

证明: 由式(8)及

有

证明： 由

有

综上, 本文在法锥条件下, 通过假设可行域在整个大的邻域内有界, 考虑用一个大球(凸集)把非凸区域罩上的思想, 避免了在求解非凸规划问题时算法有些迭代点跳出不在可行域内的情形, 并证明了相应算法具有多项式复杂性.

[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]周俊萍, 姜蕴晖, 殷明浩.最坏情况下X2SAT问题的上界 [J].计算机研究与发展, 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—), 女, 汉族, 博士研究生, 从事应用数学的研究, E-mail: 1084258210@qq.com.通信作者： 薛冬梅(1980—), 女, 汉族, 硕士, 讲师, 从事应用数学的研究, E-mial: boots119@163.com.

吉林省自然科学基金(批准号： 201215128).

O224

A

1671-5489(2014)06-1203-04

10.13413/j.cnki.jdxblxb.2014.06.18

赵立芹)