刘美杏,简金宝

(玉林师范学院,复杂系统优化与大数据处理广西高校重点实验室,广西玉林　537000)



约束优化问题稳定序列二次规划方法研究综述*

刘美杏,简金宝**

(玉林师范学院,复杂系统优化与大数据处理广西高校重点实验室,广西玉林537000)

(Guangxi Colleges and Universities Key Lab of Complex System Optimization and Big Data Processing,Yulin Normal University,Yulin,Guangxi,537000,China)

摘要:稳定序列二次规划(sSQP)方法由于在求解病态或退化约束优化问题获得理论与数值的突破性进展而备受关注,重要成果频繁问世.本文对近期国际上若干重要sSQP方法及其思想进行概述,包括罚函数型sSQP方法,滤子型sSQP方法和非精确恢复(IR)型sSQP方法等,并对约束优化问题sSQP方法的进一步研究进行探索性思考.

关键词：约束优化问题稳定序列二次规划收敛速度

0　引言

稳定序列二次规划(sSQP)方法作为序列二次规划(SQP)方法的重要扩展,致力于考虑子问题模型、假设条件、技术构造、收敛性质(全局收敛或收敛速度)与数值效果等方面的研究.尤其是对相对弱条件下的收敛速度与数值效果.值得注意的是,对于退化约束优化问题,当对应原始解的拉格朗日乘子不唯一时,快速收敛性的实现难度极大.自1998年,Wright[1]首次提出求解退化不等式约束优化的sSQP方法以来,以 Wright,Hager,Izmailov,Fernndez,Solodov,Gill及Robinson等为代表的sSQP方法及理论研究发展迅速,取得系列成果.文献[1]的方法在每次迭代时需求解一个目标函数二次的极大极小问题,可等价转化为原始对偶空间上的稳定二次规划(QP)问题。该作者在二阶充分最优性条件(SOSC)、Mangasarian-Fromovitz约束规格(MFCQ)和严格互补等条件下,证明了sSQP方法的局部二次收敛性.文献[2]进一步改进文献[1]的sSQP方法,在SOSC和MFCQ等较弱的条件下,证明算法具备局部二次收敛性.Hager[3]对收敛性假设条件进行研究,仅在SOSC条件下获得文献[1]中算法的局部收敛性,并提出用一对不等式约束来表示等式约束,从而可将方法推广到一般约束优化问题.相比较,传统SQP方法对乘子唯一性有着较苛刻的要求,只能依靠严格MFCQ条件来保证.特别地,在等式约束情形下,迫使线性无关约束规格(LICQ)成立[4].文献[5]将sSQP方法推广到求解含等式与不等式约束的变分问题,当初始点充分靠近原始对偶稳定点时,仅需SOSC假设条件,实现了算法的超线性收敛性.对于等式约束优化问题,文献[6]在非临界乘子的条件下建立了超线性收敛的sSQP方法.文献[7]基于线性方程组,在无需LICQ和严格互补等较强的假设条件下,提出一个二次收敛的牛顿型sSQP方法,并给出了该方法超线性收敛的重要定理.文献[8]将拟牛顿型sSQP方法拓广到变分不等式问题,通过对Bregman距离极小化来更新矩阵信息,这样仅需要SOSC便可证明算法的超线性收敛性.

上述文献主要聚焦在最优解的局部范围内构造有效算法,并研究不同假设条件对其收敛速度的影响,建立了一批局部超线性收敛或二次收敛的sSQP方法.这些文献都侧重于局部收敛速度的分析,对算法全局优化策略(全局收敛性质)未做深入研究.而此问题正是实际应用和优化学者们希冀解决的问题,也是衡量最优化算法有效性的重要指标之一.近年来，尽管国内外不少学者对全局化sSQP方法潜心研究,但成果有限.本文主要介绍如下几类的全局sSQP算法:罚函数型sSQP方法[9-12]、滤子型sSQP方法[13]和IR型sSQP方法[14],并对约束优化问题sSQP方法的进一步研究进行探索性思考.

1　函数型sSQP方法

当前,对sSQP方法全局化策略的研究仍是一项极其具有挑战性的工作,其中约束优化sSQP方法全局化时罚函数的选取极其困难,这对于最优性或下降性影响甚大.Gill等[9]引入原始对偶广义增广拉格朗日(AL)函数,提出了一个求解等式约束加简单界约束优化问题的全局收敛sSQP方法.Izmailov等[11]充分利用AL方法的鲁棒性,在没有任何积极约束识别策略下构造了一个sSQP方法,并证明了算法的全局收敛性和局部收敛速度.随后,他们又在文献[12]中以原始对偶精确罚函数[15]为效益函数,提出了一个求解等式约束优化问题的sSQP方法,并分析了算法的全局收敛性和超线性收敛速度.下面参考文献[12],介绍一个具体的罚函数型sSQP算法.

考虑等式约束优化问题:

min f(x)

s.t. h(x)=0,

(1)

其中f(x):Rn→R,h(x)=(h1(x),…,hl(x))T:Rn→Rl至少是二阶可微函数.令问题(1)的Lagrange函数为

(2)

(3)

进而,定义函数Φ:Rn×Rl→ Rn×Rl,

(4)

对一个给定的原始对偶迭代点(x,λ)∈Rn×Rl及稳定参数σ>0,考虑如下原始对偶空间上的sSQP子问题,并产生sSQP方向(ξ,η)，

s.t. h(x)+h′(x)ξ-ση=0,

(5)

基于上述sSQP方向(搜索方向),文献[12]采用如下原始对偶效益函数[15]φc1,c2:Rn×Rl→ R,

(6)

此处选取适当罚参数c1>0,c2>0,可以保证由子问题(5)产生的sSQP方向是φc1,c2(x,λ)的下降方向.

由文献[16]和文献[17]知,原始对偶效益函数(6)是一个精确罚函数.即如果c2>0充分小,c1>0充分大,则φc1,c2(x,λ)任意稳定点都是问题(1)的稳定点;反之,如果最优性系统(3)的原始对偶解(x,λ)满足LICQ和SOSC等条件,则它必是罚函数φc1,c2(x,λ)的严格局部极小解.

(7)

算法1(文献[12]中sSQP算法)

步骤1由(4)式计算ΦkΦ(xk,λk),若Φk=0,终止.

步骤3(i)如果

(8)

则进入步骤5.

(ii)如果

‖h(xk)‖≥ψ1(σk)

(9)

且

(10)

(iii)如果

(11)

步骤5计算αk=θj,此处j为满足不等式

φc1,c2((xk,λk)+θjdk)≤φc1,c2(xk,λk)+

(12)

的最小非负整数.

步骤6令(xk+1,λk+1)=(xk,λk)+αkdk,k∶=

k+1,返回步骤1.

在算法1的迭代过程中,常量值C1,C2的设置对该算法的执行有着重要的防御作用.一般地,这两个数值应该取足够大,方能保证罚参数c1,c2的更新法则不受影响.为了增强算法设计的有效性,当子问题(5)KKT系统无解或步骤3的任一情形都不被执行时,算法1执行步骤4的拟牛顿步防御措施,以修正sSQP方向使之具有下降性,从而算法具有良好的适定性和全局收敛性质.当初始点充分靠近稳定点时,仅需要非临界Lagrangian乘子假设,即可证明算法1的超线性收敛.对退化测试问题,算法1表现出了良好的数值效果.

2　滤子型sSQP方法

滤子法是近20年提出的求解非线性约束优化的一种有效方法.该方法的提出是为了避免在实际问题中设置罚参数.早期滤子法的研究归功于Fletcher和Leyffer[20],随后该方法因良好的数值效果而备受关注,近期代表成果见文献[21-23]等.文献[13]对稳定QP子问题进行修正,并结合双滤子技术[21]提出了求解一般约束优化问题的滤子型sSQP方法.下面对文献[13]中的算法进行分析.

考虑如下一般非线性规划问题:

min f(x)

s.t. hε(x)=0,

hΙ(x)≤0,

(13)

其中,hε(x)=(hi(x),i∈ε),hΙ(x)=(hi(x),i∈Ι),ε= {1,2,·s,l},Ι= {l+1,l+2,·s,m},f:Rn→ R,hi:Rn→ R,i∈ε∪Ι为连续可微函数.定义问题(13)的Lagrangian函数L(x,μ)为

(14)

这里μ=(μ1,μ2,·s,μm)T是Lagrangian乘子向量.

对于当前给定的原始对偶估计迭代点对(xk,μL,k),求解如下修正的稳定QP子问题:

(15)

(16)

问题(15)是一个传统的稳定QP子问题模型.源于算法良好的收敛性质,设计了两种乘子更新方式,其中μL,k保证全局收敛,μk则满足局部收敛的需求.类似地,考虑Bk和σL,k的更新准则.

基于问题(15)的解(dk,Δλk),定义原始对偶搜索方向(dk,Δμk)(此处Δμk=Δλk+μL,k-μk),此方向对算法收敛性理论分析有着重要的作用,其等价于求解如下相容的稳定QP子问题:

Δμ‖2

(17)

在设计非线性规划问题(13)的有效算法时,除需要对目标函数进行极小化,同时要不断降低约束违反度函数:

(18)

然而,搜索方向(dk,Δμk)难以直接达到这样的要求.因此,引入如下辅助目标函数Φ(x,μ)和松弛约束违反度函数 p(x,μ):

(19)

(20)

进而引进双滤子技术(基于文献[21],但有所改进),包括“全局滤子”和“局部滤子”.前者致力于算法收敛于KKT点或稳定点,后者以实现其局部收敛速度.对于第k次迭代,“全局滤子”和“局部滤子”分别记为Fgk,Flk.

(21)

(22)

此处γ1,γ2∈(0,1).

(23)

(24)

此处γ3>0是一个常数.

对于问题(13)及当前迭代点对(xk,μk),求解稳定QP子问题(17)得到搜素方向(dk,Δμk),并沿着此方向和步长α,分别定义函数Φ的实际下降量和线性预测下降量:

ΔΦk(α)=Φ(xk,μk)-Φ(xk+αdk,μk+αΔμk),

(25)

此外,文献[13]结合“全局滤子”接受条件,进一步利用回溯技术选择了恰当的步长αk,判断条件和步长下界.

开关条件:

(26)

充分下降条件:

(27)

(28)

(29)

其中,

(30)

(31)

(32)

其中,μmax>0,β∈(0,1)是两个常数.

下面给出求解问题(13)的滤子型sSQP算法.

算法2(文献[13]中sSQP算法之外循环)

步骤1如果(xk,μk)是问题(13)的KKT点或不可行稳定点,则终止.

算法3(算法2之内循环)

步骤3如果开关条件(26)不成立或充分下降条件(27)成立,则终止.否则令α=r α,返回步骤1.

利用双滤子技术,由算法2产生的所有迭代点均能被滤子接受(全局滤子或局部滤子),这对整个算法的收敛性质分析起到至关重要的作用.在理论上,不需要任何约束规格,即可证明:滤子型sSQP算法2不仅具有全局收敛性(存在收敛子列或收敛于KKT点,或收敛于不可行稳定点),而且在SOSC下,算法达到超线性收敛速度.

3　IR型sSQP方法

sSQP方法的研究最早可以追溯到20世纪末,虽然在适当的假设条件或技术下早期的研究成果实现了算法快速的收敛速度,但在理论上能实现全局收敛的成果较少.滤子型sSQP方法需储存滤子信息,会造成存储量大,而且当迭代点远离可行域,或者在迭代过程中当试探步长比既定下界要小时,为寻找一个能被全局滤子接受的新迭代点,需要执行可行性恢复阶段,这无疑增加算法计算成本,从而影响数值效果.然而,IR技术[24-27]可以减少可行性恢复阶段的复杂性,对sSQP算法的理论分析有着重要的作用.文献[14]提出了求解含等式且变量有界约束优化的IR型sSQP方法.下面详细介绍此算法.

考虑问题(1),且满足约束条件x∈Ω={x∈Rn|a≤x≤b},此处a,b∈Rn.定义问题(1)的自然残差σ:Rn×Rl→R，

(33)

其中,PΩ表示在Ω上的正交投影,L∶Rn×Rl→R是Lagrangian函数(2).

对于原始对偶迭代点对(xk,λk),罚参数ρk>0及Qk，其中Qk是问题(1)Lagrangian Hesse的近似,考虑如下拟牛顿型sSQP子问题:

xk‖λ‖2

ξ∈Ω.

(34)

为构造全局收敛算法,引入下面的辅助函数Fk(x,λ),Hk(x,λ):Rn× Rl→ R:

(35)

(36)

选取点Yk(x)=(x,λk+ρkh(x)),易知Hk(Yk(x))=0,∀x∈Rn,且对于Yk∶=Yk(xk),Y∶=(x,λ),sSQP子问题(34)等价于如下QP子问题:

(37)

注意到Hk(Yk)=0.不难发现上述QP子问题(37)对应于优化问题:

s.t.Hk(Y)=0,Y∈Ω×Rl

(38)

的QP近似子问题.通过近似求解问题(37)可获得sSQP方法的局部收敛性质[3,5].

对每次迭代,IR方法包括恢复阶段和极小化阶段.在恢复阶段,给定迭代点Xk,计算恢复点Yk,避免了目标函数值以及可行性恶化.在极小化阶段,基于可行性和最优性构造了一个含罚参数的效益函数,并沿着一阶可行方向进行线搜索.

下面给出IR型sSQP算法的具体步骤.

算法4(文献[14]中sSQP算法)

(39)

步骤2(i)令Xk,0=(xk,0,λk,0)=(xk,λk),θ0∈(0,1),Qk,0为对称正定矩阵,j∶=0.

(ii)计算Yk,j=(xk,j,λk,j+ρkh(xk,j)),求解如下QP子问题,得到最优解Dk,j∈ Rn×Rl.

(40)

如果‖Dk,j‖

(iii)令θj+1∈{2-i:i∈N∪{0}}为满足下面不等式的最大值:

Φk(Yk,j,θj+1)-Φk(Xk,j,θj+1)≤

(41)

此处Φk(X,θ)=θFk(X)+(1-θ)‖Hk(X)‖是效益函数.

(iv)令tj∈{2-i:i∈N∪{0}}为满足下面不等式的最大值:

Φk(Yk,j+tjDk,j,θj+1)-Φk(Xk,j,θj+1)≤

(42)

(v)令Xk,j+1=Yk,j+tjDk,j,选取对称正定矩阵Qk,j+1,令j∶=j+1,返回步骤2(ii).

事实上，基于IR方法的思想,算法4无需实质性地修正sSQP子问题(34)的结构，只需求解子问题(37)得到非精确解，然后巧妙利用类似增广拉格朗日(AL)罚参数更新策略(步骤3),即可获得算法的全局收敛性质.在严格MFCO和SOSC等条件下,可保证罚参数序列是有界的,进而算法继承了良好的局部收敛速度(线性收敛).

4　展望

本文对求解约束优化问题的若干sSQP方法的思想及算法作了一个较详细的概述,主要介绍了早期sSQP方法的局部收敛成果;近年来实现了全局收敛的罚函数型sSQP方法、滤子型sSQP方法和非精确恢复(IR)型sSQP方法.对sSQP方法还有如下一些问题值得思考和研究.

①如何修正原始对偶罚函数型sSQP算法,在适当的假设条件下,将方法拓展到一般约束优化问题,并制成软件包使之得到广泛应用;

②现有的滤子型sSQP算法考虑内点法求解一个与传统QP子问题相当的修正稳定QP子问题,无疑会在严格内点的选择和计算上遇到困难;加之滤子技术需要进入可行性恢复阶段,也会增加计算成本.因此,如何改进算法以减少计算量,有待进一步探讨;

③目前基于IR技术构造sSQP方法时,需要严格MFCQ和SOSC等条件以实现算法线性收敛,没有继承传统sSQP方法优点(具有快速收敛速度的鲁棒性),如何修正罚参数以更新技术等,建立超线性收敛的IR型sSQP方法值得进一步深入研究;

④求解大规模稀梳优化与工程优化 (如庞杂的电气工程中的潮流问题、机组合问题)的高效的sSQP方法有必要进一步探索.

参考文献:

[1]WRIGHT S J.Superlinear convergence of a stabilized SQP method to a degenerate solution[J].Computational Optimization and Applications,1998,11(3):253-275.

[2]WRIGHT S J.Modifying SQP for degenerate problems[J].SIAM Journal on Optimization,2002,13(2):470-497.

[3]HAGER W W.Stabilized sequential quadratic programming[J].Computational Optimization and Applications,1999,12(1/2/3):253-273.

[4]IZMAILOV A F,SOLODOV M V.Newton-Type Methods for Optimization and Variational Problems:Springer Series in Operations Research and Financial Engineering[M].Switzerland:Springer International Publishing,2014.

[6]IZMAILOV A F,SOLODOV M V.Stabilized SQP revisited[J].Mathematical Programming,2012,133(1/2):93-120.

[7]LI D H,QI L.A Stabilized SQP Method via Linear Equations[R].New South Wales:Mathematics Department,University of New South Wales,2000.

[9]GILL P E,ROBINSON D P.A globally convergent stabilized SQP method[J].SIAM Journal on Optimization,2013,23(4):1983-2010.

[10]GILL P E,KUNGURTSEV V,ROBINSON D P.A Globally Convergent Stabilized SQP Method:Superlinear Convergence[R].UCSD Center for Computational Mathematics Technical Report CCoM-13-4,2014.

[11]IZMAILOV A F,SOLODOV M V,USKOV E I.Combining stabilized SQP with the augmented Lagrangian algorithm[J].Computational Optimization and Applications,2015,62(2):405-429.

[12]IZMAILOV A F,SOLODOV M V,USKOV E I.Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function[J].Journal of Optimization Theory and Applications,2016,169(1):148-178.

[13]SHEN C G,ZHANG L H,LIU W.A stabilized filter SQP algorithm for nonlinear programming[J].Journal of Global Optimization,2016,65(4):677-708.

[15]DI PILLO G,GRIPPO L.A new class of augmented Lagrangians in nonlinear programming[J].SIAM Journal on Control and Optimization,1979,17(5):618-628.

[16]BERTSEKAS D P.Constrained Optimization and Lagrange Multiplier Methods[M].New York:Academic Press,1982.

[17]BERTSEKAS D P.Enlarging the region of convergence of Newton’s method for constrained optimization[J].Journal of Optimization Theory and Applications,1982,36(2):221-252.

[18]IZMAILOV A F,SOLODOV M V.On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions[J].Mathematical Programming,2009,117(1/2):271-304.

[19]IZMAILOV A F,SOLODOV M V.Critical Lagrange multipliers:What we currently know about them,how they spoil our lives,and what we can do about it[J].TOP,2015,23(1):1-26.

[20]FLETCHER R,LEYFFER S.Nonlinear programming without a penalty function[J].Mathematical Programming,2002,91(2):239-269.

[21]SHEN C G,LEYFFER S,FLETCHER R.A nonmonotone filter method for nonlinear optimization[J].Computational Optimization and Applications,2012,52(3):583-607.

[22]GOULD N I M,LOH Y,ROBINSON D P.A filter method with unified step computation for nonlinear optimization[J].SIAM Journal on Optimization,2014,24(1):175-209.

[23]GOULD N I M,LOH Y,ROBINSON D P.Anonmon- otone filter SQP method:Local convergence and numerical results[J].SIAM Journal on Optimization,2015,25(3):1885-1911.

[26]BIRGIN E G,MARTNEZ J M.Local convergence of an inexact-restoration method and numerical experiments[J].Journal of Optimization Theory and Applications,2005,127(2):229-247.

[27]FISCHER A,FRIEDLANDER A.A new line search inexact restoration approach for nonlinear programming[J].Computational Optimization and Applications,2010,46(2):333-346.

(责任编辑：尹闯)

An Overview of the Researches on Stabilized Sequential Quadratic Programming Methods for Constrained Optimization Problems

LIU Meixing,JIAN Jinbao

Key words：constrained optimization problems,stabilized sequential quadratic programming,convergence rate

Abstract：The stabilized sequential quadratic programming (sSQP) methods attract great attention with respect to the theoretical and numerical breakthrough for solving ill-posed or degenerate constrained optimization problems,and many important references about sSQP methods were published.This paper gives an overview on some important sSQP methods,which mainly include penalty function type sSQP methods,filter type sSQP methods and inexact restoration (IR) type sSQP methods,and a few exploratory considerations for further study on sSQP methods are given.

收稿日期：2016-07-01

作者简介：刘美杏(1987-),女，硕士，主要从事最优化理论与算法研究。

中图分类号:O221.2

文献标识码：A

文章编号：1005-9164(2016)05-0385-07

修回日期：2016-08-27

*国家自然科学基金项目(11271086),广西自然科学基金项目(2014GXNSFFA118001),广西高校科研项目(ZD201407)和复杂系统优化与大数据重点实验室开放基金项目(2015CSOBDP0203)资助。

**通信作者:简金宝(1964-),男,教授,博士,博士生导师,主要从事最优化理论与算法及应用研究,E-mail:jianjb@gxu.edu.cn。

广西科学Guangxi Sciences 2016,23(5):385～391

网络优先数字出版时间：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.006

网络优先数字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1520.012.html