二次规划(QP)及有效集方法 解二次规划的有效集方法 minf(x)=xHx+cx当H为对称阵,称二次规划 基本思想:对于不等式约束的二次规划,在某可行点 当H正定时,称凸二次规划 处将不起作用约束去掉,起作用约束视为等式约束 st.Ax≤b 凸二次规划性质: 通过求解等式约束的二次规划来改进可行点 等式约束Ax=b下 最优点←KKT点 的 Lagrange乘子法部最优解全局最优解 min(x)=-r'Hx+cx minf(x)=5x'Hx+ s.Ax≤b L函数L(x,A)=xHx+ax+(Ax-b),A∈R b,j∈J(a,是A的第/列) 基本·若x为(1)的最优解,则它也是(2)的最优解 最优解方程x+c+4=0 原理若x为(1)的可行解,又是(2)的KT点,且 Ax-b=0 L一乘子非负,则它必是(1)的最优解 基本步骤设(1)的可行点为x*,有效集 min==lxX+cx 记作/*,用L—乘子法求解 MTAB求解QPs,Ax≤b,.x=b:5xn Ix, fval, exitflag, output, lambda] minf(x*d)=1(x*+d)H(x*+d)+(x*+4)得P”, quadprog(H,C, Al, bl, A2, b2, vl, v2, xO, options) 若d=0,则x*为(2)最优解,当λ*非负时x*是(1)最优解 x1+2x2=3 x1-x22-3H 有效集若=0,且(2)<0,q∈/,则x不是最优解, x1-3x,≤3 修正有效集修正为g} x1≥2,x2≤04 若d≠0,以此为方向确定步长a·使得 a(x*+*弹)=by,pgJ*,则有效集修正为严U{p Exam0803 m (学学奖 实例2:投资组合问题 实例2:投资组合问题 minz2=4x2+36x2+100x2+5x1x2-20xx3-30x2x1 加权 MinZ=BZ2-Z st5x1+8x2+10x321000 0x1+25x2+30x3≤5000 模型 st.20x1+25x2+30x3≤5000 portfolio2.m 通过试探发现B从 解得x=1.0e+002*(13111,0.1529,0.2221) 0.0001-01以0.0001的 如果一定要整数解,可以四舍五入到(131,15,22) 步长变化就可以得到 如利用 LINGO软件可得整数最优解(132,15,2) 很好的近似结果 用去资金为132x20+15×25+22×30=3675(百元) 期望收益为132×5+15×8+22×10=1000(百元 投资股纂A、B、C分别 风险(方差为68116,标准差约为261(百元 为153、35、35(手)6 二次规划(QP)及有效集方法 st Ax b f x x Hx cx T ≤ = + . . 2 1 min ( ) 当H为对称阵，称二次规划 当H正定时，称凸二次规划 凸二次规划性质： 最优点⇔KKT点； 局部最优解⇔全局最优解； T T m L x λ = x Hx + cx + λ (Ax − b), λ ∈ R 2 1 ( , ) 最优解方程 0 0 − = + + = Ax b Hx c A T T λ L函数 等式约束 下 的Lagrange乘子法 Ax = b 解二次规划的有效集方法 基本思想：对于不等式约束的二次规划，在某可行点 处将不起作用约束去掉，起作用约束视为等式约束， 通过求解等式约束的二次规划来改进可行点。 • 若x为(1)的最优解，则它也是(2)的最优解 • 若x为(1)的可行解，又是(2)的KKT点，且 L—乘子非负，则它必是(1)的最优解。 st Ax b f x x Hx cx T ≤ = + . . 2 1 min ( ) (1) 1 . . , 2 1 min ( ) st a x b j J f x x Hx cx j j T = ∈ = + (a 是A的第 j列) j (2) 基本 原理 . . 0, * ( * ) ( * ) ( * ) 2 1 min ( * ) st a d j J f x d x d H x d c x d j T = ∈ + = + + + + 若d*≠0，以此为方向确定步长α*使得 ap(x*+α*d*)=bp，p∉J*，则有效集修正为J*∪{p}。 设(1)的可行点为x*，有效集 记作J*，用L—乘子法求解: 基本步骤 得d*, λ* • 若d*=0, 则x*为(2)最优解; 当λ *非负时x*是(1)最优解 若d*=0, 且(λ *)q<0, q∈J* , 则x*不是最优解, 有效集修正为J*\{q} 。 有效集 修正 MATLAB求解QP [x,fval,exitflag,output,lambda] = quadprog(H,c,A1,b1,A2,b2,v1,v2,x0,options) 1 1 2 2 1 2 2 1 . . , , min s t A x b A x b v x v z x Hx c x T T ≤ = ≤ ≤ = + 2, 0 3 3 2 3 . . 2 3 min ( , ) 2 3 3 3 1 2 1 2 1 2 1 2 1 2 2 1 2 2 2 1 2 1 ≥ ≤ − ≤ − ≥ − + = = − + − + x x x x x x st x x f x x x x x x x x Exam0803.m (1,2), 3, [2, Inf], 2 [Inf,0] , 3 3 , 1 3 2 1 1 3 , 3 6 4 3 2 2 1 1 1 = = = − = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛− = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − = A b v v A b H c 解得x = 1.0e+002 *（1.3111，0.1529，0.2221） 如果一定要整数解，可以四舍五入到（131，15，22） 如利用LINGO软件,可得整数最优解(132，15，22) 用去资金为132×20+15×25+22×30 = 3675（百元） 期望收益为132×5+15×8+22×10 = 1000（百元） 风险(方差)为 68116，标准差约为261（百元） 实例2：投资组合问题 s.t. 5x1 +8x2+10x3 ≥ 1000 20x1+25x2+30x3 ≤ 5000 x1，x2，x3 ≥ 0 1 2 1 3 2 3 2 3 2 2 2 2 1 min Z = 4x + 36x +100x + 5x x − 20x x − 30x x portfolio1.m 通过试探发现 β从 0.0001~0.1以0.0001的 步长变化就可以得到 很好的近似结果 实例2：投资组合问题 Min Z =βZ2 - Z1 s.t. 20x1+25x2+30x3 ≤ 5000 x1，x2，x3 ≥ 0 加权 模型 0 200 400 600 800 1000 1200 1400 1600 1800 0 100 200 300 400 500 600 700 800 900 预期收益(百元) 均方差（百元） 投资股票A、B、C分别 为153、35、35（手） portfolio2.m