一种关于序列二次规划和lp罚函数的推论与证明

苗　晴,唐　颂，凌永权

(1.广东工业大学 信息工程学院，广东 广州 510006；2.佛山科学技术学院 数学与大数据学院，广东 佛山 528000; 3.南开大学 数学学院,天津 300071)



一种关于序列二次规划和lp罚函数的推论与证明

苗晴1,2,唐颂3，凌永权1

(1.广东工业大学 信息工程学院，广东 广州 510006；2.佛山科学技术学院 数学与大数据学院，广东 佛山 528000; 3.南开大学 数学学院,天津 300071)

针对一般的含有不等式和等式约束的非线性优化问题，给出了一个关于序列二次规划和lp罚函数的推论与证明.推导了当取相应的二次规划子问题的解作为搜索方向时，则lp罚函数沿该搜索方向的方向导数满足一定的不等式条件；同时通过确定罚参数的取值范围，证明了该搜索方向是lp罚函数在原问题处的下降方向.

非线性约束优化； 序列二次规划； 罚函数； 方向导数

最优化理论与方法是一门应用性很强的学科，在国防经济、工农业生产、交通运输、工程设计和金融贸易等领域有着广泛的应用.非线性约束优化是最优化方法中重要的组成部分，它的一般形式可表述为[1-3]

(1)

常见的求解非线性约束优化问题的方法有Lagrange乘子法[4]、罚函数法[5]和序列二次规划方法[6]等.其中序列二次规划方法(SQP方法)是一类重要的求解非线性约束优化问题的方法，它是在Wilson-Han-Powell(WHP)方法的基础上发展的[1].随后SQP方法引起了许多学者的极大兴趣，得到了进一步的发展并取得大量的研究成果，该类算法的研究也一直是非线性领域的一个热点[7-16].

在非线性约束优化中，WHP方法把求解上述的非线性约束优化问题转化为相应的二次规划子问题，用l1精确罚函数作为效益函数来确定步长，并通过对罚函数中参数的选取及二次规划目标函数矩阵的修正，建立了一个快速有效的算法[1,5].算法中证明了当罚参数满足一定条件时，用二次规划子问题的解作为原问题变量在迭代过程中的搜索方向，则它是该l1罚函数的下降方向.本文受WHP方法的启发，在基于l1精确罚函数的SQP方法的基础上，把l1罚函数给予推广，构造了lp罚函数作为效益函数(这里的p满足p>1)，并给出关于SQP算法中lp罚函数的相关的推论和严格证明.

1　SQP算法的l1精确罚函数

(2)

记d(k)为子问题(2)的解，则SQP方法是用d(k)作为搜索方向，记λ(k+1)为问题(2)的Lagrange乘子，故由KKT条件，得到：

(3)

(4)

▽hj(x(k))Td(k)+hj(x(k))=0,j∈J.

(5)

▽gi(x(k))Td(k)+gi(x(k))≥0,i∈I.

(6)

记l1罚函数

φ1(x,μ)=f(x)+

(7)

同时记罚函数φ1(x(k),μ)沿d(k)方向的方向导数为D(φ1(x(k),μ);d(k))，则它满足

D(φ1(x(k),μ);d(k))≤-d(k) TBkd(k)-

(8)

2　SQP算法的lp罚函数

自从基于l1罚函数的SQP方法提出以来，随着算法自身理论的不断完善，它已成为求解中小规模的约束优化问题中最受欢迎的方法之一.本文在基于l1精确罚函数的基础上，把SQP算法中的l1罚函数给予推广，构造了SQP算法的lp罚函数作为效益函数(这里的p满足p>1即可).在lp罚函数中得出，若采用相应的二次规划子问题的解作为搜索方向时，则罚函数沿该搜索方向的方向导数满足一定的条件；当lp罚函数的参数取值范围确定时，该搜索方向是lp罚函数在原问题处的下降方向.推导与证明如下：

设(d(k),λ(k+1))是子问题(2)的解，记lp罚函数(p>1 )为

(9)

则可以得到罚函数φp(x(k),μ)沿d(k)方向的方向导数满足

D(φp(x(k),μ);d(k))≤-d(k) TBkd(k)-

(10)

证明记罚函数φp(x(k),μ)沿d(k)方向的方向导数为D(φp(x(k),μ);d(k))，则得

D(φp(x(k),μ);d(k))=

(11)

由KKT条件(3)，可得到

▽f(x(k))Td(k)=-d(k) TBkd(k)+

(12)

又由KKT条件(4)和(5)，则式(12)即可化为

▽f(x(k))Td(k)=-d(k) TBkd(k)-

(13)

对于∀t∈(0,δ),0<δ<1，i∈I，由中值定理得

(14)

(15)

所以可得

(16)

同理，对于∀t∈(0,δ),0<δ<1，j∈J，由中值定理得

hj(x(k)+td(k))=hj(x(k))+t▽hj(x(k))Td(k)+o(t)=hj(x(k))-thj(x(k))+thj(x(k))+t▽hj(x(k))Td(k)+o(t)=(1-t)hj(x(k))+t(hj(x(k))+▽hj(x(k))Td(k))+o(t)=(1-t)hj(x(k))+o(t).

(17)

所以可得

(18)

由式(16)和(18)得

(19)

从而，由式(11)得，方向导数

D(φp(x(k),μ);d(k))=▽f(x(k))Td(k)+

(20)

再由式(13)，可得

D(φp(x(k),μ);d(k))≤-d(k) TBkd(k)-

即证不等式(10)成立.

(21)

(22)

(23)

因此，由(21)式可得

(24)

从而，方向导数

D(φp(x(k),μ);d(k))≤-d(k) TBkd(k)-

(25)

所以，若d(k) TBkd(k)>0，且当μ≥‖λ(k+1)‖q时，有D(φp(x(k),μ);d(k))<0，即证d(k)是lp罚函数在x(k)处的下降方向.

3　结束语

本文针对一般的含有不等式和等式约束的非线性优化问题，在Wilson-Han-Powell方法的基础上，结合SQP算法和罚函数的思想，把SQP方法中的l1罚函数给予推广，构造了lp罚函数作为效益函数.严谨推导了若取相应的二次规划子问题的解d(k)作为搜索方向时，则lp罚函数沿该搜索方向的方向导数满足一定的不等式条件；同时通过对lp罚函数中罚参数μ的选取范围的确定，严格证明了该搜索方向是对应的lp罚函数在原问题x(k)处的下降方向.

[1] 袁亚湘,孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社,1997.

[2] 孙文瑜, 徐成贤, 朱德通. 最优化方法[M]. 2版. 北京: 高等教育出版社,2010.

[3] 李董辉, 童小娇, 万中. 数值最优化算法与理论[M].2版.北京: 科学出版社,2010.

[4]DIPILLOG,GRIPPOL.AnewaugmentedLagrangianfunctionforinequalityconstraintsinnonlinearprogrammingproblems[J]．JournalofOptimizationTheoryandApplications, 1982, 36(4):495-519．

[5]HANSP,MANGASARIANOL.Exactpenaltyfunctionsinnonlinearprogramming[J].MathematicalProgramming, 1979, 17(1): 251-269.

[6]POWELLMJD,YUANY.Arecursivequadraticprogrammingalgorithmthatusesdifferentiableexactpenaltyfunctions[J].MathematicalProgramming, 1986, 35(3): 265-278.

[7]HANSP.Agloballyconvergentmethodfornonlinearprogramming[J].JournalofOptimizationTheoryandApplications, 1977, 22(3): 297-309.

[8]PANTOJAJFADO,MAYNEDQ.Exactpenaltyfunctionalgorithmwithsimpleupdatingofthepenaltyparameter[J].JournalofOptimizationTheoryandApplications, 1991, 69(3): 441-467.

[9]FLETCHERR,LEYFFERS.Nonlinearprogrammingwithoutapenaltyfunction[J].MathematicalProgramming, 2002, 91(2): 239-269.

[10]GILLPE,MURRAYW,SAUNDERSMA.SNOPT:AnSQPalgorithmforlarge-scaleconstrainedoptimization[J].SIAMJournalonOptimization, 2002, 12(4): 979-1006.

[11]JIANJB.Newsequentialquadratically-constrainedquadraticprogrammingmethodoffeasibledirectionsanditsconvergencerate[J].JournalofOptimizationTheoryandApplications, 2006, 129(1): 109-130.

[12] JIN Z, WANG Y Q. A simple feasible SQP method for inequality constrained optimization with global and superlinear convergence[J]. Journal of Computational and Applied Mathematics, 2010, 233(11): 3060-3073.

[13] TANG C M, JIAN J B, LI G Y. A working set SQCQP algorithm with simple nonmonotone penalty parameters[J]. Journal of Computational and Applied Mathematics, 2011, 236(6): 1382-1398.

[14] JIAN J B, Li J, ZHENG H Y, LI J L. A superlinearly convergent norm-relaxed method of quasi-strongly sub-feasible direction for inequality constrained minimax problems[J]. Applied Mathematics and Computation, 2014, 226: 673-690.

[15] JIAN J B, CHEN Q F, HUANG Z W. A superlinearly convergent SQP method without boundedness assumptions on any of the iterative sequences[J]. Journal of Computational and Applied Mathematics, 2014, 263: 115-128.

[16] JIAN J B, GUO C H, TANG C M, BAI Y Q. A new superlinearly convergent algorithm of combining QP subproblem with system of linear equations for nonlinear optimization[J]. Journal of Computational and Applied Mathematics, 2015, 273: 88-102.

A Corollary and Proof about Sequential Quadratic Programming and lpPenalty Function

Miao Qing1,2， Tang Song3, Ling Bingo Wing-Kuen1

(1. School of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China;2. School of Mathematics and Big Data, Foshan University, Foshan 528000, China;3. School of Mathematical Sciences, Nankai University, Tianjin 300071, China)

For a general nonlinear optimization problem with both inequality and equality constraints, a corollary on the optimization problem with a lppenalty function is studied and proved based on the sequential quadratic programming approach. In particular, the corollary defines the inequality condition for the search direction of the optimization problem. Moreover, it proves that the derived search direction is a descent direction of the penalty function in the original problem by determining the range of penalty parameter.

nonlinearly constrained optimization; sequential quadratic programming; penalty function; directional derivative

2016- 04- 18

国家自然科学基金资助项目(61372173)

苗晴(1982-)，女，讲师，博士研究生，主要研究方向为优化方法与信号处理等.

凌永权(1973-)，男，国家“青年千人计划”入选者，广东工业大学“百人计划”特聘教授，博士生导师，主要研究方向为最优化信号处理与时频分析等.E-mail：yongquanling@gdut.edu.cn

10.3969/j.issn.1007- 7162.2016.05.001

O221.2

A

1007-7162(2016)05- 0001- 04