第7章最优性条件 §7.1无约束问题的极值问题 7.1.1 无约束极值问题 考虑非线性规划问题： min f(x),x∈R” 其中f(x)是定义在R"上的实函数.这个问题是求f(x)在n 维欧氏空间中的极小点，称为无约束极值问题.这是一个古典的 极值问题，在微积分学中已经有所研究，那里给出了定义在几何 空间上的实函数极值存在条件，这一节只是把已有理论在n维欧 氏空间中加以推广
第7章 最优性条件 §7.1 无约束问题的极值问题 考虑非线性规划问题: min ( ), n f x x R 其中 是定义在 上的实函数.这个问题是求 在n 维欧氏空间中的极小点,称为无约束极值问题.这是一个古典的 极值问题,在微积分学中已经有所研究,那里给出了定义在几何 空间上的实函数极值存在条件,这一节只是把已有理论在n 维欧 氏空间中加以推广. n f (x) R f (x) 7.1.1 无约束极值问题
7.1.2必要条件 为研究函数f(x)的极值条件，先介绍一个定理，它在后面的证 明中将要多次用到 定理7.1.1 设函数f(x)在点x可微，如果存在方向d, 使f(x)Id0，使得对每个九∈(0，δ)，有 f(+九d)<f() 定理7.1.2 设函数f(x)在点x可微，若x是局部极小点， 则梯度Vf()=0. 定理7.1.3 设函数(x)在点x二次可微，若x是局部极小 点，则梯度f()=0,并且Hessian矩2f()是半正定的
7.1.2 必要条件 为研究函数 的极值条件,先介绍一个定理,它在后面的证 明中将要多次用到. f (x) 定理7.1.1 设函数 在点 可微,如果存在方向 , 使 ,则存在数 ,使得对每个 ,有 f (x) x d f (x) d 0 T 0 (0, ) f x d f x ( ) ( ). + 定理7.1.2 设函数 在点 可微,若 是局部极小点, 则梯度 f (x) x x = f x( ) 0. 定理7.1.3 设函数 在点 二次可微,若 是局部极小 点,则梯度 ,并且Hessian矩阵 是半正定的. f (x) x x f (x) = 0 ( ) 2 f x
7.1.3二阶充分条件 局部极小点的二阶充分条件： 定理7.1.4设f(x)在点X处二次可微，若梯度f()=0,且 Hessian矩阵V2f()正定，则X是局部极小点. 7.1.4 充要条件 前面几个定理分别给出无约束极值的必要条件和充分条件 这些条件都不是充要条件，而且利用这些条件只能研究局部极小 点.下面在函数凸性的假设下给出全局极小点的充要条件 定理7.1.5 设f(x)是定义在Rn上的可微凸函数x∈R” 则X为全局极小点的充要条件是Vf()=0·
7.1.3 二阶充分条件 局部极小点的二阶充分条件： 定理7.1.4 设 在点 处二次可微,若梯度 ,且 Hessian矩阵 正定,则 是局部极小点. f (x) x f (x) = 0 ( ) 2 f x x 7.1.4 充要条件 前面几个定理分别给出无约束极值的必要条件和充分条件, 这些条件都不是充要条件,而且利用这些条件只能研究局部极小 点.下面在函数凸性的假设下,给出全局极小点的充要条件. 定理7.1.5 设 是定义在 上的可微凸函数, , 则 为全局极小点的充要条件是 . f (x) n R n x R x f (x) = 0
例1利用极值条件解下列问题： mmfx)(k2-}+x好+x号-2x 例2 利用极值条件解下列问题： 3 -x 3
( ) 1 2 2 2 1 2 2 min f (x)= x1 −1 + x + x − 2x 例1 利用极值条件解下列问题: 例2 利用极值条件解下列问题: 3 3 2 1 2 2 1 1 1 min ( ) 3 3 f x x x x x = + − −
§7. 2约束极值问题的最优性条件 7.2.1约束极值问题 有约束的极值问题一般表示为 min f(x) x∈R" s.t 8,(x)≥0i=1.,m (7.2.1) h(x)=0j=1,,1 其中g,(x)≥0称为不等式约束，h,(x)=0称为等式约束集合 5=1 (x)≥0，i=1,,m (7.2.2) h,(x)=0j=1,,1 称为可行集或可行域
§7.2 约束极值问题的最优性条件 7.2.1 约束极值问题 有约束的极值问题一般表示为 其中 gi (x) 0 称为不等式约束, hj (x) = 0 称为等式约束.集合 min ( ) . ( ) 0 1,..., ( ) 0 1,..., n i j f x x R s t g x i m h x j l = = = (7.2.1) = = = = h x j l g x i m S x j i ( ) 0, 1,..., ( ) 0, 1,..., | (7.2.2) 称为可行集或可行域
由于在约束极值问题中，自变量的取值问题中，自变量的取值 受到限制，目标函数在无约束情况下的平稳点（驻点）很可能不在 可行域内，因此一般不能用无约束处理约束问题！ 7.2.2 可行方向与下降方向 为增加直观性，我们先给出最优性的几何条件，然后在给出它 们的代数表示.为此引入可行方向与下降方向的概念 我们先定义下降方向. 定义7.2.1设f(x)是定义在R"上的实函数，x∈R”,d是 非零向量.若存在数6>0，使得对每个入∈(0,6)，都有 f(+d)<f(x) 则称d为函数f(x)在x处的下降方向
由于在约束极值问题中,自变量的取值问题中,自变量的取值 受到限制 , 目标函数在无约束情况下的平稳点(驻点)很可能不在 可行域内 , 因此一般不能用无约束处理约束问题. 7.2.2 可行方向与下降方向 为增加直观性,我们先给出最优性的几何条件,然后在给出它 们的代数表示.为此引入可行方向与下降方向的概念. 我们先定义下降方向. 定义7.2.1 设 是定义在 上的实函数, , 是 非零向量.若存在数 ,使得对每个 ,都有 f (x) n R n x R d 0 (0, ) f (x + d) f (x) 则称 d 为函数 f (x)在 x 处的下降方向
如果f(x是可微函数，且f(x)d0，使得对每一个九∈(0,6)，都有 x+d∈S 则称d为集合S在x的可行方向. 其中l”表示闭S 即 的闭包
如果 f (x) 是可微函数,且 ,根据定理7.1.1,显然 为 在 处的下降方向.这时记作 f (x) d 0 T d f (x) x 下面定义可行域 S 的可行方向. 定义7.2.2 设集合 , , 是非零向量,若存在 数 ,使得对每一个 ,都有 n S R x clS d 0 (0, ) x + d S 则称 d 为集合 S 在 x 的可行方向. 其中“ cl ”表示闭包， clS 即 S 的闭包。 { | ( ) 0} F0 = d f x d T (7.2.3)
集合S在X处所有可行方向组成的集合 D={d|d≠0，x∈clS,36>0, (7.2.4) 使得V几∈(0，δ)，有+d∈S} 称为在X处的可行方向锥。 由可行方向和下降方向的定义可知，如果x是f(x)在S上 的局部极小点，则在X处的可行方向一定不是下降方向。 定理7.2.1考虑问题 min f(x) s.t x∈S 设S是R"中的非空集合，x∈S,f(x)在x处可微。如果x是 局部最优解，则F∩D=中。 其中F。和D分别又式(7.2.3)和(7.2.4)定义
称为在 x 处的可行方向锥。 由可行方向和下降方向的定义可知，如果 是 在 上 的局部极小点，则在 处的可行方向一定不是下降方向。 x f (x) S x 定理7.2.1 考虑问题 st x S f x . min ( ) 设 是 中的非空集合， ， 在 处可微。如果 是 局部最优解，则 。 其中 和 分别又式(7.2.3)和(7.2.4)定义。 S n R x S f (x) x x F0 D = F0 D 集合 S 在 x 处所有可行方向组成的集合 D = {d | d 0, x clS, 0, 使得 (0,),有x + d S} (7.2.4)
7.2.3 不等式约束问题的一阶最优性条件 考虑非线性规划问题： min f(x) s.t 8,(x)≥0i=1,2m (7.2.3) 这个问题的可行域 S={x|g,(x)≥0，i=1,,m} (7.2.8) 为把最优性的几何条件用代数来表示，我们引入起作用约 束的概念. 问题(7.2.3)的约束条件，在点x∈S处呈现两种情形： 有些约束，它们的下标集用【表示，成立等式，即 8,(x)=0ie1 (7.2.9)
7.2.3 不等式约束问题的一阶最优性条件 考虑非线性规划问题: 这个问题的可行域 为把最优性的几何条件用代数来表示, 我们引入起作用约 束的概念. 问题(7.2.3)的约束条件,在点 处呈现两种情形: 有些约束,它们的下标集用 表示,成立等式,即 x S I st g x i m f x i . ( ) 0 1,..., min ( ) = (7.2.3) S {x | g (x) 0,i 1,...,m} = i = (7.2.8) g x i I i ( ) = 0 (7.2.9)
另一些约束成立严格不等式，即 8,(x)>0,ie1. (7.2.10) 满足(7.2.9)的约束称为在元处起作用约束。 满足（7.2.10)的约束称为在x处不起作用约束。 起作用约束下标集I={ig()=0} 定义了起作用约束后，就能用集合 G={dVg,(x)'d>0,i∈I (7.2.11) 取代定理7.2.1中的可行方向锥D
另一些约束成立严格不等式，即 起作用约束下标集 { | ( ) 0} i I i g x = = 定义了起作用约束后，就能用集合 ( ) 0, . i g x i I (7.2.10) 0 { ( ) 0, } T G d g x d i I = i (7.2.11) 满足（7.2.9）的约束称为在 x 处起作用约束。 满足（7.2.10）的约束称为在 x 处不起作用约束。 取代定理7.2.1中的可行方向锥D