序列二次规划算法

1.Legendre PolynomialsNamed in honor of Adrien-Marie (1752-1833) the mathematician, not Louis (1752-1797) the politician.1.1. IntroductionA polynomial is a finite sum of terms like a k x k, where k is a positive integer or zero. There are sets of polynomials such that the product of any two different ones, multiplied by a function w(x) called a weight function and integrated over a certain interval, vanishes. Such a set is called a set of orthogonal polynomials. Among other things, this property makes it possible to expand an arbitrary function f(x) as a sum of the polynomials, each multiplied by a coefficient c(k), which is easily and uniquely determined by integration. A Fourier series is similar, but the orthogonal functions are not polynomials. These functions can also be used to specify basis states in quantum mechanics, which must be orthogonal.1.2. Legendre Polynomials DenifitionThe Legendre polynomials P n(x), n = 0, 1, 2 ... are orthogonal on the interval from -1 to +1, which is expressed by the integralThe Kronecker delta is zero if n ≠ m, and unity if n = m. In most applications, x = cos θ, and θ varies from 0 to π. In this case, dx = sin θ dθ, of course. The Legendre polynomials are a special case of the more general Jacobi polynomials P(α,β)n(x) orthogonal on (-1,1). By a suitable change of variable, the range can be changed from (-1,1) to an arbitrary (a,b). The weight function w(x) of the Legendre polynomials is unity, and this is what distinguishes them from the others and determines them.1.3. ApplicationsThe Lengendre polynomials are very clearly motivated by a problem that often appears. For example, suppose we have an electric charge q at point Q in the figure at the left, one of a group whose positions are referred to an origin at O,and we desire the potential at some point P. The distance PO is taken asunity for convenience; simply multiply all distances by the actualdistance PO in any particular case. The potential due to this charge is q/R.We ca n find R as a function of r and θ by the Law of Cosines: R2 = 1 + r2- 2r cos θ = 1 - 2rx + r2, where x = cos θ. Now we expand 1/R in powersof r, finding 1/R = Σ P n(x)r n. The function 1/R is called the generatingfunction of the Legendre polynomials, and can be used to investigatetheir properties. Generating functions are available for most orthogonal polynomials, but only in the Legendre case does the generating function have a clear and simple meaning.If we let x = 1, we find that P n(1) = 1, and P n(-1) = (-1)n. By taking partialderivatives of 1/R with respect to x and r, and then considering the coefficients of individual powers of r, we can find a number of relations between the polynomials and their derivatives. These can be manipulated to find the recursion relation, (n + 1) P n+1(x) = (2n + 1)x P n(x) - n P n-1(x), and the differential equation satisfied by the polynomials, (1 - x2) P"n(x) -2x P'n(x) + n(n + 1) P n(x) = 0. The recurrence relation allows us to find all the polynomials, since it is easy to find that P0(x) = 1, P1(x) = x directly from the generating function, and this starts us off. The differential equation allows us to apply the polynomials to problems arising in mathematics and physics, among which is the important problem of the solution of Laplace's equation and spherical harmonics.The recurrence relation shows that the coefficient A n of the highest power of x satisfies the relation A n+1 = (2k + 1)/(k + 1) A n, and so from the known coefficients for n = 0, 1 we can find that the coefficient of the highest power of x in P n is 1.3.5...(2n-1)/n!.The polynomials can also be found by solving the differential equation by determining the coefficients of a power series substituted in the equation. This method was often used in quantum mechanics texts (see Reference 3), since the students were not usually acquainted with the mathematics of orthogonal polynomials. This method does not allow one to investigate the properties of the polynomials in any detail, however, yielding only the individual polynomials themselves.Consider the polynomials G n(x) = d n/dx n(x2- 1)n. The quantity to be differentiated is indeed a polynomial, of degree 2n, and consisting of only even powers. When differentiated n times, it becomes a polynomial of order n consisting of either all odd or all even powers of x, as n is odd or even. The coefficient of the highest power of x is 2n(2n-1)(2n-2)...(n+1), and the first two polynomials are 1 and 2x. If G(x) is substituted in the recurrence relation for the Legendre polynomials, it is found to satisfy it. If we divide G(x) by the constant 2n n!, then the first two polynomials are 1 and x. Therefore, P n(x) = (1/2n n!) d n/dx n(x2- 1)n. This is called Rodrigues's formula; similar formulas exist for other orthogonal polynomials.The great advantage of Rodrigues' formula is its form as an nth derivative. This means that in an integral, it can be used repeatedly in an integration by parts to evaluate the integral. The orthogonality of the Legendre polynomials follows very quickly when Rodrigues' formula is used. There is a Rodrigues' formula for many, but not all, orthogonal polynomials. It can be used to find the recurrence relation, the differential equation, and many other properties.For finding solutions to Laplace's equation in spherical coordinates, the Legendre polynomials are sufficient so long as the problem is axially symmetric, in which there is no φ-dependence. The more general problem requires the introduction of related functions called the associated Legendre functions that are actually built up from Jacobi polynomials, and can also be expressed in terms of derivatives of the Legendre polynomials. Physics texts generally approached the problem from first principles, never mentioning Jacobi polynomials, and thereby losing valuable insight.The Jacobi polynomials P(α,β)n(x) are orthogonal on (-1,1) with weight function w(x) = (1 - x)α(1 + x)β. Their Rodrigues' formula is P(α,β)n(x) = [(-1)n/2n n!] (1 - x)-α(1 +x)-β d n/dx n (1 - x)α+n(1 + x)β+n. The ordinary Legendre polynomial P n(x) = P(0,0)n(x). They satisfy the differential equation (1 - x2)P"(α,β)n+ [β - α - (α + β + 2)x] P'(α,β)n + n(α + β + n + 1) P(α,β)n = 0.In solving Laplace's equation by the method of separation of variables, one obtains for the θ dependence T(x), x = cos θ, the differential equationd/dx[(1 - x2)dT/dx] = [l(l+1) - m2/(1 - x2]T = 0 The substitution T(x) = (1 - x2)m/2y(x) now gives the equation(1-x2)y" - 2(m + 1)xy' + [l(l+1) - m(m+1)]y = 0, which we recognize as satisfied by the Jacobi polynomial P(m,m)l-m(x). Hence, T(x) = (1 - x2)m/2y(x) P(m,m)l-m(x). This is the associated Legendre function, often denoted P m l(x) in physics texts (e.g., Reference 4), and defined there as (-1)m(1 - x2)m/2 d m/dx m P l. The subscript is no longer the degree of the polynomial.All the above is for a positive m. Since the equation contains m2, the solution for negative m is essentially the same, except perhaps for a multiplicative factor. This is of little consequence for the traditional applications of spherical harmonics, but is critical for quantum mechanics, where relative phases matter. The choice in physics is that P-m l(x) = (-1)m[(l - m)!/(l + m)!] P m l(x), where m is always positive on the right. If you work the functions out explicitly, you will find that the functions for +m and -m are essentially the same, as might be expected, and differ at most by a factor of -1.For the same m, P m l(x) and P m l'(x) are orthogonal, and the integral of the square of P m l(x) is the same as for P l(x), multiplied by (l - m)!/(l + m)!. The functions are not orthogonal for different values of m; orthogonality of the spherical harmonics in this case depends on the φ functions.1.4. References1.M. Abramowitz and I. Stegun, Handbook of MathematicalFunctions (Washington, D.C.: National Bureau of Standards, AppliedMathematics Series 55, June 1964). Chapter 22.2. D. Jackson, Fourier Series and Orthogonal Functions(Mathematical Assoc. of America, Carus Mathematical Monographs No. 6,1941). Chapter X.3.L. Pauling and E. B. Wilson, Introduction to Quantum Mechanics(New York: McGraw-Hill, 1935). Chapter V.4.J. D. Jackson, Classical Electrodynamics, 2nd . ed. (New York:McGraw-Hill, 1975), Chapter III.2. Gauss 型积分2.1. Gauss 型求积公式的构造方法(1)求出区间[a,b]上权函数为W(x)的正交多项式pn(x)(2)求出pn(x)的n 个零点x1 , x2 , … xn 即为Gsuss 点.(3)计算积分系数2.2. 几种Gauss 型求积公式2.2.1. Gauss-Legendre 求积公式区间[-1,1]上权函数W(x)=1的Gauss 型求积公式，称为Gauss-Legendre 求积公式，其Gauss 点为Legendre 多项式的零点。

序列二次规划算法流程框图下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。

文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor. I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!1. 初始化：设置算法参数，如最大迭代次数、收敛精度等。

选择初始点$x_0$。

求解双层规划问题的松弛序列二次规划方法
杜梦琪;徐梦薇;段庆松
【期刊名称】《高校应用数学学报（A辑）》
【年(卷),期】2024(39)2
【摘要】考虑一类具有特殊结构的双层规划问题,其下层问题为凸问题.首先通过内点罚方法将下层的约束函数惩罚到目标函数,使得下层问题近似为一系列无约束优化问题.然后使用KKT条件替换无约束的下层问题的最优解集,那么双层规划问题被一系列松弛的单层问题近似.文中设计了一种光滑的序列二次规划算法求解该松弛问题,并证明了当罚因子趋近于0时,该算法生成的迭代点列收敛到双层规划问题的弱稳定点.数值实验验证了算法的可行性.
【总页数】17页(P182-198)
【作者】杜梦琪;徐梦薇;段庆松
【作者单位】河北工业大学理学院;中银金融科技有限公司智能风控中心
【正文语种】中文
【中图分类】O224
【相关文献】
1.一种由滤子松弛化的序列二次规划算法
2.带有二次约束的一般二次规划问题的松弛分枝定界方法
3.凸二次规划松弛方法研究离散加工时间可控排序问题
4.凸二次规划松弛方法研究离散加工时间可控排序问题
5.求解互补问题的一种序列二次规划方法
因版权原因，仅展示原文概要，查看原文内容请购买。

第十五章序列二次规划法第十五章序列二次规划法考察一般非线性约束最优化问题m in ( )( ) 0 , { 1 , 2 , , }s . t.( ) 0 , { 1 , 2 , , }i eei efxc x i mc x i m mEI m(15.0.1)其中 )( )), ((i xfc i E Ix ??都二阶连续可微 .序列二次规划法(Sequential Quadratic Programming，简称SQP)的基本思想是在当前迭代点 kx 处，以问题 (15.1.1)的 Lagrange 函数 ( , )Lx? 在 ( ),kkx ? 处关于变量 x 的 Taylor 二阶展开式作为目标函数，以约束条件 ( )( )i x i E Ic ??在 kx 处的 Taylor 一阶展开式作为约束条件，构造一个二次规划子问题来获得搜索方向 kd ，它可以看作是求解无约束优化问题的牛顿法(或拟牛顿法 )在约束情形下的推广 . 由于 2 ( , )kkxxLx?? 的计算量比较大且不一定正定，因此，我们一般采用拟牛顿法思想构造正定矩阵序列{}kB ，并以kB 代替 2 ( , )kkxxLx?? ，即由二次规划子问题m i n ( ) ( ) 0 ,s .t . 12() ((,) )0T k Tkk k Tik k Tiiid B d dc xd Ecxfxc x icx dIi(15.0.2)来确定下降方向 kd .在序列二次规划法中，一般采用某种精确罚函数来作为评价算法产生的迭代点 kx 趋近原问题 (15.1.1)最优解 x 的程度的价值函数 .§15.1 Lagrange-Newton 法本节考察仅有等式约束的情形m i n ( )s .t . ( ) 0 , {1 , 2 , , }i Efxc x i m??? ? (15.1.1)第十五章序列二次规划法272 最优化理论与方法 [乌力吉 ]其中 (( )), )(i xfc ix E? 均二阶连续可微 . 其 Lagrange 函数为1(( ), ) ) (miiif x cLx x????? ?. (15.1.2)由第九章可知，在一定条件下， x 是问题 (15.1.1)的局部解的必要条件是存在 m满足 K-K-T 条件1( , ) ( ) ( ) ,(, ),) ( mx i iiL x f x c cx xxL?(15.1.3)这里 12( ) , ( ) ,( ) ( , ( ) ) Tmxcc xcx xc ? ?.Lagrange-Newton 法的基本思想是利用牛顿法求解非线性方程组 (15.1.3)来得到原问题(15.1.1)的 K-K-T 点及其乘子 .§15.1.1 非线性方程组的阻尼 Newton 法我们先来讨论求解一般非线性方程组()Gx?0 (15.1.4)的 Newton 法，其中 : nnG 连续可微 .在当前迭代点 kx 处，将向量值函数 ()Gx 以其在 kx 处的 T aylor 一阶展开式近似代替，求解线性方程组) ( )( ()k k k TG x dd G x G x? ? ? ? ? 0， (15.1.5)其中 12( ) ( ( ) ( ) ( ) )k k k knG x G x G x G x? ? ? ? ??，这个方程组又称为 Newton 方程，当()Gx 的 Jacobi 矩阵 ()kTGx? 可逆时，可解得 Newton 方向1( ) )( ()k k T kG x G xd ??? ? . (15.1.6)Newton 方向 kd 是价值函数21211|| ( ) |() |22 ()imixGx G x? ?? ??(15.1.7)在点 kx 处的下降方向，这是因为§ 15.1 Lagrange-Newton 法最优化理论与方法 [乌力吉 ] 2731( ) ( ) ( ) ( ) ( )k k kmikkiix x G x G x G xG?， (15.1.8)由此得( ) ) ( ) ) ( )(( ()2k T k k T k T k k T k kx d G x d G xG x G x x??? ? ?? ? ? ?， (15.1.9)因此，当 kx 不是非线性方程组 (15.1.4)的解时，必有 ( ) 0k T kx d.求解非线性方程组的经典 Newton 法迭代格式为1k k kxx d? ??. (15.1.10)设 x 为 ()Gx?0 的解， ( )Gx? 可逆，则由 ()Gx 连续可微可知，当kx 充分靠近 x 时，)( kGx? 也可逆，且由 Von-Neumann 引理知，存在 0M? ，使得1|| ( ) ||kG x M，于是11 | | | | | | | | ( ) ) ( ) | || | (k k k k k T kx x d x x G x xx Gx??? ? ? ? ? ? ??1| | ( ) ) | | ( )( | | (( | |))k T k k T kG x G x G x x x?? ? ? ???| | ( ) | | ( | | | | | ) | | ( | | )|kkM G x o x x o x x? ? ? ??， (15.1.11)这表明非线性方程组的牛顿法具有局部超线性收敛速率，特别地，当 ()Gx? 在点 x 处局部Lipschitz 连续时，由定理 1.2.1，有1 | | | | (| | ( ) ) ( ) ( ) | |k k k T kx G x GxM x G x x x? ? ? ? ? ??2(|| || )kO x x??， (15.1.12)这时，非线性方程组的 Newton 法具有局部二阶收敛速率 .算法 15.1（非线性方程组的阻尼 Newton 法）步 1：给定初始点 0 nx?? ，参数 (0,1)?? 和 (0,1)?? ，容许误差0?? ，置 0k? ；步 2：如果 ()kx ，则算法结束，输出近似解 kx ；步 3：确定牛顿方向，从牛顿方程( ) ( )k k TG x G x d?? ? 0 (15.1.13)解出 kd ，并令 1?? ；步 4：沿 kd 进行简单后退线搜索，如果第十五章序列二次规划法274 最优化理论与方法 [乌力吉 ]( ) (1 ) ( )k k kx d x? ? ? ? ?? ? ?， (15.1.14)则令 ? ??? ，转步 4，否则令 k ；步 5：令 1k k kkx x d?? ?? ，置 1kk??，转步 2.定理 15.1.1 设 : n nG 连续可微，如果 ()kGx? 对每个 k 都可逆，且存在 0M? ，使得 1()|| ||kG x M总成立，则算法 15.1 产生的点列 {}kx 的任何聚点都是 ()Gx?0 的解 .证设x 是点列{}kx 的一个聚点，则存在无穷指标集1 {1,2, }K ? ? ，满足1limkkKk xx??? ?， (15.1.15)由于算法 15.1 是下降算法，故由数列 {( )}kx? 单调减少可知( ) ( )limk kxx???? ? . (15.1.16)由于 1()|| ||kG x M，故对每个 1k K? ，都有1 0| | | | | | | | | | | | | |( ) ) ||( ( )k k kG x G x GdM x?? ?? ?，(15.1.17)即1{}k kKd ?有界，从而存在无穷指标集 21K K? ，使得2limkkKk dd??? ?，且由 ()Gx 连续可微，有2( ) ( ) | || | l i m | | 0( ) ( ) | |T k T k kkKkddG x G x G x G x???? ? ? ???，即( ) ( )T dG x G x? ? ?. (15.1.18)再由算法 15.1 步 4 可知，1 )( ) ( ) (1 ( )k k k kkkdx x x? ? ? ? ? ?? ??? ?， (15.1.19)( ) (1 ( ))k k kkkdxx? ? ? ? ?? ??， (15.1.20)其中 ? /kk? ? ?? .下面用反证法来证明定理的结论成立 . 假设 x 不是 ()Gx?0 的解，这时 ( ) 0x? ? ，由不等式 (15.1.19)和极限 (15.1.16)，有 lim 0k k??? ?，因此，§ 15.1 Lagrange-Newton 法最优化理论与方法 [乌力吉 ] 275lim? 0kk ??? ? ， (15.1.21)由此得2( ) ( l im 2) ( ) ( ) ( ) ( )? T T Tk kK kkxx x d G x G x xd d? ? ? ???，从而对充分大的 2k K? ，都有3 (1? ?( )2 ) ( )kkdxx? ? ? ???? . (15.1.22) 由于对任意 (0,1)?? ，有22l i m ( ) l i m ? )? (kkkkk K k Kkkx d x x d? ? ? ???? ? ? ?? ? ? ?，故由 ( ) ( ) ( )Tx G x G x?? ? ? 连续以及2limkkKk dd??? ?，有)? ?| ( ) ( ( ) ( |)k k kkkdx x x xd? ? ? ? ? ?? ? ???|? ?| ( ) ( )k k k T k k Tk k k kddx dx d? ? ? ? ? ? ? ?? ? ? ???( ) ? ? ?|( ( ) )k k k k T kk k kdxx dd? ? ? ? ? ? ?? ? ?? ? ?) (|( ? )?k T kkk d d dx? ? ? ?????( || ) ( ( ) || || ||k k k k kk k kdx x dd? ? ? ? ? ? ?? ??????|| ( ) || || || )kkk ddx d? ? ?? ? ? ??2? )( )( ,kok K k? ?? ??， (15.1.23)其中 (0 ,1), (0 ,1)kk对任意 2k K? 成立，故对充分大的 2k K? ，由不等式 (15.1.20) ,(15.1.23)和 (15.1.22)，有( ) ( ) ( )k k k kkk dx x x? ? ? ? ? ?? ? ??( ) ( ) ( )kkxod x? ? ? ?? ? ??1? ? ? ?( ) ( ) ( ) ( )2k k k kx x o x? ? ? ? ? ? ?? ? ??? ?， (15.1.24)即有 ( ) ( )kxx?? ?? ，对不等式两边取极限，得第十五章序列二次规划法276 最优化理论与方法 [乌力吉 ]1) ( ) 0( x，由于 (0,1)?? ，故 ( ) 0x? ? ，但这与假设矛盾，矛盾表明假设不成立 .§15.1.2 等式约束优化问题的 Lagrange-Newton 法在本节，我们回过头来考察非线性方程组 (15.1.3)1()),(().miiif x c xcx(15.1.25)以 () mnAx 来表示约束函数 ()cx的 Jacobi 矩阵，即12 mA x c x c x c x? ? ? ? ??， (15.1.26)并记1(, ()()( ) ( ) ( , )) m ii xifGxcxcxx c x Lx? ??， (15.1.27)则 (,)Gx? 的 Jacobi 矩阵为2 ( ) ( ))( ,(, )Txx Lx AxxxG A ?? ?????? ?????O . (15.1.28)假设 A (A1) 约束函数 ()cx的 Jacobi 矩阵 ()Ax 是行满秩的；(A2) Lagrange 函数的 Hesse 矩阵 2 ( ),xxLx?? 在切平面 { | }nd Ad? ? 0? 上正定，即有2 ( |, ) 0 },{Tnxx L x dd d dd A?? ? ? ?? ? ?0 0?. (15.1.29)定理 15.1.2 如果问题 (15.1.25)满足假设 A，则 ( , )Gx?? 是可逆矩阵 .证设存在向量 nmd 满足2 ) ( )) (,,()(T xxx dAxddAxLxGx ??? ??? ? ? ? ??? ? ??? ?? ??? ?????? 00O，则由2 (), )( Txx xLx d A x d ??? ? ? 0， (15.1.30)§ 15.1 Lagrange-Newton 法最优化理论与方法 [乌力吉 ] 277()xA x d??0 ， (15.1.31)有2 (, ) ( ) ( ) xT T T Tx x x x xd d d A x d ALx xdd??? ??? ? 0，(15.1.32)这样，由等式 (15.1.31)和 (15.1.32)以及假设 (A2)可知 xd?0 ，将其代入方程等式 (15.1.30)，得()TA x d? ?0 ，而由假设 (A1)可知 ()TAx 是列满秩的，故 d??0 ，从而 ( , )Gx?? 是可逆矩阵 .记1( , ) ( , ) ( , )2 Tx G x G x? ? ? ?? .等式约束优化问题的Lagrange-Newton 法就是通过算法15.1 来求解非线性方程组(15.1.14)来得到约束问题(15.1.3)的K-K-T 点及其乘子，具体算法如下：算法 15.2（等式约束优化问题的 Lagrange-Newton 法）步 1：给定初始点 00)(, nmx ? ??? ，参数 (0,1)?? 和 (0,1)?? ，容许误差 0?? ，置 0k? ；步2：如果(),kkx? ? ?? ，则算法结束，输出近似K-K-T 点对( ),kkx ? ；步 3：确定牛顿方向，从牛顿方程2 ( , () ( ) ( )( )())k k k T k k T kxxxkkdAfdAL x x x A xx c xO 0(15.1.33)解出 , )( kkxd d? ，并令 1?? ；步 4：沿 , )( kkxd d? 进行简单后退线搜索，如果( ) ( 1 ) (,, )k k k k k kxx d d x?? ? ? ? ? ? ? ?? ? ? ?，则令 ? ??? ，转步 4，否则令 k ；步 5：令 1kkk kxx x d?? ?? ， 1kkk kd????? ?? ，置 1kk??，转步 2.这个算法的全局收敛性和局部收敛速率可由§15.1.1 中相应结论得到 .注对于包含不等式约束的优化问题第十五章序列二次规划法278 最优化理论与方法 [乌力吉 ]m in ( )( ) 0 , { 1 , 2 , , }s . t.( ) 0 , { 1 , 2 , , }i eei efxc x i mc x i m mI m我们可以考虑引入松弛变量，使其成为仅具有等式约束的优化问题2m in ( )( ) 0 , { 1 , 2 , , }s. t.( ) 0 , { 1 , 2 , , }eii eiefxc x i mc x y i m m m EI具体讨论读者自己完成 .当我们恒取 1k?? 时，算法 15.2 就变成经典 Newton 法，这时有迭代格式11,.kkkxkx x dd从而，牛顿方程 (15.1.33)可以写成2 ) ( )(,()()()k k k T kxxkkL x x xxc dAA xf? ?? ? ? ?? ? ??? ?? ? ? ???? ??O 0， (15.1.34)由此解出 kkxdd? 和 1 kkkd???? ??.另一方面，我们注意到非线性方程组 (15.1.34) 完全可以看成是二次规划问题21m in ( ) (2s . t., ) ()))( (T k k k Txxkkd f xq d d L x ddx cxA(15.1.35)的一阶必要条件，即为问题 (15.1.20)的 K-K-T 条件 .当假设 A 满足时，非线性方程组 (15.1.34)的唯一解 1)(,kkd ?? 就是凸二次规划问题(15.1.35)的最优解及其乘子 .因此，等式约束优化问题的 Lagrange-Newton 法可以理解为每次求解一个二次规划子问题来得到在当前迭代点 kx 处关于变量 x 的下降方向 kkxdd? 以及1k k kx x d? ??的乘子1k?? .这给了我们一个启示，对于约束优化问题可以通过解一系列这样的二次规划子问题来产生收敛于原问题 K-K-T 点及其 Lagrange 乘子的迭代序列 {}kx 和{}k? ，这就是序列二次规划法的思想来源 .§ 15.2 序列二次规划法最优化理论与方法 [乌力吉 ] 279§15.2 序列二次规划法本节考察一般非线性约束最优化问题m in ( )( ) 0 , { 1 , 2 , , }s . t.( ) 0 , { 1 , 2 , , }i eei ec x i mc x i m mEI m(15.2.1)其中 )( )), ((i xfc i E Ix ??都二阶连续可微 .类似于二次规划子问题(15.1.35)，我们构造一般约束问题(15.2.1)的二次规划子问题()) ( )1m in ( 0 , ,) ( ) 0 , ) 2 (s.t . (T k T kk T k iik T k d f x cdq d d Bc x i Ec d c x i Idxx(15.2.2)其中 kB 是 Lagrange 函数的 Hesse 矩阵 2 ,)( kkxxLx?? 的近似 . 二次规划问题 (15.2.2)的 K-K-T 条件为1( ) ( ) ,( ) ( ) 0 , ,( ) ( ) 0 , 0 , ( ) ( ) .( ) 0 , mkkk i iik T kiik T k k T ki i i i i if x c xx x i Ex x x x IBdc d cc d c c d c i 0(15.2.3)定理 15.2.1 如果 kd 是二次规划问题 (15.2.2)的 K-K-T 点， k? 是相应的乘子，则对于 1l?罚函数() 1|( ) ( ) | ( ) ||kcxP x f x? ? ??? ， (15.2.4)有() 110) | | ( ) | | (( () )kk mk T k k k kk i iid cxd P x d B d xd c?， (15.2.5)其中() 1| | ( ) | | | ( ) | | m i n{ 0 , ( ) } |k iii E i Ic x c x c x| ( ) | m a x{ 0 , ( ) }iii E i Ic x c x????? ?? . (15.2.6) 证对任意 , nyz?? ， [0,1]?? ，有第十五章序列二次规划法280 最优化理论与方法 [乌力吉 ]() 11| | [ ( 1 | m i n{ 0 , ( 1 } |) ] | | )nii iy z y z? ? ? ??? ? ???? ?1 )m a x{ 0 , (1 }ini iyz??? ?? ? ??1 [ ( 1 m a x{ 0 , } m a x{ 0 ,) }]niii yz???? ? ? ? ??11) m i n{ 0 , m i n{ 0}} ,(1nniiiiyz??????? ??( ) ( )11) | || ||(| ||1 yz.因此，由函数 ()1| || |y? 的凸性和 K-K-T 条件知， ()Px? 在 kx 处沿方向 kd 的方向导数( ) ( )1100) ( ) | | ( ) | |()( | | | |l i mkk k k kk T kd P x cd x d xfx cd d?( ) ( )11((|| [ ) ) ] || ( ) |) || |l im() k k T k kk T k c x A x d xf x d c( ) ( )11( ) ( | ( ( ) ) ] || ( ) ||| ) || )[k T k k k T k kf x d x Accx d x? ???????11 ()( ) ( ) | |||miTk k k k kk i iBd c x xcd?? ????? ? ? ???????() 11|() | ( ) | | ( )mk T k k k kk i iicxd B d cx??? ?? ? ? ? ?，其中矩阵 1 2) ( ( ) ( ) ( ) )( kk mkkc x c x xx cA ? ? ? ??，从而定理得证 .定理 15.2.2 如果 kd 是二次规划问题 (15.2.2)的 K-K-T 点， k? 是相应的乘子，则当( ) 0k T kkd B d ? 且 || ||k 时， kd 是 1l? 罚函数 (15.2.4)在kx 处的下降方向 .证由于1 ( ) ( ) ) ( ))( (m k k k k k ki i i i i ii E Iiic x c x c x? ? ?? ? ??? ? ? ??? ?() 1| ( ) || | | | | | |m a x{ 0 , ( ) } ( ) | ||k k k k k ki i i ii EI ic x c x c x? ? ?，故当 ( ) 0k T kkd B d ? 且 || ||k 时，由 (15.2.5)知 ()Px? 在 kx处沿方向 kd 的方向导数§ 15.2 序列二次规划法最优化理论与方法 [乌力吉 ] 281)( 0kkP d ddx?，这表明 kd 是 1l? 罚函数 (15.2.4)在 kx 处的下降方向 .下面给出序列二次规划法的具体算法，这个算法是韩世平于 1976 年提出来的， Powell在 1977 年给出修改方案 . 由于 Wilson 早在 1963 年就讨论过Lagrange-Newton 法，因此，下面的算法也称作 Wilson-Han-Powell 算法 .算法 15.3（序列二次规划法）步 1：给定初始点 0 nx?? ，罚因子 0?? ，步长上限 0?? ，初始矩阵 0 nnB ，初始参数 0 0?? ，容许误差 0?? ，置 0k? ；步 2：求解二次规划子问题 (15.2.2)得到下降方向 kd ，如果|| ||kd ?? ，则算法结束，输出近似 K-K-T 点 kx ；步 3：求出步长 [0, ]k ，使得0) m i(( n)k k k kkkP d P x dx?? ??? ? ???? ? ? ?； (15.2.7)步 4：令 1kk kkx x d?? ?? ；步 5：产生矩阵 1kB? 和参数 1 0k?? ? ；步 6：置 1kk??，转步 2.注（ 1）在算法 15.3 中，价值函数 ()Px? 是 1l? 罚函数 (15.2.4)，正数列 {}k? 满足0k k??. (15.2.8)（2）矩阵1kB? 的计算一般是用拟牛顿迭代公式产生，我们希望它是 2 1 1( , )kkxxLx 的近似，因此可取1 1 11( ) ( ) ( ), )( ()mk k k k k k k k ki i iix x f x f x cs xy cx?? ? ??? ? ? ? ? ? ? ? ? ??， (15.2.9)然后利用拟牛顿公式计算1kB? . 由于上述线搜索过程不能保证( )0k T kys ? ，从而不能直接利用 BFGS 方法 . Powell 在 1978 年给出了一种修正策略，即取) 0 . 2 ( )( 1 ), ( ,, ) 0 . 2(,()k k T k k T kk kk k k T k k T kk k k ky s B sBysy y s y s B ss?? ????? ? ?第十五章序列二次规划法282 最优化理论与方法 [乌力吉 ]其中(0 .8 ()( ) )k T kkk k T k k T kks B ssysBs? ? ?，经过这样的修正，我们就可以用 BFGS 方法 .还有一种修正策略是以1 ( ) ( )? 2mk k k kiii c x c xyy ? ?? ?? ?来取代 ky . 这种做法一般能保证 ?( )0k T ks y ? ，如果 ?( )0k T ks y ? ，则可以通过增大 ? 来实现其反号 .定理 15.2.3 设 ()fx和 ( )( )i x i E Ic ??都连续可微，且存在两个常数 0 mM?? ，使得不等式22|| |||| || T km d Bd M dd?? (15.2.10)对一切 k 和 nd?? 都成立 . 如果不等式 || ||k 对一切 k 都成立，则由算法 15.3 产生的点列 {}kx 的任何聚点都是约束优化问题 (15.2.1)的 K-K-T 点 .证设x 是点列{}kx 的任意一个聚点，且存在无穷指标集0 {1, }2,K ? ? ，使得0limkkkK x x?.由定理的条件可知， {}k? 和 {}kB 都有界从而0{}k kK? ?和0{}k k KB ?都有收敛子列，不妨就设00,lim limkkk kKKBB? ???.由于 kd 是二次规划子问题 (15.2.2)的最优解，从而 kd 满足 K-K-T 条件 (15.2.3). 注意到()fx和 ( )( )i x i E Ic ??都连续可微， kB 满足不等式 (15.2.10)，由线性方程组的扰动理论，我们在 (15.2.3)式中令 k?? ，不难得出lim kkKk dd??? ? ， (15.2.11)且 d 满足 K-K-T 条件§ 15.2 序列二次规划法最优化理论与方法 [乌力吉 ] 2831( ) ( ) ,( ) ( ) 0 , , ( ) ( ) 0 , 0 , ( ) ( ) .( ) 0 , miiiTiiTi i iTi i if x c xx x i ExxBdc d cc d c cdx x Ici(15.2.12)如果 d?0 ，则由 K-K-T 条件 (15.2.12)易见，这时 x 是约束优化问题 (15.2.1)的 K-K-T点，定理得证 .下面讨论 d?0 的情形，这时取 [0, ]? ?? ，满足0) m i((n)P x P xdd????????? ? ?.由于 d 满足 K-K-T 条件 (15.2.12)，其中 ? 是 x 的乘子， 0Td Bd? ，|| ||? ??? ，由定理 15.2.2 可知， d 是目标函数 ()Px? 在 x 处的下降方向，从而有)(()P x P xd.记 ) )0((P x P x d??? ??? ?? ，由于kkd x dx ??? ? ? 0,)( kKk ?? ? ，故对充分大的 0k K? ，有() 2 ()kkPPx d x??? ??? ?. (15.2.13)另一方面，由于1 0) m in(( )( )k k k kkkxxP P d P x? ? ??? ? ? ?? ??? ? ? ? ? 对每个 k 成立，故对任意自然数 k 和 m ， 1mk??，有111( ) )(mmkiikPxxP?? ?. (15.2.14)再注意到不等式 (15.2.8)蕴含对充分大的 k 有2iki ???? ??，因此，对充分大的 k ，我们在不等式 (15.2.14)中令 m?? ，得第十五章序列二次规划法284 最优化理论与方法 [乌力吉 ]11( ) )(k iikP xP x?? ?0 (m i n )kk iikPdx??? ??。

第7章约束问题的优化方法第三节二次规划第四节序列二次规划第三节二次规划一、二次规划的基本概念二次规划（Quadratic Programming, QP）是一种特殊的非线性规划问题，目标函数是二次函数，约束是线性函数，如果只含等式约束，则形如（1）为阶对称矩阵，为矩阵，秩为。

如果半正定/正定，则其KKT点就是全局最优。

许多现实问题本身可建模为二次规划，而一些一般规划问题也能近似归结为求解二次规划问题，因此二次规划具有重要的地位。

求解二次规划（QP）问题的算法较多，如：（1）Lagrange方法（2）起作用集方法（3）Lemke方法（4）路径跟踪法二、求解等式约束QP问题的Lagrange方法考虑QP问题（1），其Lagrange函数为KKT条件：将此方程组写成（2）系数矩阵称为Lagrange矩阵。

设Lagrange矩阵可逆，其逆矩阵可表示为由式，得假设逆矩阵存在，由上述关系可解得：（3）（4）（5）于是Lagrange矩阵的逆可知。

（2）式两端乘以Lagrange矩阵的逆，就得到KKT点（6）（7）的迭代形式：设是问题（1）的任一可行解，即满足，在此点，目标函数的梯度利用和，可将（6）、（7）式改写为（8）（9）如果目标函数凸，则上述点就是一个全局极小。

例1，用Lagrange方法求解可计算出。

由（3）、（4）、（5）式得到再根据（6）式，计算问题的最优解（KKT点）为：三、起作用集方法（具有不等式约束的QP问题）考虑具有不等式约束的QP问题（10）为阶对称正定矩阵，为矩阵，秩为。

因为不是等式约束，因此该问题不能直接用Lagrange方法求解*，求解的策略之一，是用起作用集方法将它转化为求解等式约束问题。

*使用剩余变量也能化为等式约束：；但这种方法是不可取的，因为又增加了不等式约束：，结果问题还是没有完全转化为等式约束。

（一）起作用集方法的基本思路在每次迭代中，以已知的可行点为起点，把在该点的起作用约束作为等式约束，在此约束下极小化目标函数，而其余的约束暂且不管，求得新的比较好的可行点后，再重复以上做法。

文章编号：1671-7872(2023)03-0313-11基于序列二次规划算法的插电式混合动力汽车模型预测控制策略张代庆 ，俞　聪 ，牛礼民 ，汪　恒 ，张义奇(安徽工业大学 机械工程学院, 安徽 马鞍山 243032)摘要：为提升插电式混合动力汽车(PHEV)的车速预测精度和燃油经济性，提出基于序列二次规划(SQP)算法的模型预测控制能量管理策略。

以卷积神经网络(CNN)构建的车速预测模型为基础，选取三类典型历史工况数据作为CNN 车速预测模型的训练集，使用鲸鱼优化算法(WOA)优化CNN 参数，通过优化的WOA-CNN 模型预测未来时域内的车速；采用SQP 算法对模型预测控制策略进行求解，且与基于规则的电量消耗和电量保持(CD-CS)策略和基于全局优化的动态规划(DP)策略的控制结果进行对比分析，验证所提策略的有效性。

结果表明：通过WOA-CNN 模型可提高车速预测精度，为4.88%~8.39%；与DP 控制策略相比，本文提出策略的燃油消耗量高出1.98%，但计算时间减少了74.32%，能量管理的实时性得到大幅提升；与CD-CS 控制策略相比，提出策略的节油率为20.37%。

综合考虑，本文提出策略的整车能量消耗和计算成本较优，可合理实现对PHEV 转矩分配的智能控制。

关键词：能量管理策略；模型预测控制；卷积神经网络；鲸鱼优化算法；序列二次规划；混合动力汽车中图分类号：U 469.72 文献标志码：A doi ：10.12415/j.issn.1671−7872.22264Predictive Control Strategy of PHEV Model Based on Sequential QuadraticProgramming AlgorithmZHANG Daiqing, YU Cong, NIU Limin, WANG Heng, ZHANG Yiqi(School of Mechanical Engineering, Anhui University of Technology, Maanshan 243032, China)Abstract ：In order to improve the speed prediction accuracy and fuel economy of plug-in hybrid electric vehicle (PHEV), a model predictive control energy management strategy based on sequential quadratic programming (SQP)algorithm was proposed. Based on the speed prediction model constructed by convolutional neural network (CNN),three types of typical historical working conditions were selected as the training set of CNN speed prediction model.Whale optimization algorithm (WOA) was used to optimize CNN parameters, and the optimized WOA-CNN model was used to predict the future speed in the time domain. SQP algorithm was used to solve the model predictive control strategy, and the control results with the rule-based charge depleting and charge sustaining (CD-CS) control strategy and the global optimization based dynamic programming (DP) control strategy were compared and analyzed to verify the effectiveness of the proposed strategy. The results show that the prediction accuracy of vehicle speed收稿日期：2022-10-24基金项目：先进数控和伺服驱动技术安徽省高校重点实验室开放基金项目(XJSK202104)；安徽工程大学电力驱动与控制安徽省重点实验室开放基金项目(DQKJ202204)；安徽省大学生创新创业项目(S202110360259)作者简介：张代庆(1997—)，男，黑龙江大庆人，硕士生，主要研究方向为新能源汽车控制技术。