八, 凸集与凸函数
1.凸集
（ 1） 凸组合：已知,nRX ? 任取 k个点,Xxi ? 如果存在常数
0?ia, ),,2,1( ki ?? 11 ???ki ia,使得 ?? ?? xxaki ii1,则称 ?x 为 ix
),,2,1( ki ?? 的凸组合。
（ 2）凸集：设集合 nRX ?,如果 X 中任意两点的凸组合
仍然属于 X,则称 X 为凸集。
2.凸函数
设 RRXf n ??:, 任取 Xxx ?21,,如果 1,0,2 121 ??? ??i iaaa,
有 )()())(( 22112211 xfaxfaxaxaf ????,则称 f 为 X上的（严格）
凸函数。
例子,2)( xxf ?
5,凸规划
（ 1）
Dxts
xf
?..
)(m in
其中 )(xf 是凸函数,D 是凸集。
（ 2） )(m in xf
?
?
?
?
?
?
?
?
?
?
?
?
?
0)(
0)(
0)(
0)(
..
1
1
xh
xh
xg
xg
ts
k
l
?
?
其中 )(,)( xgxf i 是凸函数,)(xhj 是线性函数。
水平集, fXxxfxD,,)(|{ ??? ?? 是凸函数 }。
性质：水平集一定是凸集。
3,凸函数的性质
定理, 凸函数的局部极小点就是全局极小点。
4,凸函数的判断条件
定理 1,)(xf 是凸集 X上的凸函数的充要条件是 Xxx ?? 21,，有
)()()()( 12112 xxxfxfxf T ????,
定理 2.设 )(xf 在凸集 X上有二阶连续偏导数，则 )(xf 是凸
函数的充要条件是 Xx??,有 )(2 xf? 半正定。
例：正定二次函数 cxbAxxxf TT ??? 21)(,其中 A
是正定矩阵。
十, 算法及相关概念
1.一般迭代算法
集合 S上的迭代算法 A：
（ 1）初始点 0x ；
（ 2）按照某种规则 A产生下一个迭代点 )(1 kk xAx ?? 。
（ i）如果点列 }{ kx 收敛于最优解 *x,则称算法 A收敛。
（ ii）如果 ?? ???? )()()( 10 kxfxfxf,则称算法 A为
下降迭代算法。
.
0x
.1x,
2x
九, 极小点的判定条件
（ 1）必要条件,0)()(m in)( ???? ?? xfxfxf
（ 2）充分条件：
0)(
0)(
2 ??
??
?
?
xf
xf
? )(m in)( xfxf ??
2.下降迭代算法步骤
（ 1）给出初始点 0x,令 0?k ；
（ 2）按照某种规则确定下降搜索方向 kd ；
（ 3）按照某种规则确定搜索步长 k?,使得
)()( kkkk xfdxf ?? ?；
（ 4）令 kkkk dxx ???? 1, 1,?? kk ；
（ 5）判断 kx 是否满足停止条件。是则停止，否则转第 2步。
搜索步长确定方法：
)(m i n)( kkkkk dxfdxf ?? ? ???
称 0)( ??? kTkkk ddxf ?。k? 为最优步长，且有
十一, 终止条件
?
)(3
1
?? ??
?? k
k
kk
x
x
xx ? ? ? ?
? ? ? ? )(4
1
?? ???
?
k
k
kk
xfxf xfxf
?
?
?
?
?
?
?
?
?
?
?
?
?
1
1
1
1
)(
)()(
?
?
k
kk
k
kk
xf
xfxf
x
xx
??
?
?
?
?
?
2
2)(
?
?
k
k
x
xf
??
???
??
??
?
?
1
1
1
1
)()( ?
?
kk
kk
xfxf
xx
?
2.
4.
1.
11 ???? kk xx 21 )()( ???? kk xfxf
3.
5.最可靠法则,
十二, 收敛速度
则称 的收敛阶为 。
设算法 A所得的点列为 }{ kx,如果
,|||||||| **1 ?? xxxx kk ????,0,???
?}{ kx