最优化方法第一次B

1、八八. 凸集与凸函数凸集与凸函数1.凸集凸集（1）凸组合：已知凸组合：已知 ，nRX 任取k个点 ， Xxi 如果存在常数0 ia，),2,1(ki 11 kiia，使得 xxakiii1，则称 x为ix),2,1(ki 的凸组合。的凸组合。（2）凸集：设集合）凸集：设集合nRX ，如果X中任意两点的凸组合仍然属于X，则称X为凸集。2.凸函数凸函数设设RRXfn :，任取任取Xxx 21,，如果如果1,0,2121 iiaaa，有有)()()(22112211xfaxfaxaxaf ，则称则称f为为X上的（严格）上的（严格）凸函数。凸函数。例子：例子： 2)(xxf 5. 凸规划凸规划（1）D

2、xtsxf .)(min其中其中)(xf是凸函数，是凸函数，D是凸集。是凸集。（2）)(minxf 0)(0)(0)(0)(.11xhxhxgxgtskl其中其中)(, )(xgxfi是凸函数，是凸函数，)(xhj是线性函数。是线性函数。水平集水平集： fXxxfxD,)(| 是凸函数是凸函数。性质：水平集一定是凸集。性质：水平集一定是凸集。3. 凸函数的性质凸函数的性质定理定理. 凸函数的局部极小点就是全局极小点。凸函数的局部极小点就是全局极小点。4. 凸函数的判断条件凸函数的判断条件定理定理1. )(xf是凸集是凸集X上的凸函数的充要条件是上的凸函数的充要条件是Xxx 21,，有，有)()

3、()()(12112xxxfxfxfT .定理定理2.设设)(xf在凸集在凸集X上有二阶连续偏导数，则上有二阶连续偏导数，则)(xf是凸是凸函数的充要条件是函数的充要条件是Xx ，有，有)(2xf 半正定。半正定。例：正定二次函数例：正定二次函数cxbAxxxfTT 21)(，其中，其中A是正定矩阵。是正定矩阵。十十. 算法及相关概念算法及相关概念1.一般迭代算法一般迭代算法集合集合S上的迭代算法上的迭代算法A：（1）初始点）初始点0 x；（2）按照某种规则）按照某种规则A产生下一个迭代点产生下一个迭代点)(1kkxAx 。（i）如果点列）如果点列kx收敛于最优解收敛于最优解*x，则称算法，则

4、称算法A收敛。收敛。（ii）如果）如果 )()()(10kxfxfxf，则称算法，则称算法A为为下降迭代算法。下降迭代算法。.0 x.1x.2x九九. 极小点的判定条件极小点的判定条件（1）必要条件：）必要条件：0)()(min)(xfxfxf（2）充分条件：）充分条件：0)(0)(2 xfxf)(min)(xfxf2.下降迭代算法步骤下降迭代算法步骤（1）给出初始点）给出初始点0 x，令，令0 k；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向kd；（3）按照某种规则确定搜索步长）按照某种规则确定搜索步长k ，使得，使得)()(kkkkxfdxf ；（4）令）令kkkkdxx 1，1: kk；（5）判断）判断kx是否满足停止条件。是则停止，否则转第是否满足停止条件。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：)(min)(kkkkkdxfdxf 称称0)( kTkkkddxf 。k 为最优步长，且有为最优步长，且有十一十一. 终止条件终止条件)(31kkkkxxxx)(41kkkkxfxfxfxf1111)()()(kkkkkkxfxfxfxxx22)(kkxxf1111)()(kkkkxfxfxx2.4.1.11kkxx21)()(kkxfxf3.5.最可靠法则最可靠法则