文档介绍：《非线性规划》课程设计
题目：二次规划起作用集方法
院系：数理学院应用数学系
专业：数学与应用数学
姓名学号：119084112数112
指导教师：
日期：2014年6月19日
摘要
二次规划（QP）是指目标函数为决策变解，且在点X*处的起作用约
束集为J*，则X*是下述等式约束问题的唯一解:
minQ(x)=
XtHx+CTX
=b,igJ*.
ii
只含有等式约束的二次规划:
minf(x)=
xtHx+ctx;
2
=b,i=1,2,—,m.
ii
(2)
式中H为n阶对称正定矩阵，c,x均为n维列向量；a(i=1,2,•••,m)i
为n维行向量.
(3)
定理二规划(2)式的K-T对(x*,A*)是存在唯一的，且(x*,A*)为(2)
(3)
式的K-T对的充要条件是它们满足方程组：
一H
—At
X
—c
-A
0_
A
—b
二、一般正定二次规划的起作用集方法及计算步骤
对于一般正定二次规划(1)式，由定理一可知，只要能找到X*所满足的起作用约束指标集j*，就可以通过求解等式约束(2)式二次规划化问题得到X*.
但是X*未知，J*不能一下求出，可采用逐步改进的方法：先求出问题
(1)式的一个可行点X(k)，计算点X(k)处有起作用约束指标集J，并
k
求解相应的等式约束的二次规划问题(2)式•设其最优解为X(k)，乘子向量为Ak•令Pk=X(k)-x(k)，即认为Pk是从点X(k)出发至X(k)的方kkk
向，如求出了P也就找到了X(k)，X(k)=X(k)+(2)式
kk
可以化成求解：
minf(x)=1PtHP+(Hx(k)+c)tP
12kkk
=1PtHP+Vf(x(k))tP
2kkk
=0,ieJ.
ikk
设x(k)的起作用约束指标集为J，则根据x(k)与x(k)之间不同关系
k+1
来调整J(当然要使目标函数值不断减少)•按照这种思路继续，就
k
有可能得到J*，从而求得(1)式的最优解x*.
第1步：选定初始可行点x(1)及相应的起作用约束指标集J，使
1
a(igJ)：=1.
i1
第2步：求解含有等式约束的正定二次规划问题(3),设其解为P.
k
第3步：若Pk=0(即x(k)=x(k))，则计算相应的乘子向量a，转第
kk
4步•若P#0，转第5步.
k
第4步：若VjgJ\(1,2,.・.,m)；都有X(k)>0成立，则x(k)为规划(1)
kj
式的最优解，计算结束；否则求出加Q二min{X(k)|jgJ\(1,2,…,m)}，
qjk
令x(k+1)=x(k)，J=j\{q},k:=k+1,返回第2步.
k+1k
第5步：若皿=x(k)+P(P#0)满足ax>b，
kkii
ig{m+1，m+2,…,L}\J(即x(k)也满足规划(1)的可行域)，则k
令x(k+1)=x(k)，计算x(k+1)处的起作用约束指标集J，令k:=k+1，返k+1
回第2步•否则(即x(k+1)不是规划(1)式的可行解)转第6步.
第6