2.5二次规划在线视频

同学们好

本次课主要讲授二次规划

二次规划是十分特殊的约束非线性规划问题

所以对它的求解方法也是特殊的

二次规划有着广泛的应用

不少实际问题

例如意大利水文学家纳特（Natale）

托迪尼（Todini）于1974年提出的

线性约束系统模型（CLS）的参数识别问题

支持向量机模型的求解等

最终都归结为求解一个二次规划问题

其中目标函数是一个二次函数

约束条件是me个等式约束和

（m-me）个不等式约束

m个约束条件的左端项均为线性函数

当H正定（或半正定）时

二次规划问题

（2.5-1）～（2.5-3）为凸规划

它的局部极值点即为全局极值点

Kuhn-Tucker条件不但是

极值点存在的必要条件

也是充分条件

因此

求解二次规划问题

（2.5-1）～（2.5-3）

可以转化为求Kuhn-Tucker点

考虑只有等式约束的二次规划问题

求解等式约束二次规划问题等价于

求解由K-T条件得到的线性方程组.

下面看一个例题.

例

求解仅有等式约束的二次规划

解

该二次规划的广义拉格朗日函数为

K-T条件

求解由上述K-T条件构成的线性方程组得

于是

Wolfe方法求解的是如

（2.5-19）～（2.5-21）

形式的二次规划

我们有K-T条件组

（2.5-22）～（2.5-25）

Wolfe方法就是将求解K-T条件

（2.5-22）～（2.5-25）

转化为线性规划问题求解

进而达到求解二次规划问题

（2.5-19）～（2.5-21）

的目的.

这一算法分为短形式和长形式2种情形

下面考虑Wolfe方法短形式

假定H正定或g=0

引进人工变量W

Z1

Z2

考虑线性规划问题（2.5-26）～（2.5-30）
（2.5-30）的含义是

vj与xj不能同时作为基变量

显然它是线性规划问题

（2.5-26）～（2.5-30）

的1个基本可行解

若采用线性规划单纯形法求解得到

线性规划问题（2.5-26）～（2.5-30）的最优解

且满足（2.5-31）

则求得满足Kuhn-Tucker条件（2.5-22）～（2.5-25）的K-T点

线性规划问题（2.5-26）～（2.5-30）

可分解成较简单的2阶段求解

以第1阶段求得的最优解及U=0

V=0

W=0作为第2阶段线性规划问题

（2.5-36）～（2.5-40）

的初始基本可行解

采用单纯形法求解

求解过程中保持（2.5-40）成立

Wolfe已证明

当H正定或g=0时

线性规划问题

（2.5-36）～（2.5-40）

的最小值S2*=0

且Z1*=0

Z2*=0

于是

第2阶段最终求得的最优解满足

K-T条件（2.5-22）～（2.5-25）

进而求得二次规划问题

（2.5-19）～（2.5-21）

的最优解

下面考虑Wolfe方法长形式

将原二次规划问题分成3个阶段求解

首先

在原二次规划问题的K-T条件组

（2.5-22）～（2.5-25）中

令g=0

得（2.5-41）～（2.5-43）

便于Wolfe方法短形式进行2阶段求解

用第1阶段

第2阶段求出的最优解

与μ=0一起组成第3阶段辅助线性规划问题

（2.5-44）～（2.5-48）的一个基本解

求得（2.5-44）～（2.5-48）

一个解满足μ=1

则它就是原二次规划问题

（2.5-19）～（2.5-21）

的最优解.

当我们求解线性规划问题

（2.5-44）～（2.5-48）时

会发生2种情况

找到最优解

最优解无界

Wolfe证明了不会出现第一种情况

因此

在第3阶段单纯形迭代求解过程中

求得一系列解

X(i)

vi)

U(i)μ(i)

i=1

2…

I

I+1…

其中0<μ(1)< μ(2)<…<μ(I)< μ(I+1)<…

若μ(I)<1

则必存在λ>0使μ(I)+ λμ(I+1)=1

于是得到（2.5-44）～（2.5-48）一个解

X^

V^

U^

μ^

=(X(I)+λX(I+1)

V(I)+ λV(I+1)

U(I)+ λU(I+1) μ(

I)+ λμ(I+1))

且满足μ^=1

若μ(I)≥1

则存在一个迭代步骤i0满足1≤i0≤I-1

使μ(i0)<1≤μ(i0+1)

于是存在α≥0β≥0α+β=1

使i)+βμ(i0+1)=1

于是得到（2.5-44）～（2.5-48）一个解

X^

V^

U^μ^=α

X(i0)+ βX(i0+1) α

V(i0)+ βV(i0+1) α

U(i0)+ βU(i0+1) αμ(

i0)+ βμ(i0+1)

且满足μ^=1

总之

求得（2.5-44）～（2.5-48）

一个解满足μ=1

即求得原二次规划问题

（2.5-19）～（2.5-21）

的最优解

有效集法是通过求解有限个

等式约束二次规划问题来解决

一般约束下的二次规划问题

（2.5-1）～（2.5-3）

理论基础是定理2.5-2

定理2.5-2 中的(2.5-50)

表示二次规划问题（2.5-1）～（2.5-3）

在X*点起作用的约束即有效约束

如果X*是（2.5-1）～（2.5-3）的可行点

且是问题（2.5-49）与

（2.5-50）的局部最优解

在X*处的Lagrange乘子满足非负性

即（2.5-51）成立

则X*必是原问题

（2.5-1）～（2.5-3）的K-T点

设在第 次迭代

有二次规划问题

（2.5-1）～（2.5-3）

的一个可行点

其有效集为

求等式约束二次规划问题

(2.5-52)

(2.5-53)的最优解为

相应的

乘子向量为

是否等于

两种情况求点

使得
第一种情形

由于

和
分别是（2.5-52）

（2.5-53）的最优解和可行解

所以有

但

不一定可行

1）若 为原问题的可行解

令

重复第 次迭代

2）若 不可行

取连接 与 的直线上

靠 最近的可行点作为

下次迭代的点

重复第 次迭代

第二种情形

1）若

则 是（2.5-1）～（2.5-3）的最优解

计算结束

2）若有小于0的k-T乘子

则取

在有效集 中删去小于0的k-T乘子对应的约束条件指标

得新的有效集

以

代替

重复第 次迭代.

本次课到此结束

谢谢大家

再见