当前位置：文档之家 › 第4章 最优性条件

第4章 最优性条件

  • 格式：doc
  • 大小：1.23 MB
  • 文档页数：17

下载文档原格式

  / 17

合集下载

4一般约束最优化问题的最优性条件.

4一般约束最优化问题的最优性条件.
*
T
, c 2 x
1,1, 0
*
T
.
令 6
即： f x * 2c1 x * 2c2 x * . * 0, i 1,2,3,4,5. c x 令i 0，i 3， 4， 5，则 i i
* x 所以， 是K-T点．
Fritz John 最优性条件—一阶必要条件
一般约束最优化问题的最优性条件
Fritz John 最优性条件—一阶必要条件
一般约束最优化问题的最优性条件
Fritz John 最优性条件—一阶必要条件
缺点
一般约束最优化问题的最优性条件
Kuhn-Tucker 最优性条件—一阶必要条件
一般约束最优化问题的最优性条件
c 3 x x1 0
c4 x x 2 0 c5 x x 3 0
试验证最优点 x * 1, 1, 1T为K-T点．
一般约束最优化问题的最优性条件
解： I * 1, 2, f x * 6,2,4T ,
c1 x
2,2, 2
一般约束最优化问题的最优性条件
Kuhn-Tucker 最优性条件—一阶充分条件
一般约束最优化问题的最优性条件
Kuhn-Tucker 最优性条件—一阶充分条件
一般约束最优化问题的最优性条件
Kuhn-Tucker 最优性条件—一阶充分条件
一般约束最优化问题的最优性条件
Kuhn-Tucker 最优性条件—一阶充分条件
一般约束最优化问题的最优性条件
几何最优性条件—一阶必要条件 定义 I ( x ) {i | gi ( x ) 0, i 1,2,..., m}. 定理3.4.1

工程优化 第4章-4

工程优化 第4章-4

优点：计算量较少，而且总能收敛到一个局部极小点。 缺点：收敛速度较慢
牛顿法（Newton）---基本思想
牛顿法是一种函数逼近法，基本思想是：在极小点附近用 函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数 的极小点的近似值。 对 f (x) 在 x k 点二阶泰勒展开：
f ( x) f ( xk ) f '( xk )( x xk )
从极值的必要条件 P x a1 2a2 x 0

求得
x a1 / 2a2
求出系数 a1 和 a2 ，就可得到极小点的表达式。
x a1 / 2a2
1 x 2 x
2 2 2
2 x3 f1 x32 x12 f 2 x12 x22 f 3
P x1 a0 a1 x1 a2 x12 f1 f x1
（1） （2） （3）
P x2 a0 a1 x2 a2 x22 f2 f x2
P x3 a0 a1 x3 a2 x32 f3 f x3
插值法---求二次插值多项式的极小点
0, 令 k 1 。 步骤1：给定初始点 x1 R，
步骤2：计算 f '( xk ), f ''( xk ) 。
步骤3：若 f '( xk ) ，停止，x* xk ，否则转步骤4。 步骤4：计算
f '( xk ) xk 1 =xk f ''( xk )
令 k k 1，转步骤2。 特点：收敛速度快，局部二阶收敛。 缺点：须计算二次导数，工作量大；对初始点要求高，要求初 始点离极小点不太远，否则有可能使极小化发散或收敛到非极 小点；局部收敛。

第四章约束问题的最优化方法

第四章约束问题的最优化方法

当limr(k) 0 k
则(x, r(k) ) f (x) , xk * x *
例： 用内点法求
min
f
(x)

x2 1

x2 2
s.t. g( x) 1 x1 0 的约束最优解。
解:
首先构造内点惩罚函数: (
x,
r)

x2 1

x2 2

rk
ln(x1
1)
用解析法求函数的极小值，运用极值条件：
二. 直接解法：
基本思想：合理选择初始点，确定搜索方向，以迭代公式 x(k+1)= x(k)+α(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。 适用范围：只能求解不等式约束优化问题的最优解。
基本要点：选取初始点、确定搜索方向及适当步长。
搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。 可行性：迭代点必须在约束条件所限制的可行域内，即满足
1
u1 gu (x)
② .(x, r(k) )
m
f (x) r(k)
1
u1 gu (x)
③ .(x, r (k) )
f (x)
m
r (k) u u 1
1 gu (x)
其中：gu (x) 0,u 1,2,...m
其中：gu (x) 0,u 1,2,...m
gu(x)0, u=1,2,…,p
适用性：当前迭代点的目标函数值较前一点是下降的，即满足 F(xk+1)<F(xk)
收敛条件：
• 边界点的收敛条件应该符合 K-T 条件；
• 内点的收敛条件为： xk1 xk 1
和

最优化方法4-1第四章 约束最优化方法-KKT条件

最优化方法4-1第四章 约束最优化方法-KKT条件
（I） x*为问题的局部最优解且 I*={i| c i (x*)=0, 1≤i≤m };
(II) f(x)和 c i (x)（i∈I*）在 x*点可微；
（III）c i (x)（i∈I\ I*）在 x*点连续
则 S={p∈Rn | ▽f(x*)Tp<0}
与 G={ p∈Rn |▽c i(x* )Tp>0, i∈I*} 的交是空集，
（iii）▽ci(x*)(i=1,2,…,l)线性无关；
则存在一组不全为零的实数 1*… l*使得
l
▽f(x*)- i *▽c i(x*)=0 1
定义 n+l 元函数：
l
L(x, )=f(x)- Tc(x)=f(x)- ici(x) i1 为 lagrange 函数，

1


1 2
x1 x2 1 0
的 KT 点为 x* (0, 3)T,相应乘子为* (1 ,0)T。
6
例 2：验证(2,1)T 为下面约束优化问题的 K-T 点.
min
f ( x1 , x2 ) ( x1 3)2 ( x2 2)2
恰好给出等式约束问题的一阶必要条件
及 c i(x*)=0，i=1, …,l
点（X*, *）称为 lagrange 函数 L（x, ）的驻点。
几何意义是明显的：考虑一个约束的情况：
-▽f(x*)
-▽f(x ) x
▽c(x )
c(x)
▽c(x*)
这里 x* 是局部最优解，
▽f(x*)与▽c(x*) 共线，
称 为 lagrange 乘子向量。
lagrange 函数的梯度为
▽L(x, )=(▽xL,▽ L)T

图的λ_4-最优性的邻域交条件

图的λ_4-最优性的邻域交条件
限制边 连通 度 ， 到最小 的这 种 ５称为 Ｇ的 Ａ 一 设 Ｆ是 图 Ｇ的一个 子 图 ， ａ Ｆ）表示恰 好有 一个端 点在 达 割． 令 （ Ｆ上 的边 的数 目． 义 ＝ （ ）＝ｍｉ ｛ （ ： Ｇ的 ｋ 定 Ｇ ｎ ａ Ｆ） Ｆ是 阶连通 子 图 ｝ 如 果 Ａ （ ． Ｇ）＝ （ ， Ｇ） 则称 Ｇ是 Ａ ． 最 优 的． 定义 Ｇ的阶 凡 Ｇ （ ）＝ｆ （ Ｉ 点 的邻域 为 Ⅳ（ ）＝ ｛， Ｅ∈Ｅ（ ｝对 Ａ， ， Ｇ） ， ／Ｖ ３ ｔ ： Ｇ） ． Ｂ ｃ Ｖ 定义 ［ ］ ， 为一 端 在 中， 一端在 Ｂ 中的边 的集 合． 另 设 ， ｙ为 （ ）的子集 ， Ｇ 如果 ［ ， ］ Ｇ的 ． ｙ为 限制边 割 ， 满足 Ｊ［ 且 ，
关 键 词 ： ；一 制 边 连 通 度 ； 一 性 图 ４限 最优
中图 分 类 号 ： １７ ５ ０ ５ ． 文 献 标 识 码 ： Ａ
Ｎｅ ｇ ｏ ｈｏ ｄ Ｉ ｔ ｒ ｅ ｔｏ ｎ ｔｏ ｓ ｆ ｒ 一 ｉ ｈｂ ｒ ｏ ｎ ｅ ｓ ｃ ｉ ｎ Ｃｏ ｄｉｉ ｎ ｏ Ｏｐｔｍ ａ ｉｙ ｏ ａ ｈ ｉ ｌｔ ｆ ａ Ｇｒ ｐ
Ｎ（ Ｊ ７ｈ ｌｓ ｎ ｉ ｅ “ｏ ｌ ｓ ｎａｔａ ｇ ， ｅ 入 一ｐｉ ａ．ｆｈ ｅ ｕｌｙＪ ） ） ／ ｏ ｄｅｈ ｒ ｒ）ｉ ｒ ｎｌ ｔ ｎＧｉ ４ｏ ｔ １Ｉｔｅｉ ｑ ａ ｔ Ｎ（ ｎ ＞ ｄａ ｔ ｚ ｅｏ ｉ ｅｈ ｓ ｍ ｎ ｉ
高敬 振 ， 丽 黄
（ 山东 师 范 大 学 数 学 科 学 学 院 ， 山东 济 南 ２０ １ ） ５０ ４
摘要 ： 文给 出了图的 Ａ － 本 ４最优性的邻域交条件 ： 图 Ｇ是阶数大于等于 １ 设 １的 Ａ － ４连通 图， Ｇ的任意一 对不 对 相邻顶点 ， 若 ｕ 均不在 三角形 中 ， ｉ “ ｎＮ（ ） ＞５ 若 ｕ或 在 三角形 中 ， Ｉ ｕ ｎＮ（ Ｉ ， ， ， 有 Ｎ（ ） ＂Ｉ ， ／ 有 Ⅳ（ ） ） ≥７ 则 Ｇ是 九一 最优的 ； Ｇ中任意一对不相邻顶点 ， 若 满足 １ Ｈ ｎⅣ（ ｌ ５ 任意一条边 满足 １ ） Ⅳ（ ） ） Ｉ ， ＞ Ｎ（ ｎＮ（ ） ｙＩ ≤２ 则 Ｇ也是 Ａ － ， ４最优的． 这些结果在网络可靠 性分析中有一定应用 ．

最优化计算方法(工程优化)第4章

最优化计算方法(工程优化)第4章
f (x*) 0, 2 f x 正定，则 x 为 f (x) 的严格局部极小
点。
如果 2 f x 负定，则 x 为 f (x) 的严格局部极大点。
无约束优化的最优性条件----凸优化的一阶条件
定理(一阶充要条件)
设 f : Rn R 是凸函数且在 x 处连续可微，则 x 为 f (x)的全局极小点的充要条件是 f (x*) 0.
f (x p) f (x)+f (x)T p o( )
P是什么方向时，函数值 f (x p) 下降最快？也就是
p是什么方向时，f (x)T p 取得最小值？
f (x)T p f (x) p cos(f (x), p)
当 cos(f (x), p) 1 时，f (x)T p 最小，最小值为
令 f x 0, 即：
利用一阶条件 求驻点
利用二阶条件 判断驻点是否 是极小点
x12 1 0
x22
2x2
0
得到驻点： 1 1 1 1
x1
0 ,
x2
2 ,
x3
0
,
x4
2
.
无约束优化的最优性条件
函数 f x 的Hesse阵：
2
f
x
2x1
0
0
2
x2
2
利用二阶条件 判断驻点是否 是极小点
2 0
0 2
的行列式小于0；
x1, x4是鞍点；
2
f
x2
2 0
0
2
是正定矩阵；
x2 是极小点；
2
f
x3
2 0
0 2
是负定矩阵；
x3 是极大点。
• 对某些较简单的函数，这样做有时是可行的；

最优化方法第四章(1)概要


（4.7）
D {x si ( x) 0, i 1,2, , 对于约束问题（4.7），设 x D 。若 x 使得 某个不等式约束有 si ( x ) 0 ，则该不等式约束 si ( x ) 0 称为是关于容许点 x 的起作用约束；否则，若 si ( x ) 0 ， 则该不等式约束称为是关于容许点 x 的不起作用约束。
*
*
G( x* ) S ( x* ) * * p C ( x ) ， 证 根据引理4.3，若 p G( x ) ，则 * * C ( x ) S ( x ) , 从而 G( x* ) C( x* ) 。又根据定理4.5，有 故必有 G( x* ) S ( x* ) 。
j 1
l
Lagrange 函数（4.4)的梯度是
x L L L
其中
x L f ( x ) j h j ( x )
l
L h1 ( x ), h2 ( x ),
最优性必要条件
j 1
hl ( x )
T
L( x* , 1* , 2* ,
C 是凸集，则称为凸锥。
显然，由 的集合
n 维向量 v1, v2 ,
m i 1
, vm 的全部非负组合构成
C {x x i vi , i 0}
是一个以原点为顶点的凸锥。由于这样的凸锥的边界是 （超）平面或直线，所以也称为由 v1 , v2 , , vm 张成的 凸多面锥。 n 是 D 定义4.3 设 R 中的非空集，且 x D。对于非零 n 向量 p R ，若存在 0 ，当 t (0, ) 时，必有 x tp D ，则 p 称为点 x 的容许方向向量，其方向 称为点 x 的容许方向。由点 x 的全部容许方向向量构成的 集合称为点 x 的容许方向锥，记作 C ( x* )

最优化：最优性条件


g i ( x ) T d 0 和 h j ( x ) T d 0, 即d LFD( x, D ) 注意：尽管 LFD( x, D )具有代数表示, 但上面的命题表明 LFD( x, D )是SFD( x, D )的一个子集,因此还不能用 LFD( x, D )替换定理 9.1.1中的SFD( x, D )
令 xk x k d k , 由定义9.1.2知, {xk } D.
为理解序列可行方向, 我们来看看它的几何解释：
xk
D
D
●
dk
●
xdຫໍສະໝຸດ xkdk●●
d
x
(a ) 点x在D内部
(b) 点x在D的边界上
序列可行方向实际 上就是可行方向
显然,
序列可行方向包含可行 方向和边界的切线方向
FD( x, D) SFD( x, D) (只需取d k d )
定义9.1.1 设x D, d R n .若存在数 0, 使得 x d D, (0, ], 则称d是D在x处的一个可行方向.
记x处所有可行方向的集合为FD( x, D)
若记x处函数f 的所有下降方向 集合为GD( x ) * 容易看出, 如果x 是(9.1)的最优 解, 则在该点不存在既下降又 可行的方向, 即
等式 h j ( x) 0 : h j ( x)T d 0
由上面分析可知：d FD( x, D ), 则有 h j ( x )T d 0, j E T g ( x ) d 0, i I 且 g i ( x ) 0 i
但反之不一定成立.
为方便起见, 记
可行域：D {x : g i ( x ) 0, i I ; h j ( x ) 0, j E}

无约束问题的最优化条件


即，在算法每次迭代中，求解信赖域子问题：
1 T min (d ) f ( xk ) g k d d Gk d 2
(k ) T
s.t
d hk
在信赖域算法中，信赖域半径 hk 采用自适应方式调整， 若
(k )
(d ) 与 f ( xk d ) 近似程度好，则 hk 尽可能取大，
T (0)
2)方向
d
(0)
(G( x )) f ( x ) 1, 3 2
(0) 1 (0)
T
3)求最优步长
x
(0) dFra bibliotek(0)代入目标函数得：
(1)
1 0 3 3 0 2 2
(0)
三、最速下降算法收敛性定理
定理 5 设 f C1 (一阶连续可微), S x f ( x ) f ( x0 )


有界，则由最速下降法得到的迭代点列 xk 具有如下性质： 1） 数列 f ( xk ) 严格单调下降； 2） xk 的任何极限点（聚点） x 都是 f ( x ) 的驻点，
T k 1
d k 0
5.3 牛顿法
自动化学院
一、牛顿迭代公式
牛顿法的基本思想是利用目标函数在当前迭代点 xk 处 的二次近似的极小点作为 f ( x ) 的近似极小点。
设 xk 是当前迭代点， 2 f ( xk ) 正定，
1 f ( x) f ( xk ) f ( xk ) ( x xk ) ( x xk )T 2 f ( xk )( x xk ) 2 1 (k ) T Q ( x) f ( xk ) f ( xk ) ( x xk ) ( x xk )T 2 f ( xk )( x xk ) 2

最优化方法(刘)第四章


阻尼牛顿法收敛定理
定理2: 设 f ( x) 二阶连续可微， 又设对任意的x0 ∈Rn , 存在常数m > 0, 使得 f ( x) 在 L ={x f (x) ≤ f (x0 )} 2 T 2 上满足： ∇ f ( x)µ ≥ m µ ,∀ ∈Rn , x∈L( x0 ) µ µ 则在精确线搜索条件下， 阻尼牛顿法产生的点列 {xk } 满足： (1) 当{xk } 是有限点列时， 其最后一个点为 f ( x) 的唯一极小点． (2)当{xk } 是无限点列时， 收敛到 f (x) 的唯一极小点．
) x0 = (9,1
T
g0 = ∇ ( x0 ) = (9,9) f
T
T 7.2 7.2 g0 g0 x = x0 − T g0 = 1 −0.8 g1 = −7.2 g0 G 0 g T 9×0.82 g1 g1 x2 = x − T g1 = 1 2 (−1 ×0.82 g1 G 1 g )
9 1 0 x = x0 −G g0 = − 1 1 0 9
1 − 0 −1
9 0 = = x* 9 0
牛顿法收敛定理
定理1: 设 f ( x) 二次连续可微， *是 f ( x) 的局 x 部极小点， f (x* ) 正定． 假定 f ( x) 的海色阵 ∇
gk →0 .
证明： 对于最速下降法， k = 0, 由以上定理立得． θ
收敛性分析
定理2: 设 f ( x) 二次连续可微， ∇2 f ( x) ≤ M, 且 其中 M是个正常数， 对任何给定的初始点 x0, 最速下降算法或有限终止， 或者lim f ( xk ) = −∞ ,
k→ ∞
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第4章 最优性条件§4.1 最优性条件的预备知识1．极小点的定义 无约束问题：1 (1)定义1（全局极小点）若存在nR x ∈使得n R x x f x f ∈∀≥ ),()(则称x 为问题(1)的全局极小点。

如果有x x R x x f x f n ≠∈∀>, ),()(则称x 为问题(1)的严格全局极小点。

定义2 （局部极小点）设nR x ∈，如果存在0>δ使得)( ),()(x N x x f x f δ∈∀≥则称x 为问题(1)的局部极小点。

如果有}/{)( ),()(x x N x x f x f δ∈∀>则称x 为问题(1)的严格局部极小点。

约束问题：)(min x f (2)s.t. m i x g i ,,1,0)( =≥l j x h j ,,1,0)( ==其中)( ),( ),(x h x g x f j i 都是定义在nR 上的实值连续函数，且至少有一个是非线性的。

称)(x f 为目标函数，)(x g i 为不等式约束函数,)( x h j 为等式约束函数。

(i) 如果0=m ，称(2)为等式约束优化问题； (ii) 如果0=l ，称(2)为不等式约束优化问题；(iii) 如果),,1)(( ),,,1)((l j x h m i x g j i ==都为线性函数，)(x f 是二次函数，则称(2)为二次规划问题。

若nR x ∈满足(2)的所有约束条件，称x 为(2)的可行点(或可行解)。

可行集（可行域）：⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧=≥=≥=.,,1,0)(,,,1,0)(l j x h m i x g x S j i 。

定义3 (全局极小点)设S x ∈使得 S x x f x f ∈∀≥ ),()(成立，则称x 为问题(2)的全局极小点。

如果有x x S x x f x f ≠∈∀>, ),()(成立，则称x 为问题(2)的严格全局极小点。

定义4 (局部极小点)设S x ∈，如果存在0>δ使得S x N x x f x f )( ),()(δ∈∀≥成立，则称x 为问题(2)的局部极小点。

如果有x x S x N x x f x f ≠∈∀>,)( ),()( δ成立，则称x 为问题(2)的严格局部极小点。

2. 内容安排■ 求全局极小点一般来说相当困难。

实际上可行的只是求一个局部(或严格局部)极小点。

故本课程后面所指极小点，通常指求局部极小点。

■ 仅当问题为凸规划(即目标函数)(x f 为凸函数，不等式约束函数m i x g i ,,1 ),( =-为凸函数，等式约束函数l j x h j ,,1 ),( =为线性函数)时，局部极小点才是全局极小点。

■ 按定义验证最优解是不可能的。

因此有必要给出只依赖于在x 处目标函数和约束函数信息的、且与定义等价的条件。

这样的条件称其为最优性条件，它们是各种基于梯度算法的理论基础。

§4.2 无约束问题的最优性条件考虑无约束问题(1)，回忆当R x ∈时，即单变量函数极值问题的最优性条件： 必要条件：若R x ∈且)(x f 在x 处取到极值，如果)(x f 在x 可微，则x 为)(x f 的驻点，即满足0)('=x f 。

充分条件：若R x ∈且)(x f 在x 处可微，如果0)('=x f 且0)(''>x f ，则)(x f 在x 处取到极小值；如果0)('=x f 且0)(''<x f ，则)(x f 在x 处取到极大值。

x x*3：x 为全局极大点； *4：x 为严格局部极大点。

定理1 (一阶必要条件)：设nR x ∈为函数)(x f 在nR 的局部极小点，且)(x f 在x 可微，则0)(=∇x f 。

证明 利用§4.0中的定理1可证。

几何解释：若x 为局部极小点，则)(x f 在x 处不能有下降方向。

从而，当0)(≠∇x f 时，)(x f ∇－为)(x f 在x 处的一个下降方向，故若n R x ∈为函数)(x f 在n R 的极值点，必有0)(=∇x f 。

定理2 (二阶必要条件)：设nR x ∈为函数)(x f 在nR 的局部极小点，且)(x f 在x 二阶可微，则有0)(=∇x f ，且)(2x f ∇半正定证明：利用)(x f 在x 的二阶Taylor 展开及局部极小点的定义可得。

几何解释：由x 为局部极小点及0)(=∇x f 所确定。

定理3 (二阶充分条件)：设)(x f 是定义在nR 上的二次可微函数，如果0)(=∇x f ，且)(2x f ∇正定，则x 为函数)(x f 在n R 的严格局部极小点。

证明 利用)(x f 在x 的二阶Taylor 展开及正定矩阵的定义可得。

注：满足0)(=∇x f 的点称为)(x f 的平稳点或驻点。

驻点可能是极大值点，也可能是极小值点，也可能不是极值点。

但若目标函数为凸函数，则驻点就是全局极小值点；若目标函数为凹函数，则驻点就是全局极大值点。

定理4 (凸充分性定理)：设)(x f 是定义在nR 上的凸函数，如果0)(=∇x f ，则x 为函数)(x f 在nR 上的全局极小点。

(一阶必要条件＋凸性) 证明 利用可微凸函数的一阶判别条件和0)(=∇x f 易证。

例：利用极值条件求解12232313131)(min 2x x x x x f Rx --+=∈ 解：1211-=∂∂x x f ，22222x x x f -=∂∂ 令0)(=∇x f ，即0121=-x ，02222=-x x 。

得到驻点：⎥⎦⎤⎢⎣⎡=01)1(x ，⎥⎦⎤⎢⎣⎡=21)2(x ，⎥⎦⎤⎢⎣⎡-=01)3(x ，⎥⎦⎤⎢⎣⎡-=21)4(xHesse 矩阵： ⎥⎦⎤⎢⎣⎡-=∇22002)(212x x x f在点)4()3()2()1(,,,xx x x 处Hesse 矩阵：⎥⎦⎤⎢⎣⎡-=∇2002)()1(2x f ，⎥⎦⎤⎢⎣⎡=∇2002)()2(2x f ⎥⎦⎤⎢⎣⎡--=∇2002)()3(2x f ，⎥⎦⎤⎢⎣⎡-=∇2002)()4(2x f )()1(2x f ∇和)()4(2x f ∇不定，根据定理2，)4()1(,x x 不是极小点；)()3(2x f ∇负定，)3(x 是极大点；)()2(2x f ∇正定，根据定理3，)2(x是局部极小点。

§4.3 约束问题的极值条件4.3.1 一阶最优性条件引入记号：},,1{l E =――等式约束指标集},,1{m I =――不等式约束指标集 定义1: 对(2)的任何可行解S x ∈~，若I i x g i∈=,0)~(，称第i 个不等式约束在x ~处是紧的，称集合},0)~(|{)~(I i x g i x I i ∈==为不等式约束中在x ~处的紧约束指标集。

称 )~()~(x I E x A =是在x ~处的积极集合(有效约束指标集，或紧约束指标集)。

可行集上一点是否为局部极小点, 取决于目标函数在该点以及附近其它可行点上的值。

可行方向在推导最优性条件中起十分重要的作用。

各种可行方向的定义:定义2: 设S x ∈，nR d ∈≠0，如果存在0>δ，使得S d x ∈+λ，),0( δλ∈∀则称d 是集合S 在x 处的可行方向。

S 在x 处的可行方向的集合记为),(S x FD 。

问题：问),(n R x FD ？(}0/{),(n n R R x FD =)例1: 考虑集合}|{21221x x R x S =∈=，}|{21222x x R x S ≥∈=在点Tx )0 ,0(=处的可行方向集，则∅=),(1S x FD}0,|),{(),(21212>∈=d R d d d S x FD定义3: 设S x ∈，nR d ∈，如果E j x h d j T ∈=∇ ,0)(; )( ,0)(x I i x g d i T ∈≥∇则称d 是集合S 在x 处的线性化可行方向。

S 在x 处的线性化可行方向的集合记为),(S x LFD 。

定义4: 设S x ∈，nR d ∈，如果存在序列}{k d 和}{k δ，其中0>k δ，使得S d x k k ∈+δ，k ∀且有d d k→和0→k δ，则称d 是集合S 在x 处的序列可行方向。

S 在x 处的所有序列可行方向的集合记为),(S x SFD 。

xx x x d kk k --=∞→lim注：可行方向为几何概念，线性化可行方向为代数概念，序列可行方向是基于极限定义的几何概念。

例2 }|{2122x x R x S =∈=，取T x )0 ,0(=，则∅=),(S x FD}|)0,{(),(11R d d S x LFD ∈=}|)0,{(),(11R d d S x SFD ∈=上述定义的三个可行方向集有如下关系： 引理1 设S x ∈，如果所有的约束函数在x 处可微，则有),(),(),(S x LFD S x SFD S x FD ⊆⊆。

注：该结论条件可以放宽为)()(x I i x g i ∈，，)( x h j ，l j ,,1 =在x 处可微，其余不等式约束函数)()(x I i x g i ∉，在x 处连续。

引理2 (几何最优性条件－必要)：设S x ∈是(2)的局部极小点，如果)(x f 在x 处可微，则必有),( ,0)(S x SFD d x f d T ∈∀≥∇证明 利用目标函数)(x f 在k k d x δ+处的一阶Taylor 展开，序列可行方向的定义及局部极小点的定义可证。

注：该定理也可表述为：S x ∈是(2)的局部极小点，则∅=<∇),(}0)(|{S x SFD x f d d T 。

第一个集合表示目标函数在x 处的一个下降方向的子集，即该下降方向的子集与序列可行方向无公共元素。

定理1：设S x ∈是(2)的局部极小点，如果目标函数和所有的约束函数在x 处可微，且),(),(S x LFD S x SFD = (3)则必存在I i w i ∈ ,和E j v j ∈ ,使得0)()()(11=∇-∇-∇∑∑==lj j j mi i i x h v x g w x f （梯度条件）（4a ） 0)( ,0=≥x g w w i i i ，m i ,,1 = （互补松弛条件）（4b ）该定理的另外一种等价表示（基于该等价表示可以看出K-T 最优性条件的几何意义）： 定理'1: 设S x ∈是(2)的局部极小点，如果目标函数和所有的约束函数在x 处可微，且),(),(S x LFD S x SFD =则必存在)( ,0x I i w i ∈≥和E j v j ∈ ,使得0)()()(1)(=∇-∇-∇∑∑=∈lj jjx I i iix h v x g w x f （5）证明思路：(4a)-(4b)由Kuhn ，Tuck （1951）给出，一般称为K-T 条件，因Karush （1939）也类似地考虑了约束优化的最优性条件，所以也称K-K-T 条件。