- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
45 13
20 13
g 2 ( x1 , x 2 )
45 13
2
20 13
47
5 13
4 0.34 0
第六章
6.1 Kuhn-Tucker 条件
三、一般约束问题的Kuhn-Tucker 条件
min f ( x) ( fgh) s.t. g i ( x) 0 i 1,2, , m j 1,2, , l h j ( x) 0
第
六
章
约束最优化方法
第六章 约束最优化方法
问题 min f(x) 分量形式略 (fgh) s.t. g(x) ≤0 h(x)=0 约束集 S={x|g(x) ≤0 , h(x)=0}
6.1 Kuhn-Tucker 条件
一、等式约束性问题的最优性条件： 考虑 min f(x) (fh) s.t. h(x)=0 回顾高等数学中所学的条件极值： 即 问题 求z=f(x,y)极值 min f(x,y) 在ф(x,y)=0的条件下。 S.t. ф(x,y)=0 引入Lagrange乘子：λ Lagrange函数 L(x,y;λ)= f(x,y)+ λ ф(x,y)
ㄡ ▽h(ㄡ )
最优性条件即：
▽h(x*)
f ( x*) j h j ( x*)
* j 1
h
6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： 考虑问题 min f(x) (fg) s.t. gi(x) ≤0 i=1,2, …,m 设 x*∈S={x|gi(x) ≤0 i=1,2, …,m} 令 I={i| gi(x*) =0 i=1,2, …,m} 称I为 x*点处的起作用集（紧约束集）。 如果x*是l.opt. ,对每一个约束函数来说，只有当它是起作用约 束时，才产生影响，如：
6.2 既约梯度法
一、解线性约束问题的既约梯度法
Amn , 秩A m, b R
m
多面体同( LP )的S .
2 S的每个极点都有m个正分量。（B b 0） 3、既约梯度及搜索方向： x S , 存在分解A [ B, N ], Bmm 非奇异， xB x x N 相应 使x B 0, x N 0 x B 基变量，x N 非基变量
第六章
6.1 Kuhn-Tucker 条件
二、不等式约束问题的Khun-Tucker条件： （续） 可能的K-T点出现在下列情况： ①两约束曲线的交点：g1与g2,g1与g3,g1与g4,g2与g3,g2与g4,g3与 g4。 ②目标函数与一条曲线相交的情况： g1，g2, g3, g4 对每一个情况求得满足(1)~(6)的点(x1,x2)T及乘子u1,u2,u3,u4,验 证当满足可得，且ui≥ 0时，即为一个K-T点。 下面举几个情况： ● g1与g2交点：x=(2,1)T∈S ,I={1,2} 则u3=u4=0 解
第六章
例
g3=0 x2
▽g2(x*)
-▽f(x*) (3,2)T
2 1
x*
▽g1(x*)
1
2 3 g1=0
4
g4=0 x1 g2=0
6.1 Kuhn-Tucker 条件 二、不等式约束问题的Khun-Tucker条件： （续）
在x 点 g 1 ( x1 , x 2 ) 0 g 2 ( x1 , x 2 ) 0
x1 x 2 5 0 g 1与g 3交点： x1 0 5) 5)
T T
得x (0,
5)
T
(0, (0,
S , 故不是K T点；
S , 不满足g 2 0, 故不是K T点。
T
●
g 3 , g 4 交点 : x (0,0)
S
I {3,4}故u1 u 2 0
定理： 问题( fgh)，x S {x | g ( x) 0, h( x) 0}, I为起作用集。
设g i ( x)(i I )在x 可微, g i ( x)(i I )在x 连续，h j，（j 1,2, , l） 在x 的某邻域内连续可微。（CQ, 约束规格）。 向量组{，g i ( x )(i I ), , h1 ( x ), , hl ( x )}线性无关。
v j h j ( x ) 0
j 1
l
如果还有g i ( x )(i I )在x 亦可微，那么
m l f ( x ) u i g i ( x ) v j h j ( x ) 0 i 1 j 1 ui 0 i 1,2, , m u i g i ( x ) 0
第六章
如果x
6.1 Kuhn-Tucker 条件
三、一般约束问题的Kuhn-Tucker 条件 (续)
l .opt .那么u i 0, i I , v j R, j 1,2, , l f ( x )
u i g i ( x )
iI
2( x1 3) 2u1 x1 u 2 0 2( x 2 2) 2u1 x 2 2u 2 0 故x (2,1) 是K T点。
T
得u1
1 3
, u2
2 3
0
第六章
6.1 Kuhn-Tucker 条件
二、不等式约束问题的Khun-Tucker条件： （续） ● 2 2
第六章
6.-Tucker条件： （续）
m f ( x ) u i g i ( x ) 0 i u i 0, i 1 2, , m , u i g i ( x) 0
2( x1 3) u1 2 x1 u 2 u 3 0 (1) 2( x 2 2) u1 2 x 2 2u 2 u 4 0 ( 2) u1 , u 2 , u 3 , u 4 0 2 2 u1 ( x1 x 2 5) 0 (3) u ( x 2 x 4) 0 ( 4) 2 1 2 u 3 x1 0 (5) 6个方程6个未知量 u 4 x 2 0 (6)
第六章
6.1 Kuhn-Tucker 条件
一、等式约束性问题的最优性条件： (续) 若(x*,y*)是条件极值，则存在λ* ，使 fx(x*,y*)+ λ* фx (x*,y*) =0 fy(x*,y*)+ λ* фy(x*,y*) =0 Ф (x*,y*)=0 推广到多元情况，可得到对于(fh)的情况： min f(x) 分量形式： s.t. hj(x)=0 j=1,2, …,l 若x*是(fh)的l.opt. ,则存在υ*∈ Rl使
g2(x)=0 x* g1(x)=0
第六章
g1(x*)=0, g1为起作用约束
第六章
6.1 Kuhn-Tucker 条件
二、不等式约束问题的Khun-Tucker条件： （续） 特别 有如下特征：如图
-▽f(ㄡ ) X* -▽f(x*)
▽g(x*)
▽g(ㄡ )
在x* ： ▽f(x*)+u* ▽g(x*)=0 u*>0 要使函数值下降，必须使g(x)值变大，则 在ㄡ 点使f(x)下降的方向（- ▽f(ㄡ ) 方向）指向约束集合内 部，因此ㄡ不是l.opt. 。
2(0 3) u 3 0 解 得u 3 6 0, u 4 4 0 2(0 2) u 4 0 故非K T点.
第六章
6.1 Kuhn-Tucker 条件
二、不等式约束问题的Khun-Tucker条件： （续） ●
目标函数f ( x)与g 1( x ) 0相切的情况： I {1}, 则u 2 u 3 u 4 0 2( x1 3) 2 x1u1 0 解2( x 2 2) 2 x 2 u1 0 2 2 x1 x 2 5 0 故均不是K T点 得( , )S
f ( x )
*
j 1
l
*
h j ( x ) 0 j
*
矩阵形式：
f ( x
*
)
h( x x
*
)
*
0
第六章
6.1 Kuhn-Tucker 条件
一、等式约束性问题的最优性条件： (续) 几何意义是明显的：考虑一个约束的情况：
-▽f(x*)
-▽f(ㄡ )
h(x)
这里 x* ---l.opt. ▽f(x*)与 ▽h(x*) 共线，而ㄡ非l.opt. ▽f(ㄡ )与▽h(ㄡ )不共线。
第六章
6.1 Kuhn-Tucker 条件
二、不等式约束问题的Khun-Tucker条件： （续） 定理（最优性必要条件）： （K-T条件） 问题(fg), 设S={x|gi(x) ≤0},x*∈S,I为x*点处的起作用集，设f, gi(x) ,i ∈I在x*点可微， gi(x) ,i I在x*点连续。 向量组{▽gi(x*), i ∈I}线性无关。 如果x*----l.opt. 那么， u*i≥0, i ∈I使
* 1 3
u1
*
1 3
u2
* 2 3
2 3
使
g 1 ( x )
g 2 ( x ) 0
用K-T条件求解：
2( x1 3) 2 x1 , g 1 ( x ) f ( x ) 2( x 2) 2x 2 2 1 0 , g 4 g 3 ( x ) 0 1 1 , g 2 ( 2) 2
f ( x )
*
u i g i ( x ) 0
