《最优化方法》课程教学资源（题解）第八次 凸集与凸函数

八.凸集与凸函数 1凸集 (1)凸组合:已知XcR",任取k个点x'∈X,如果存在常数 a1≥0(i=1,2,…,),Σn1=1,使得Σax=x,则称x为x (i=1,2,…,k)的凸组合。 (2)凸集:设集合XcR”,如果X中任意两点的凸组合 仍然属于X,则称Ⅹ为凸集。 2凸函数 设∫:XcR"→R,任取x,x2∈X,如果va1,n20,2a1=1, 有f(a1x2+a2x2)(<)≤a1f(xl)+a2f(x2),则称∫为X上的(严格) 凸函数。 例子:f(x)=x

八. 凸集与凸函数 1.凸集 （1）凸组合：已知 X  R n ，任取k个点 x i  X ，如果存在常数 ai  0 (i = 1,2,  ,k) ， 1 1  = = k i ai ，使得 − = a x = x k i i i 1 ，则称 − x 为 i x (i = 1,2,  ,k) 的凸组合。 （2）凸集：设集合 n X  R ，如果 X 中任意两点的凸组合 仍然属于 X ，则称 X 为凸集。 2.凸函数 设 f X R R :  n → ，任取 x x  X 1 2 , ，如果 , 0, 1 2 1  1 2   = i= a a ai ， 有 ( )( ) ( ) ( ) 2 2 1 1 2 2 1 f a1 x + a x   a f x + a f x ，则称 f 为X上的（严格） 凸函数。 例子： 2 f (x) = x

5.凸规划 (1 min f(x) St.x∈D 其中∫(x)是凸函数,D是凸集。 (2)min f(x) g1(x)≤0 g/(x)≤0 h(x)=0 其中f(x),8(x)是凸函数,b(x)是线性函数

5. 凸规划 （1） s t x D f x . .  min ( ) 其中 f (x) 是凸函数， D 是凸集。 （2） min f (x)          = =   ( ) 0 ( ) 0 ( ) 0 ( ) 0 . . 1 1 h x h x g x g x s t k l   其中 f (x), g (x) i 是凸函数， h (x) j 是线性函数

水平集:Da={xU(x)≤a,x∈X,厂是凸函数}。 性质:水平集一定是凸集。 3凸函数的性质 定理.凸函数的局部极小点就是全局极小点。 4.凸函数的判断条件 定理1.f(x)是凸集X上的凸函数的充要条件是vx,x2∈X,有 f(x2f(x)+vf(x'(x-x) 定理2设∫(x)在凸集X上有二阶连续偏导数,则f(x)是凸 函数的充要条件是Wx∈X,有V2f(x)半正定。 例:正定二次函数f(x)=xAx+bx+c,其中A 是正定矩阵

水平集： D = {x |f (x)  , x  X, f  是凸函数}。 性质：水平集一定是凸集。 3. 凸函数的性质 定理. 凸函数的局部极小点就是全局极小点。 4. 凸函数的判断条件 定理1. f (x) 是凸集X上的凸函数的充要条件是 x x  X 1 2 , ，有 ( ) ( ) ( ) ( ) 2 1 1 2 1 f x f x f x x x T  +  − . 定理2.设 f (x) 在凸集X上有二阶连续偏导数，则 f (x) 是凸 函数的充要条件是 x X ，有 ( ) 2  f x 半正定。 例：正定二次函数 f x x Ax b x c T T = + + 2 1 ( ) ，其中 A 是正定矩阵

十.算法及相关概念 1.一般迭代算法 集合S上的迭代算法A: (1)初始点x0; (2)按照某种规则A产生下一个迭代点x4=A(x4)。 i)如果点列{x}收敛于最优解x,则称算法A收敛。 (ⅱi)如果∫(x")>∫(x2)>…>f(x^)>…,则称算法A为 下降迭代算法

十. 算法及相关概念 1.一般迭代算法 集合S上的迭代算法A： （1）初始点 0 x ； （2）按照某种规则A产生下一个迭代点 ( ) k 1 k x = A x + 。 （i）如果点列 { } k x 收敛于最优解 * x ，则称算法A收敛。 （ii）如果 f (x 0 )  f (x 1 )   f (x k )   ，则称算法A为 下降迭代算法。 . 0 x . 1 x . 2 x

九.极小点的判定条件 (1)必要条件:f(x*)=mnf(x)→Vf(x*)=0 (2)充分条件:Vf(x)=0 →f(x)=minf(x) V2f(x)>0

九. 极小点的判定条件 （1）必要条件： ( ) = min ( )   ( ) = 0   f x f x f x （2）充分条件： ( ) 0 ( ) 0 2    =   f x f x  f (x ) = min f (x) 

2.下降迭代算法步骤 (1)给出初始点x0,令k=0; (2)按照某种规则确定下降搜索方向d; (3)按照某种规则确定搜索步长λ,使得 f∫(x4+λd-)<f(x); (4)令x=x+d,k:=k+1 5)判断x是否满足停止条件。是则停止,否则转第2步。 搜索步长确定方法: f(x4+λd)=min∫(x2+Md 称λ为最优步长,且有Vf(x4+λd)d=0

2.下降迭代算法步骤 （1）给出初始点 0 x ，令 k = 0 ； （2）按照某种规则确定下降搜索方向 k d ； （3）按照某种规则确定搜索步长 k ，使得 ( ) ( ) k k k k f x +  d  f x ； （4）令 k k k k x = x +  d +1 ， k := k +1 ； （5）判断 k x 是否满足停止条件。是则停止，否则转第2步。 搜索步长确定方法： ( ) min ( ) k k k k k f x  d f x d  + = + 称  ( + ) = 0 k T k k k k 为最优步长，且有 f x  d d

十一.终止条件 k+1-x <8 2.f(x+)-f(x-)<E2 5最可靠法则: f(xt)-f(x x-x|<6 /(x")-(x^)<6

十一. 终止条件  ( ) 3 1     − + k k k k x x x x ( ) ( ) ( ) ( ( ) ) 4 1     − + k k k k f x f x f x f x         −  − + + 1 1 1 1 ( ) ( ) ( )   k k k k k k f x f x f x x x x       2 2 ( )   k k x f x     −  −  + + 1 1 1 1 ( ) ( )   k k k k f x f x x x  2. 4. 1. 1 1 −   k + k x x 2 1 ( ) − ( )   k+ k f x f x 3. 5.最可靠法则：

十二.收敛速度 设算法A所得的点列为{x},如果 +1 0. 则称{x4}的收敛阶为a

十二. 收敛速度 则称 的收敛阶为 。 设算法A所得的点列为 { } k x ，如果 || || || || , 1 * *  x x  x x k k −  − +  ,  0. { }  k x