序列二次规划算法

《序列二次规划算法》由会员分享，可在线阅读，更多相关《序列二次规划算法（7页珍藏版）》请在装配图网上搜索。

1、序列二次规划法求解一般线性优化问题:min f (x)h (x)二 0,i e E 二l,.,m s.t. 0,i e I 二l,.,m i2(1.1) 基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通 过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的 解。1.1 等式约束优化问题的 Lagrange-Newton 法考虑等式约束优化问题min f (x)s.t.h (x)二 0, j e E 二l,.,m j(1.2)其中f : Rn t R, h : Rn T R(i e E)都为二阶连续可微的实函数.i记 h(x) = (h (x),., h

2、(x)t .lm则(1.3)的 Lagrange 函数为：L(x, u) = f (x) - u * h (x) = f (x) 一 ut * h(x)iii =1(1.3)其中 u = (u ,u ,., u )T 为拉格朗日乘子向量。l 2m约束函数h(x)的 Jacobi 矩阵为：A(x) = Vh(x)t = (Vh (x),., Vh (x)t . lm对(1.3)求导数，可以得到下列方程组：V L(x, u)xVf (x) 一 A(x)t * uV L(x, u)u-h( x)=0VL( x, u)=1.4)现在考虑用牛顿法求解非线性方程(1.4).VL(x,u)的 Jacobi

3、矩阵为:N(x,u) =W (x, u) 0的充要条件是存在常数b * 0，使得对任意的*都有xt *(U+a *S*St)x 0, Vx 丰 0 e Rn.证明略。鉴于方程组(1.6)的求解数值不稳定，故考虑将它转化成一个严格凸二次规划问题.转化的条件是(1.4)的解点x*处的最优性二阶充分条件成立，即对满足A(x*)t *d = 0的任一向量d 丰 0，成立dT *W(x*,u*)* d 0。1再由引理1知：当e 0充分小时，W(x*,u*) +A(x*)TA(x*)正定。2t考虑(1.6)中的W(x ,u )用一个正定矩阵来代替，记kk1B(x , u ) = W(x , u ) +A(

4、x )t A(x )k kk k2ekk则当(x , u ) T (x*, u*)时，矩阵 B(x*, u*)正定。kk(1.6)的第一个展开式为W(x , u )*d - A(x )t * v =-Vf (x ) + A(x )t * uk k k k k k k k将上式变形为：11W(x ,u ) + 一 A(x )tA(x )*d - A(x )t *v + u +一 A(x )d = -Vf (x )k k2Tkkkkk k 2Tk kk1令U,:二 v + u + A(x)Td 后得: k k k 2k kB(x ,u )*d - A(x )T *u kk= -Vf (xk)-因此

5、，(1.6)等价于B(x , u )kkA(x )k-A(x )t k*(d )k0丿(uk丿kk(Vf (x )k.h(x )丿k1.7)进一步，可以把方程(1.7)转换成如下严格凸二次规划:minq (d) = drB(x ,u )d + Vf(x )rd k2k kks.t h(x ) + A(x )d = 0kk1.8)方程(1.7)和(1.8)具有同解的。1.2一般形式的约束优化问题将 1.1 节中构造二次规划子问题求解等式约束优化问题的思想推广到一般形式的约束优化问题(15)。在给定点z = (x ,u ,九)后，将约束函数线性化，并对拉格朗日函数进行二次 kk k k多项式近似，

6、得到下列二次规划子问题:min dTW(x ,u )d + Vf(x )td2k kkh (x ) + Vh (x )t d = 0,i e Es.t 0.假定在 x *处，下面的条件成立：(1) 有效约束的Jacobi矩阵J *行满秩，其中s(x*)= eU心*)；S (x*)(2) 严格互补松弛条件成立，即g (x*) 0,九* 0,九*g (x*)二0, g (x*) +九* 0；i i i i i i(3) 二阶最优性充分条件成立，即对满足A(x*)t *d = 0的任一向量d丰0，成立dT *W(x*,u*,九 *)* d 0.那么若(x ,u ,九)充分靠近(x*,u*,九*)，则

7、二次规划问题(1.9)存在一个局部极小点d*，kkk使得其对应的有效约束指标集S (d *)与原问题在x*处的有效指标集S (x*)是相同的。注意:在构造二次规划子问题时，需要计算拉格朗日函数在迭代点x处的Hessen矩阵，k计算量过大。为了克服这个缺陷，韩世平基于牛顿-拉格朗日法提出了一种利用对称正定矩 阵B来代替拉格朗日矩阵W的序列二次规划法。kk对于一般约束优化问题(1.1)，在迭代点z = (x ,u ,九)，构造下列形式的二次规划子k k k k问题：min1 dTB(x ,u )d + Vf(x d2 k k kh (x ) + Vh (x )t d = 0,i e E(1,10)

8、S.t 0为罚参数，g (x)_ = max0,-g(x)。ii为了保证 SQR 方法的全局收敛性，通常借助价值函数来确定搜索步长。用来衡量一维 搜索的好坏。算法(一般约束优化问题的SQP方法)Step 0:给定初始点(x ,u ,九)e RnxRmxR对称正定矩阵B e Rn.0 0 0 0计算AeAe = Vh(x )t , Ai = Vg (x )t , A =0oooooAi0选择参数“ (O，Pe (QI),容许误差0* 2h令k ：= O.Step 1:求解子问题(1.10)得最优解d .kStep 2:若 lid II 且 II h II + 11( g )_ll ,stop,得

9、到(1.1)的一个近似 KT 点(x , u ,九).k 11k 1k 12k k kStep 3:对于某种价值函数(x,a )，选择罚参数a，使得d是该函数在x处的下降方向。kkkStep 4: Armijo搜索.令m是使下列不等式成立的最小非负整数m :k(x + pmd ,a )(x ,a ) 0.2s t B sk kk k kStep 7:令 k := k +1,转 1.o.8sT B sk-k ,s y sT B s sT yk kk k k k k 0,g( x ) + Ai d 0, Xg(x ) + Ai d二 0.k k k k第三式是 m 维互补问题，定义光滑函数2(,

10、a, b)二 a + b - Ja2 + b2 + 2e 2其中* 0为光滑参数令(s, a,b)=(s, a,b),.,(&, a,b)T，1m2其中(s,a,b) = X + g (x ) + (A1) d X2 + g (x ) + (A1) d2 + 2s2ii i kk iii kk iki其中(Ai)表示Ai的第i行.记z = (s, d, u, X) e R x Rnx Rx Rm2，那么(1.11)问题等价 k*H (z) := H (, d, u, X)H (d,u,X)1H (d,u,X)2(*, d, X)则H (z)的Jacobi矩阵为H=0BkAEkD (z)Ai2k

11、0-(AE )Tk000-( Ai )Tk0D(z)1m2其中 v = VgO(E, d, X) =(，vm )T，vi 由下式确定:2*1定：而 D =diag(a (z),.，a (z), D =diag(b (z),.，b (z)，其中 a (z),b 由下式确1m 221m2i iX.X2 + g (x ) + (A1) d2 + 2s2ii kk ib = 1.盯化)+ (A k)dX2 + g (x ) + (Ai) d2 + 2s 2 ii kk i给定参数丫 w (0,1)，定义非负函数卩(z)二丫 IIH(z)llmin1,llH(z)ll.(step 3)中选择价值函数0(XQ)二 f (x) + 丄ll h(x) ll + ll g(x)_llG11可令t = maxll u ll,ll 九 ll, g (x)_ = max0,-g (x)k k i i任意选择一个5 0，定义罚参数的修正规则为 G , G-1 T +5G = v k 1 k 1k(t + 25)1, g-1 0，而y可能不满足这一条件,k kk为此有必要对 y 进行修正。k参考文献1马昌凤最优化方法及其matlab程序设计科学出版社.2010.