第四章 约束最优化方法---最优化方法课件.ppt

严格凸二次规划的有效集方法 定理4.4.2 设x*是上面问题的最优解,且在x*处的有效集为I*,则x*也是下列问题的最优解 (4.86) (4.82) 有效集方法 证明:由于x*是(4.82)问题的最优解,存在乘子向量l*满足 显然有 这是问题(4.86)的最优解的充要条件. 有效集方法 例:解二次规划 min f(x)=(x1-1)2+(x1-2.5)2 s.t. x1 -2x2+2≥0 -x1 -2x2+6≥0 -x1 +2x2+2≥0 x1 ≥0 x2 ≥0 解: 取初始可行点x0=(2,0)T.有效集为I0={3,5}. 有效集方法 我们首先来求解等式约束二次规划 min f(x)=(x1-1)2+(x1-2.5)2s.t. -x1 +2x2+2=0 x2 =0 显然求得的最优解x1=x0. 我们来判断x1是否是原来的二次规划的KT点. 有效集方法 g1=(2,-5)T,a3=(-1,2)T,a5=(0,1)T, 令g1=l3a3+l5a5,则有l3= -2, l5= -1. 因此x1=(2,0)T不是KT点. 事实上, a3=(-1,2)T,a5=(0,1)T都是可行的下降方向. a3 a5 -g1 约束3 约束5 g1= -2a3-a5 有效集方法 去掉约束i1=3,得有效集I1={5},求解下面的二次规划 min f(x)=(x1-1)2+(x1-2.5)2 s.t. x2 =0 令x=xk+d,gk=Gxk+C, 则f(x)=xTGx/2+CTx=(xk+d)TG(xk+d)/2+CT(xk+d) =dTGd/2+xkTGd+xkTGxk/2+CTxk+CTd =dTGd/2+gkTd+xkTGxk/2+CTd 有效集方法 约束ajTx ≥bj等价于ajT(xk+d) ≥bj,即ajTd=0. 一般的,若已知可行解xk,有效集Ik,我们求解二次规划 它等价于求解 有效集方法 为了求得最优得x,只要求得对应的最优的d,因此,我们只要求解下面的二次规划 min dTGd/2+g1Tds.t. x2=0 其中 求解: 因此d1=(-1,0)T x2=x1+d1=(1,0)T. d1 x1 x2 有效集方法 因此d1=(-1,0)T x2=x1+d1=(1,0)T.有效集I2=I1={5}. 在上面求得的结果中x1+d1对于原来的二次规划是可行解. 在有些情况下,可能出现不可行解. 不过可以确定d1一定是可行的下降方向. 有效集方法 定理若严格凸二次规划 则有gkTpk0, aspk0. 作业:证明此定理. 最优解为dk=0,且Lagrange乘子有负分量(lk)s0. 设pk为下面二次规划的最优解 有效集方法 点x2对应的新二次规划为 min dTGd/2+g2Td s.t. x2=0 其中g2=(0,-5)T. 显然其最优解为d2=(0,0)T,Lagrange乘子向量为(-5). 取x3=x2+d2=x2=(1,0)T,有效集I3=I2\{5}=f. 有效集方法 点x3对应二次规划为(无约束) min dTGd/2+g3Td 求得d3=(0,2.5)T. 此时x3+d3不再可行. 我们求a3使得x3+a3d3可行,且a3尽可能大. 于是aiT(x3+a3d3)≥bi. 因此有 1-5a3+2 ≥0-1-5a3+6 ≥0-1+5a3+2 ≥01 ≥02.5a3 ≥0 解得a3=0.6.(第一个约束有效) x3 x4 约束1 有效集方法 x4=x3+a3 d3=(1,1.5)T,I4={1},g4=(0,-2)T. 求解对应的二次规划 min dTGd/2+g4Td s.t. x1 -2x2=0 解得d4=(0.4,0.2)T. x5=x4+d4=(1.4,1.7)T(可行), g5=(0.8,-1.6)T. 有效集方法 x5对应的二次规划为 min dTGd/2+g5Tds.t. x1 -2x2=0 其最优解为d5=(0,0)T. Lagrange乘子向量为(0.8)0,算法终止,最优解为x*=x5=(1.4,1.7)T. x4 x5 有效集方法 设xk是问题(4.82)的一个可行解,相应的有效集为Ik,Ak为(a1,···,am)中对应于Ik的子矩阵,求解 若(4.88)的最优解为dk=0,则xk为(4.87)的最优解.若此时Lagrange乘子向量非负,则xk是问题(4.82)的KT点,从而是最优解. (4.88) 有效集方法 若(4.88)的最优解dk ≠0,并且xk+dk为(4.82)的可行解,则令xk+1=xk+dk; 否则,以dk为方向进行线性有哪些信誉好的足球投注网站,求得(4.82)最好的