《非线性规划》课程设计题目：二次规划起作用集方法院系：数理学院应用数学系专业：数学与应用数学姓名学号：119084112 数112指导教师：日期：2014年6月19日摘要二次规划（QP）是指目标函数为决策变量x的二次函数，而约束函数是线性函数的非线性规划.二次规划规划问题是最简单的一类非线性约束优化问题，并且某些非线性规划可以转化为求解一系列二次规划问题，因此二次规划的求解方法也是求解非线性规划的基础之一.关键词：二次规划；起作用集；乘子向量AbstractQuadratic programming (QP) refers to the objective function for the quadratic function of the decision variables x, and the constraint function is a linear function of nonlinear programming, quadratic programming problem is the simplest nonlinear constraint optimization problems, and some nonlinear programming can be transformed into solving a series of quadratic programming problem, so the solving methods of quadratic programming is also one of the basis of solving nonlinear programming.Keywords: Quadratic programming; Work set; Multiplier vector目录一、二次规划的概念与性质1.1模型一1.2模型二二、一般正定二次规划的起作用集方法及计算步骤2.1方法2.2计算步骤三、算例总结一、二次规划的概念与性质 1.1模型一⎩⎨⎧+=≥==+=.,,1,,,,2,1,.;21)(min L m j b x a m i b x a t s x c Hx x x f j j i i T T(1) 式中H 为n 阶对称正定矩阵，c,x 均为n 维列向量；i a （i=1,2,···,m),j a (j=m+1,···,L)均为n 维行向量.另L m m b b b b b ,,,,,,121 +都是已知实数，且m ≤n(L ≥m).定理一 设*x 是上式正定二次规划的最优解，且在点*x 处的起作用约束集为*J ，则*x 是下述等式约束问题的唯一解：.,.21)(min *J i b x ta s xc Hx x x Q i i T T∈=+=1.2模型二只含有等式约束的二次规划：.,,2,1,.;21)(min m i b x ta s x c Hx x x f i i T T==+=（2）式中H 为n 阶对称正定矩阵，c,x 均为n 维列向量；i a （i=1,2,···,m)为n 维行向量.定理二 规划（2）式的K-T 对),(**Λx 是存在唯一的，且),(**Λx 为（2）式的K-T 对的充要条件是它们满足方程组：⎥⎦⎤⎢⎣⎡--=⎥⎦⎤⎢⎣⎡Λ⎥⎦⎤⎢⎣⎡--b c x AA H T 0二、一般正定二次规划的起作用集方法及计算步骤2.1方法对于一般正定二次规划（1)式，由定理一可知，只要能找到*x 所满足的起作用约束指标集*J ，就可以通过求解等式约束（2）式二次规划化问题得到*x .但是*x 未知，*J 不能一下求出，可采用逐步改进的方法：先求出问题（1）式的一个可行点)(k x ，计算点)(k x 处有起作用约束指标集k J ，并求解相应的等式约束的二次规划问题(2)式.设其最优解为)(ˆk x ，乘子向量为k Λ.令k P =)(ˆk x－)(k x，即认为k P 是从点)(k x出发至)(ˆk x的方向，如求出了k P 也就找到了)(ˆk x ，)(ˆk x =)(k x +k P .因此求解（2）式可以化成求解：.,0.)(21)(21)(min )()(1k k i k T k k T k kT k k Tk J i P a t s P x f HP P P c Hx HP P x f ∈=∇+=++= （3)设)(ˆk x 的起作用约束指标集为1+k J ，则根据)(ˆk x 与)(k x 之间不同关系来调整k J （当然要使目标函数值不断减少）.按照这种思路继续，就有可能得到*J ，从而求得（1）式的最优解*x . 2.2步骤第1步：选定初始可行点)1(x 及相应的起作用约束指标集1J ，使)(1J i a i ∈线性无关.令k:=1.第2步：求解含有等式约束的正定二次规划问题(3)，设其解为k P .第3步：若k P =0（即)(ˆk x=)(k x），则计算相应的乘子向量k Λ，转第4步.若k P ≠0，转第5步.第4步：若),,2,1(\m J j k ∈∀；都有0)(≥k j λ成立，则)(k x为规划（1）式的最优解，计算结束；否则求出)},,2,1(\|min{)()(m J j k k j k q ∈=λλ，令)1(+k x =)(k x，1+k J =k J \{q}, k:=k+1,返回第2步.第5步：若)(ˆk x =)(k x +k P （k P ≠0）满足i i b x a ≥，k J L m m i \},,2,1{ ++∈（即)(ˆk x 也满足规划（1）的可行域），则令)1(+k x =)(k x，计算)1(+k x 处的起作用约束指标集1+k J ，令k:=k+1，返回第2步.否则（即)1(+k x 不是规划（1）式的可行解）转第6步.第6步：从)(ˆk x 点出发沿方向k P 进行一维搜索.记)1(+k x =)(k x +k k P α，计算步长：}0,\),,2,1(|min{ˆ)(<++∈-=k i k ki k i i k P a J L m m i P a x a b α易见k aˆ为正数.因此对每个k J L m m i \},,2,1{ ++∈，i k k k i b P x a ≥+)ˆ()(α必成立. （因为)(k x是可行解，k aˆ是正数，当k k P a >0时更成立） 取k α=min{1,k aˆ}. 记 )1(+k x=)(ˆk x +k k P α.计算点)1(+k x 处的起作用约束指标集1+k J .令k:=k+1，返回第2步. 三、算例用起作用约束集方法计算（书上例题409页）：⎩⎨⎧≥-≥----+-=.0,,623.;102)(min 212121222121x x x x t s x x x x x x x f用LINGO 求解，程序如下： MODEL: Sets:num_i/1,2/:c,x; endsets data: c=-3, -2; enddata[OBJ]min=(x(1)^2－x(1)*x(2)+2*x(2)^2－x(1)－10*x(2); @sum(num_i(i):c(i)*x(i)>=－6; @for(num_i(i):x(i)>=0;);END运行该程序可得1x =21，2x =49，为原规划问题的最优解.总结二次规划规划问题是最简单的一类非线性约束优化问题，并且某些非线性规划可以转化为求解一系列二次规划问题，因此二次规划的求解方法也是求解非线性规划的基础之一. 参考文献[1]何坚勇·最优化方法·北京：清华大学出版社，2007.。
