下载文档原格式
求解二次规划问题的拉格朗日及有效集方法——最优化方法课程实验报告学院：数学与统计学院班级：硕2041班姓名：王彭学号：3112054028指导教师：阮小娥同组人：钱东东求解二次规划问题的拉格朗日及有效集方法求解二次规划问题的拉格朗日及有效集方法摘要二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，约束函数都是线性函数。
由于二次规划比较简单，便于求解（仅次于线性规划），并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此二次规划的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途径。
二次规划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一般约束凸二次规划的有效集方法。
关键字：二次规划，拉格朗日方法，有效集方法。
- 1 -《最优化方法》课程实验报告- 2 - 【目录】摘要........................................................................................................................... - 1 -1 等式约束凸二次规划的解法............................................................................... - 3 -1.1 问题描述.................................................................................................... - 3 -1.2 拉格朗日方法求解等式约束二次规划问题............................................ - 3 -1.2.1 拉格朗日方法的推导...................................................................... - 3 -1.2.2 拉格朗日方法的应用...................................................................... - 4 -2 一般凸二次规划问题的解法............................................................................... - 5 -2.1 问题描述.................................................................................................... - 5 -2.2 有效集法求解一般凸二次规划问题........................................................ - 6 -2.2.1 有效集方法的理论推导.................................................................. - 6 -2.2.2 有效集方法的算法步骤.................................................................. - 9 -2.2.3 有效集方法的应用........................................................................ - 10 -3 总结与体会......................................................................................................... - 11 -4 附录..................................................................................................................... - 11 -4.1 拉格朗日方法的matlab程序................................................................. - 11 -4.2 有效集方法的Matlab程序 .................................................................... - 11 -求解二次规划问题的拉格朗日及有效集方法- 3 -1 等式约束凸二次规划的解法1.1 问题描述我们考虑如下的二次规划问题⎪⎩⎪⎨⎧=+b Ax t s x c Hx x T T ..,21min (1.1) 其中n n R H ⨯∈对称正定，n m R A ⨯∈行满秩，n R x c,∈，m R b ∈。
第17讲凸二次规划的有效集方法凸二次规划问题（Convex Quadratic Programming）是一类重要的优化问题，在很多实际应用中都有广泛的应用。
其中，凸表示问题的目标函数和约束函数均为凸函数，二次表示问题的目标函数和约束函数均为二次函数，规划表示问题以最小化或最大化目标进行求解。
有效集方法（Active Set Method）是一种常用于求解凸二次规划问题的有效优化算法，其核心思想是通过选择合适的约束集来求解问题，并通过不断调整约束集来逐步逼近最优解。
以下将介绍凸二次规划问题的有效集方法的基本思路及求解过程。
基本思路：1.初始化：从一个空集合开始，即没有约束条件；2.解决子问题：在当前约束集下，求解相应的凸二次规划子问题，得到当前的最优解；3.更新约束集：根据最优解的性质，判断是否需要更新约束集；4.终止条件：如果约束集不再发生变化，或者达到预设的终止条件，算法结束；否则，返回第2步。
求解过程：1.初始化：先将约束集定义为空集，即没有约束条件；2.解决子问题：求解当前约束集下的凸二次规划子问题，得到当前的最优解。
常用的求解方法是拉格朗日乘子法，通过求解一组线性方程组来得到最优解；3.更新约束集：根据最优解的性质，判断是否需要更新约束集。
如果最优解满足所有约束条件，则算法结束；否则，选择一个违反约束条件的变量，将其添加到约束集，并返回第2步；4.终止条件：当约束集不再发生变化，或者达到预设的终止条件时，算法结束。
终止条件可以是达到最大迭代次数、目标函数变化小于设定阈值等。
有效集方法的优点在于可以充分利用问题的特殊结构和凸性质，通过不断调整约束集来逼近最优解。
然而，该方法在实际应用中也存在一些问题，如对约束条件的求解可能存在数值误差、对约束集的选择可能存在困难等。
因此，对于一些复杂的凸二次规划问题，可能需要考虑其他的优化算法来求解。
总之，凸二次规划问题的有效集方法是一种常用的优化算法，它通过选择合适的约束集来求解问题，并通过不断调整约束集来逼近最优解。
第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方法求解*，求解的策略之一，是用起作用集方法将它转化为求解等式约束问题。
*使用剩余变量也能化为等式约束：；但这种方法是不可取的，因为又增加了不等式约束：，结果问题还是没有完全转化为等式约束。
（一）起作用集方法的基本思路在每次迭代中，以已知的可行点为起点，把在该点的起作用约束作为等式约束，在此约束下极小化目标函数，而其余的约束暂且不管，求得新的比较好的可行点后，再重复以上做法。
《非线性规划》课程设计
题目：二次规划起作用集方法院系：数理学院应用数学系
专业：数学与应用数学
姓名学号：119084112 数112
指导教师：
日期：2014年6月19日
摘要
二次规划（QP）是指目标函数为决策变量x的二次函数，而约束函数是线性函数的非线性规划.二次规划规划问题是最简单的一类非线性约束优化问题，并且某些非线性规划可以转化为求解一系列二次规划问题，因此二次规划的求解方法也是求解非线性规划的基础之一.
关键词：二次规划；起作用集；乘子向量
Abstract
Quadratic 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,.;
2
1)(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 是下述等式约束问题的唯一解：
.
,.2
1)(min *
J i b x ta s x
c 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 A
A 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.)(2
1)(21)(min )()(1k k i k T k k T k k
T k k T
k 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 k
i 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 2121212
22121x 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 =2
1，2x =4
9，为原规划问题的最优解.
总结
二次规划规划问题是最简单的一类非线性约束优化问题，并且某些非线性规划可以转化为求解一系列二次规划问题，因此二次规划的求解方法也是求解非线性规划的基础之一. 参考文献
[1]何坚勇·最优化方法·北京：清华大学出版社，2007.。
