约束极值问题的最优性条件 约束极值问题 最优性条件
约束极值问题的最优性条件 一 .约束极值问题 二.最优性条件
约束极值问题 min f(r) h2(x)=0i=1,2,…,m st g1(x)≥0j=1,2, 记l(x)=((x),h2(x),…,bn(x), g(x)=(g(x),g2(x),…,g(x)) 则约束极值问题可记为minf(x) h(x)=0 S。t g(x)≥0 令Q={x|(x)=0,g(x)≥0},称Q为此约束极值问题 的可行域
一 .约束极值问题 = = = g x j l h x i m s t f x j i ( ) 0 1,2, , ( ) 0 1,2, , . . min ( ) 令Q = { x|h(x) = 0, g(x) 0}, 称Q为此约束极值问题 ( ) ( ( ), ( ), , ( )) , ( ) ( ( ), ( ), , ( )) , 1 2 1 2 T l T m g x g x g x g x h x h x h x h x = 记 = 则约束极值问题可记为 = ( ) 0 ( ) 0 . . min ( ) g x h x s t f x 的可行域
(x)≥0 h(x)=0分1-1(x)≥0 ∴约束极值问题也可记为 min f(x) St.g(x)≥0
− = ( ) 0 ( ) 0 ( ) 0 h x h x h x i i i 约束极值问题也可记为 . . ( ) 0 min ( ) s t g x f x
最优性条件 min f(r) st.g(x)≥0 可行域为Q={x|g(x)≥0} 1可行方向和积极约束 可行方向:设x"∈Q,d为一个向量。如果存在实数元>0, 使得对任意的∈[0,A有x"+∈Q,则称d为x处的 个可行方向。 g1(x)=0 g2(x)=0
二.最优性条件 一个可行方向。 使得对任意的 有 则 称 为 处 的 可行方向：设 ，为一个向量。如果存在实 数 ， 0 0 0 [0, ] , 0 x d Q d x x Q d + g1 (x) = 0 g2 (x) = 0 0 x 1 x 1 d 1 d 2 d 2 d 1.可行方向和积极约束 . . ( ) 0 min ( ) s t g x f x (1) 可行域为Q = { x| g(x) 0}
积极约束设点x∈Q,对于不等式约束g;(x)≥0,如果 g;(x)=0,则称g(x)≥0是点x处的积极约束 记I(x)={ig;(x)=0,1≤i≤l},称I(x)为点x处的积极 约束指标集。 例设g1(x)=x2-√2x2≥0,g2(x)=1-x2-x2≥0, √2 g3(x)=x1≥0。令x=( 求点x的积极约束 指标集。 解:、210, g2(x)=1-()2-(
则称 是点 处的积极约束。 积极约束：设点 对于不等式约束 ，如果 g x g x x x Q g x i i i ( ) 0, ( ) 0 , ( ) 0 = 约束指标集。 记 I(x) = {i| gi (x) = 0,1 i l},称 I(x)为 点x处的积极 指标集。 。令 ，求点 的积极约束 例设 g x x x x g x x x g x x x T ) 2 2 , 2 2 ( ) 0 ( ( ) 2 0, ( ) 1 0, 3 1 2 2 2 2 1 2 1 2 1 = = = − = − − 解： ) 0, 2 2 2 ( 2 2 ( ) 2 g1 x = − = ) 0, 2 2 ) ( 2 2 ( ) 1 ( 2 2 g2 x = − − =
g3(x)= 2 (x)=0/g;(x)= 83(x)=0 如何判断一个向量是否是可行方向? 定理1给定点x∈Q,记点x的积极约束指标集为(x)。给定 向量d,如果对任意的i∈I(x)有vg(x)d>0,则d是点x的 可行方向
0。 2 2 ( ) g3 x = I(x) = {1,2}。 1 x 2 x O g2 (x) = 0 g1 (x) = 0 g3 (x) = 0 x 如何判断一个向量是否是可行方向？ 可行方向。 向 量 ，如果对任意的 有 则 是 点 的 定 理 给定点 记 点 的积极约束指标集为 。给定 d i I x g x d d x x Q x I x T i ( ) ( ) 0, 1 , ( )
证明:令x=x+td,t>0。则对任意的i∈I(x),有 8, (x=8,(x)+tVg, (x)d+o( td) tVg, (x)d+o(l td o >0 x'∈Q,即d为可行方向。 可行下降方向:设点x∈Q,给定向量d,如果d既是点x处 的可行方向,又是该点的下降方向,则称d为点x处的可 行下降方向
证明：令 x'= x + t d ,t 0。则对任意的i I(x),有 ( ') ( ) ( ) (|| || ) 2 g x g x t g x d o td T i = i + i + ( ) (|| || ) 2 t g x d o td T = i + 0 x'Q,即d为可行方向。 行下降方向。 的可行方向，又是该点的下降方向，则称 为 点 处的可 可行下降方向：设 点 ，给定向量 ，如果 既是点 处 d x x Q d d x
定理2给定点x∈Q,记点x的积极约束指标集为I(x)。给定 向量d,如果d满足 vg(x)d>0i∈I(x) Vf(x)d<o 则向量d是点x处的可行下降方向。 极值点的必要条件: 定理3设x*∈Q,I(x)是其积极约束指标集。f(x)和g;(x) (∈I(x))在点x处可微,g(x)(i运I(x*)在点x*处连 续。如果x*是约束极值问题①)的局部极小点,则在 点x处没有可行下降方向
则向量 是 点 处的可行下降方向。 向 量 ，如果 满 足 定 理 给定点 记 点 的积极约束指标集为 。给定 d x f x d g x d i I x d d x Q x I x T T i ( ) 0 ( ) 0 ( ) 2 , ( ) 点 处没有可行下降方向。 续。如果 是约束极值问题（）的局部极小点，则在 在 点 处可微， 在 点 处 连 定 理 设 ， 是其积极约束指标集。 和 * * 1 ( ( *)) * ( )( ( *)) * 3 * ( *) ( ) ( ) x x i I x x g x i I x x x Q I x f x g x i i 极值点的必要条件：
2.K-T条件(库恩一塔克条件) 设点x*是约束极值问题()的局部极小点, I(x*)是其积极约束指标集 则由定理2可知,不存在向量d,使下式成立 ∫vg(x)d>0i∈I(x) IVf(d<o 分析 (1)如果I(x)中只有一个指标,不妙设g(x)为积极约束。 则不存在向量d使得 ∫vf(x*)yd<0 Vg,(x*) 成立
2. K −T 条件（库恩− 塔克条件） 是其积极约束指标集。 设 点 是约束极值问题（）的局部极小点， ( *) * 1 I x x 分析： 。 则由定理 可知，不存在向量 ，使下式成立 ( ) 0 ( ) 0 ( ) 2 f x d g x d i I x d T T i (1) 如果I(x*)中只有一个指标，不妨设g1 (x)为积极约束。 成立。 则不存在向量 使得 ( *) 0 ( *) 0 g1 x d f x d d T T
g1(x)=0 vf(ra) 则有Vf(x*)=λVg(x),>0。 即Vf(x*)-Vg1(x*)=0
g1 (x) = 0 x * ( *) g1 x − f (x*) 则有 f (x*) = g1 (x*), 0。 即 f (x*)− g1 (x*) = 0