八.凸集与凸函数 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
