为便于用单纯形法求解，令
y1 d1 1, y2 d2 1, y3
min( y3 ) 4 4 8 y1 y2 y3 3 3 3 y1 2 y2 y3 3 y1 2 y2 2 y1 , y2 , y3 0
水电与数字化工程学院 莫 莉
前节回顾
5、二次规划的转化：
对二次规划问题进行修正，从而得到如下线性规划问题：
min
(Z ) z j
j 1
n
a
i 1 n
m
ij
yn i y j c j k xk sgn(c j ) z j c j , j 1, 2,
①若 J ( X
(k )
2


X (k )
(k ) ) ，而且 f ( X ) ε1 ，停止迭代，得点
②若 J ( X
(k )
(k ) ) ，但 f ( X ) ε1 ，则取搜索方向
2
D( k ) f ( X ( k ) ) ，然后转向第(5)步。
③若J ( X ( k ) ) ，转下一步。
k ε 2
若满足则停止迭代，得到点X(k) ；否则，以D(k)为搜索方向，并转下
一步。
水电与数字化工程学院 莫 莉
6.4 可行方向法
(5) 解下述一维极值问题
λ k :min f ( X ( k ) λD( k ) )
0 λ λ
此处
λ max λ g j ( X ( k ) λD( k ) ) 0, j 1, 2,
解：先将该非线性规划问题写成 2 min f ( X ) 4 x1 4 x2 x12 x2 g1 ( X ) x1 2 x2 4 0
取初始可行点 X (0) (0, 0)T
f ( X (0) ) 0
2x 4 4 (0) f ( X ) 1 , f ( X ) 4 2 x2 4 g1 ( X ) (1, 2)T g1 ( X (0) ) 4 0 (0) 从而 J ( X ) (空集)。由于
f ( X (0) ) (4)2 (4)2 32
2
所以X(0)不是(近似)极小点。
水电与数字化工程学院 莫 莉
6.4 可行方向法
现取搜索方向
从而
X
(1)
D(0) f ( X (0) ) (4, 4)T
X
(0)
λD
(0)
0 4 4λ λ 0 4 4λ
可行方向法
现考虑非线性规划(8-3)式，设X(k)是它的一个可行解
，但不是要求的极小点。为了求它的极小点或近似
极小点，根据以前所说，应在X(k)点的可行下降方向 中选取某一方向D(k) ，并确定步长λk，使
( k 1) (k ) (k ) X X λ D R k ( k 1) (k ) f ( X ) f ( X )
水电与数字化工程学院
莫 莉
前节回顾
3、库恩-塔克条件：
设X*是非线性规划(7-3)式的极小点，而且在X*点的各起作用
* T , , l* )，使下述条件成立： 约束的梯度线性无关，则存在向量 * ( 1* , 2
l * * * f ( X ) g ( X )0 j j j 1 * * j g j ( X ) 0, j 1, 2, ,l * j 1, 2, ,l j 0,
。
水电与数字化工程学院
莫 莉
6.4 可行方向法
设X(k)点的起作用约束集非空，为求X(k)点的可行下降方向，可由下述不等 式组确定向量D： (k ) T f ( X ) D 0 （8-22） (k ) T
g j ( X ) D 0, jJ
这等价于由下面的不等式组求向量D和实数η： f ( X ( k ) )T D (k ) T （8-23） g j ( X ) D , j J 0 (k ) T (k ) T 若使 f ( X ) D 和 gj ( X ) D (对所有 j J )的最大值极小化， 即可将上述选取搜索方向的工作，转换为求解下述线性规划问题：
第二章 非线性规划(Nonlinear Programming)
主讲人：莫 莉
moli@
2015 年 6 月
水电与数字化工程学院 莫 莉
前节回顾
温
一般模型
故
求解
知
罚函数法
新
可行方向法
基本概念
最优性条件
水电与数字化工程学院
莫 莉
前节回顾
1、一般模型
大多数极值问题其变量的取值都会受到一定限制，这种限制由约束 条件来体现。带有约束条件的极值问题称为约束极值问题。非线性
则得到可行下降方向
D ( k )，这就是我们所要的搜索方向。
水电与数字化工程学院
莫 莉
6.4 可行方向法
可行方向法的迭代步骤如下：
(0) (1)确定允许误差 ε1 0 ε 2 0，选初始近似点 X R，并令 k: 0
(2)确定起作用约束指标集
J ( X ( k ) ) j g j ( X ( k ) ) 0,1 j l
莫 莉
从而得到：
水电与数字化工程学院
6.4 可行方向法
引入剩余变量y4，松弛变量y5,y6,y7以及人工变量y8，得线性规划问题 如下：
min( y3 My8 ) 4 4 8 y1 y2 y3 y4 y8 3 3 3 y1 2 y2 y3 y5 3 y1 y6 2 y2 y7 2 y j 0, j 1, 2, ,8
（8-21）
水电与数字化工程学院
莫 莉
6.4 可行方向法
若满足精度要求，迭代停止，X(k+1)就是所要的点。否 则，从X(k+1)出发继续进行迭代，直到满足要求为止。
上述方法称为可行方向法，其特点是：
迭代过程中采用的搜索方向为可行方向，所产生的迭
代点列｛X(k)｝始终在可行域内，目标函数值单调下降
将其代入约束条件，并令 g1 ( X (1) ) 0 ，解得 λ 1/ 3
f ( X (1) ) 16λ 16λ 16λ 2 16λ 2 32λ 2 32λ
(1) 令 f ( X ) 对λ的导数等于零，解得λ=1/2。因λ大于
λ(λ 1/ 3)
故取 λ0 λ 1/ 3
（7-12）
（7-13）
（7-14）
(8-12)式右端的第二项为二次型。如果该二次型正定(或半正定)，则目 标函数为严格凸函数 (或凸函数 )；此外，二次规划的可行域为凸集， 因而，上述规划属于凸规划。第7章已指出：凸规划的局部极值即为全 局极值。对于这种问题，库恩-塔克条件不但是极值点存在的必要条件 ，而且也是充分条件。
水电与数字化工程学院 莫 莉
前节回顾
温
一般模型
故
求解
知
罚函数法
新
可行方向法
基本概念
最优性条件
水电与数字化工程学院
莫 莉
第二章 非线性规划
1 基本概念 最优性条件 凸函数和凸规划 一维搜索方法
2
3 4
Hale Waihona Puke 56水电与数字化工程学院
无约束最优化方法
约束最优化方法★
莫 莉
6.4 可行方向法
j 1, 2,
水电与数字化工程学院
莫 莉
前节回顾
2、可行下降方向
如果方向D既是X(0)点的可行方向，又是这个点的下降方向，就称它 是该点的可行下降方向。 （1）假如X(0)点不是极小点，继续寻优时的搜索方向就应从该点的可 行下降方向中去找。若某点存在可行下降方向，它就不会是极小点。 （2）若某点为极小点，则在该点不存在可行下降方向。
X (1)
64 4 4 , , f ( X (1) ) 9 3 3
T
T
4 4 f ( X (1) ) , , 3 3
水电与数字化工程学院
g1 ( X (1) ) 0
莫 莉
6.4 可行方向法
构造下述线性规划问题：
min 4 4 d1 d 2 3 3 d1 2d 2 1 d1 1, 1 d 2 1
(8-10)
条件(8-10)式常简称为K-T条件。满足这个条件的点(它当然也满足非线 性规划的所有约束条件)称为库恩-塔克点(或K-T点)。
水电与数字化工程学院 莫 莉
前节回顾
4、二次规划：
若非线性规划的目标函数为自变量X的二次函数，约束条件全是线性 的，称这种规划为二次规划。二次规划的数学模型为：

,l

(6) 令
X ( k 1) X ( k ) λ k D ( k ) k : k 1
转回第(2)步。
水电与数字化工程学院 莫 莉
6.4 可行方向法
例 用可行方向法解下述非线性规划问题
2 max f ( X ) 4 x1 4 x2 x12 x2 x1 2 x2 4
k 1
n
,n
a
j 1
（8-20）
,m
ij
x j xn i bi 0, i 1, 2, j 1, 2, j 1, 2, j 1, 2, ,n m ,n m ,n
x j 0, y j 0, z j 0,
该线性规划尚应满足(8-17)式。这相当于说，不能使xj和yj(对每一个j ) 同时为基变量。