* 2 1 0 * 3(1 x1 ) * 1 * 0 1 2 3 0 1 0 1 0 1*[(1 x1* )3 x2* ] 0 2* x1* 0 3* x2* 0 1* , 2* , 3* 0
min f1 ( X ) f ( X ) x1
x1
s.t. g1 ( X ) (1 x1 )3 x2 0 g 2 ( X ) x1 0 g3 ( X ) x2 0
如上图所示，阴影部分为可行域 R，红色直线为目标函数的等值 线。显然最大值点为（1，0）。
（3） 成立
并令 即得
*j j / 0 , j 1,2,...p
p * * * f ( X ) g ( X )0 j j j 1 * * j g j ( X ) 0, j 1,..., p j * 0, ( j 1,..., p )
对于凸规划，库恩—塔克条件不但是最优点存在的必 要条件，它同时也是充分条件。
库恩—塔克条件的几何解释：
某非线性规划的可行解X(k)，假定此处有两个起作用约束， 且其梯度线性无关。 若X（k）是极小点，则 f ( X ( k ) ) 必处于
g1 ( X ( k ) ), g 2 ( X ( k ) )
1 p
线性无关。则存在向量
( * ,..., * ), M ( * ,..., * )
使得
p m * * * * * f ( X ) i hi ( X ) j g j ( X ) 0 i 1 j 1 j * g j ( X * ) 0, j 1,..., p * 0, (i 1,..., m) * 0, ( j 1,..., p) i j
（7）
min f ( X ) s.t. g j ( X ) 0 hi ( X ) 0
j 1,..., p i 1,..., m
( II )
若x*是非线性规划(II)的局部极小点， 且x*点的所有起作用约束的梯度
hi ( X * ),i 1,...,m
1 m
和
g j ( X * )( j J )
min f ( X ) x12 x2 s.t. x12 x2 2 9 x1 x2 1
s.t. g1 ( X ) 9 x12 x2 2 0 g 2 ( X ) 1 x1 x2 0
2 0 2 f ( X ) 0 0 2 0, 2 0 0 0 0
* *
使得
p * * * f ( X ) j g j ( X ) 0 j 1 * * j g j ( X ) 0, j 1,..., p j * 0, ( j 1,..., p )
（7）
成立
p * * 0 f ( X ) j g j ( X ) 0 j 1 * j g j ( X ) 0, j 1,..., p j 0, j 1,..., p
j
的充要条件是存在不全为零的非负数，使得
A
j 1 j
l
j
0
成立
2、Fritze John定理
min f ( X ) s.t. g j (X ) 0
j 1,..., p
(I )
p * * 0 f ( X ) j g j ( X ) 0 j 1 * j g j ( X ) 0, j 1,..., p j 0, j 1,..., p
பைடு நூலகம்
2 x1 1 2 x1 (1 1 ) 2 0 2 x1 1 2 x 0 1 2 x 0 1 2 1 1 2 2
讨论
(i)1 0, 2 0 2 1 0, (ii)
(2)
(1)
该问题的K-T条件为
2 x1 (1 1 ) 2 0 1 2 x 0 1 2 2 2 2 1 ( x1 x2 9) 0 2 ( x1 x2 1 ) 0 1 , 2 0
（1） （2） （3） （4） （5）
第9讲 最优性条件和二次规划
最优性条件 二次规划
重 点：最优性条件，二次规划 难 点: 最优性条件及应用 基本要求：理解可行方向、下降方向、有效约束等概念， 掌握最优性条件，并会用其求解有约束极值问题，掌握 二次规划模型及求解方法，理解序列二次规划的原理和特点。
最优性条件（5.1）
min f ( X ) s.t. g j ( X ) 0 j 1,..., p (I )
0 0 g1 ( X * ) , g3 ( X * ) 1 1
线性相关
X * (1,0)T 不是K-T点。
自己验证 X * (1,0)T 是F-J点。
例2 用K-T条件，求解非线性规划 解：1 验证该问题为凸规划 原问题标准化为
min f ( X ) x12 x2
（1） （2） （3） （4）
（5）
（1）式为
1 31* (1 x1* ) 2 2* 0
1* 3* 0
X * (1,0)T
代入上式，得：2* 1 0 不是K-T点。
故 X * (1,0)T
X (1,0) 的起作用约束为
* T
g1 ( X ) (1 x1 )3 x2 0 g3 ( X ) x2 0
0f ( X ) j g j ( X * ) 0
* j 1 l
(6)
j g j ( X * ) 0, j 0, j 1,2,...,p
3 Kuhn-Tucker条件
设x*是非线性规划（I）的局部极小点f ( X ), g j ( X ) 有一阶连续偏导 而且X*处的所有起作用约束梯度线性无关， 则存在数 1 ,..., p
(3) 成立
1 (4)
f ( X * )T P 0 * T * g j ( X ) P 0, j J ( X )
0 0, j 0, ( j J )
0f ( X * )
jJ ( X * )

j g j ( X * ) 0 (5)
p
g j ( X ) 0 j 1,..., p; hi ( X ) 0, i 1,..., m
处的起作用（紧）约束。记 处起作用（紧）约束的下标集 记 R= X g j ( X ) 0 j 1,..., p 或 R= X
为（I）或（II）的可行域
2 可行方向 定义:
判别条件 若 若
D
是 X (0) 的任一下降方向，则有 f ( X (0) )T D 0
(2)
D
既满足（1）式又满足（2）式则称
D
为 X (0)的下 降可行方向
f ( X )在 X (0) 处可微， 定理1 X (0) 为（I）的局部极小值点，
g j ( X )( j J ( X
(0)
(0) (0)处可微 g ( X )( j J ( X ))在 X (0) 处连续 在 j )) X
则在 X (0) 处不存在可行下降方向。即不存在向量
g j ( X (0) )T D 0, j J ( X (0) ) (1)
D
f ( X ) D 0
(0) T
同时成立
(2)
二、最优性条件
1、Gordan引理
设 A1 ,..., Al 为 l 个 n 维向量，不存在向量P 使得 AT P 0, J 1,..., l 成立
（7）
* * * * 其中 1 ,..., m ; 1 ,..., p 称为广义拉格朗日(Lagrange)乘子。
库恩—塔克条件是确定某点为最优点的必要条件， 只要是最优点．且此处起作用约束的梯度线性无关。 就必须满足这个条件。但一般说来它并不是充分条 件，因而，满足这个条件的点不一定就是最优点。
min f ( X ) s.t. g j ( X ) 0 hi ( X ) 0 j 1,..., p i 1,..., m ( II )
一、基本概念
1 起作用（紧）约束
X (0)
是(I)的可行解，若 g j ( X (0) ) 0 则称 g j ( X ) 0 为 X (0)
2 f ( X ) 半正定， f ( X ) 是凸函数
2 0 2 0 2 g1 ( X ) , 2 0, 40 0 2 0 2
2 g1 ( X )
负定
所以 g1 ( X ) 是凹函数 故该问题为凸规划。
2 求K-T点
2x f (X ) 1 1 2 x1 g1 ( X ) 2 x2 1 g 2 ( X ) 1
1 0, 2 0 (1 1 ) x1 0, 1 0 x1 0 1 0 x12 x2 2 9 x2 3 (2) 1 x2 3, 1 6
(3)
X (0, 3)T 是K-T点
(iii)
x12 x2 2 9 1 0, 2 0 x1 x2 1
3(1 x1 ) 2 1 1 0 f ( X ) , g1 ( X ) , g ( X ) , g ( X ) 2 3 0 0 1 1
K-T条件
f ( X * ) 1*g1 ( X * ) 2*g 2 ( X * ) 3*g3 ( X * ) 0 * * g ( X )0 1 1 2* g 2 ( X * ) 0 3* g3 ( X * ) 0 * * * , , 1 2 3 0