min f(r) 定理1: St.g(x)≤0 给定点x∈Q,记点x的积极约束指标集为I(x)。给定向量d, 如果对任意的∈I(x)有vg(x)d<0,则d是点x的可行方向。 证明:令x'=x+td,t>0。则对任意的i∈I(x),有 8, (x)=g, (x)+tvg (x)d+o( td) =tvg(x)d+o( 5<o x∈Q,即d为可行方向。 定义4可行下降方向 设点x∈旦给定向量d,如果d既是点x处的可行方向, 又是该点的下降方向,则称d为点x处的可行下降方向
6 令 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 证明: 定理1: 定义4: 可行下降方向 如果对任意的 有 则 是 点 的可行方向。 给定点 记 点 的积极约束指标集为 。给定向量 ， i I x g x d d x x Q x I x d T i ( ) ( ) 0, , ( ) min ( ) . . 0 f x s t g(x)
定理2: min f(r) 给定点xeQ,记点x的积极约束指标集为(x)。给定(s.g(x)≤0 向量d,如果d满足 g(x)d<0i∈I(x) vf(x)d<0 则向量d是点x处的可行下降方向。 证略 ③极值点的必要条件: 定理3:设x*∈Q,I(x)是其积极约束指标集。 f(x)和g;(x)(i∈I(x)在点x*处可微, g;(x)(igⅣ(x)在点x处连续。 如果x*是约束极值问题1)的局部极小点,则在 点x处没有可行下降方向
7 则向量 是 点 处的可行下降方向。 向 量 ，如果 满 足 给定点 记 点 的积极约束指标集为 。给定 d x f x d g x d i I x d d x Q x I x T T i ( ) 0 ( ) 0 ( ) , ( ) 设 x*Q，I(x*)是其积极约束指标集。 定理2: 定理3: 证略 ③极值点的必要条件: f (x)和gi (x)(i I(x*))在点x*处可微， gi (x)(i I(x*))在点x*处连续。 点 处没有可行下降方向。 如 果 是约束极值问题 的局部极小点，则在 * * (1) x x min ( ) . . 0 f x s t g(x)
定义5.设ScR",称S为凸集当且仅当Vx1,x2ES及∈0,1都有 x1+(1-1)x2∈S 定义6.设x,x,…,x,∈R",称x是x,x,…x的一个凸组合当且仅当存在 ∑1=1,20使x=∑1x。 定义7.设S∈R",称∫是S上的凸函数当且仅当对x,x2∈S及 ∈|0,都有 ∫(x1+(1-1)x2)≤f(x1)+(1-A)f(x2) 严格凸组合严格凸 线性组合 定理若八以)是S上的凸函数,则ce∈R,水平集X=(sS∫(xsc是凸集 若八∞)是凸函数,S是凸集,min∫(x)为凸规划。凸规划的局部解是整体解! xES S={xe1:(x)s0;=1…,c(x)=00=p+,…+q 般要求c1(x)当=1,2…p时为凸函数,当p+1,+时为线性函数。 8
8 定义 5. 设 n S R ，称 S 为凸集当且仅当 1 2 x x S , 及 [0,1]都有 1 2 x x S + − (1 ) 定义 6. 设 1 2 , , , n p x x x R ，称 x是 1 2 , , , p x x x 的一个凸组合当且仅当存在 1 1, 0 l i i i = = 使 1 l i i i x x = = 。 定义 7. 设 n S R ，称 f 是 S 上的凸函数当且仅当对 1 2 x x S , 及 [0,1]都有 1 2 1 2 f x x f x f x ( (1 ) ) ( ) (1 ) ( ) + − + − 严格凸组合 严格凸 线性组合 定理 若 f(x)是 S 上的凸函数，则 c R，水平集 X x S f x c = ( ) 是凸集. min ( ) x S f x 若f(x)是凸函数，S是凸集， 为凸规划。 ( ) 0, 1,..., , ( ) 0, 1,..., n S x R c x i p c x j p p q = = = = + + i i 一般要求 ( ) i c x 当i=1,2,…,p时为凸函数，当i=p+1,…,p+q时为线性函数。 凸规划的局部解是整体解！
82∫(x)a2f(x) 2f(x) C, o df(x) a-f(r)af( 82∫(x) axax. a ax. a Vf(x)= ax2 vf(r) df(x) a-f(r)af(x a-f(r) axax 定理(凸函数的一阶充要条件)若fx)在S上可微,则f(x)是凸函 数当且仅当 ∫(x)≥∫(x)+Vf(x)(x-x),Vx∈S 定理(凸函数的二阶充要条件)设∫:S→R二阶连续可导,则 I)厂是S上的凸函数的充要条件是∫的Hese矩阵vf(x)在S上是半正定的。 2)当vf(x在S上是正定矩阵时,∫是S上的严格凸函数。(注:逆命题不成立)9
9 2 2 2 2 1 1 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 ( ) ( ) ( ) .... ( ) ( ) ( ) ... ( ) ( ) ( ) ( ) n n n n n f x f x f x x x x x x f x f x f x x x x x x f x f x f x f x x x x x x = 1 2 ( ) ( ) ( ) ( ) n f x x f x f x x f x x = 定理(凸函数的一阶充要条件) 若 f(x)在 S 上可微，则 f(x)是凸函 数当且仅当 ( ) ( ) ( ) ( ) T f x f x f x x x + − ， x S 定理(凸函数的二阶充要条件) 设 f : S R 二阶连续可导，则 1)f 是 S 上的凸函数的充要条件是 f 的 Hesse 矩阵 ( ) 2 f x 在 S 上是半正定的。 2)当 ( ) 2 f x 在 S 上是正定矩阵时，f 是 S 上的严格凸函数。(注:逆命题不成立)
最优性条件 无约束规划minf(x) x∈R 定理:可微函数解的必要条件:x*是局部解则:V(x)=0.x是驻点(稳定点) 可微凸函数解的充要条件:x是整体极小解当且仅当Vf(x)=0 y=f(r) qp(t)=∫(x*+tdO 10
10 定理：可微函数解的必要条件：x*是局部解,则： = f x( *) 0. 最优性条件 min ( ) n x R f x 无约束规划 x*是驻点(稳定点) 可微凸函数解的充要条件：x*是整体极小解当且仅当 = f x( *) 0. ( ) ( * ) t f x td = +