五、坐标下降法
🚩坐标下降法就是分治法的思想。
六、最优化算法瓶颈
🚩前面梯度下降法,还有牛顿法求极值的依据都是ᐁf(xk)=0,而前面我们也说了函数在某一点的导数或梯度等于 0 就是驻点,它只是函数取得极值的必要条件,不是充分条件,也就是说无法推导出
所有我们前面介绍的数值优化算法,都会面临两个问题。
6.1 局部极值问题
🚩这个问题好歹是个局部极值,只不过不是全局极值,理论上我们要求全局最优解的话,我们要把所有极小值找出来,你可能要不断的去设置不同的初始迭代点,反复的求解让它收敛到不同的局部最小值,然后来比较谁最小来找到一个全局最小值。
6.2 鞍点问题
🚩前面我们说过一元函数x3函数,在坐标为 0 处它是驻点,但是它连局部最小值都不是,对应多元函数来说,我们称之为鞍点(既不是极大值点也不是极小值点的临界点,叫做鞍点)。严格定义是,在这一点它的Hessian 矩阵是不定的,既不正定也不负定,这样它就即不是极小值的点也不是极大值的点。
在物理上要广泛一些,指在一个方向是极大值,另一个方向是极小值的点。
七、凸优化问题
🚩前面我们说过数值优化面临两个问题,一个是局部极值问题,和鞍点问题,我们能不能避免这两个问题呢?
只要我们对优化问题进行限定就可以,这类问题有两个限定条件
1、优化变量的可行域必须是凸集
2、优化函数必须是个凸函数
同时满足这两个限定条件的问题,叫做凸优化问题,从而才有局部极小值进而全局极小值。
八、凸集
🚩凸集的定义:对于一个点的集合C有 x , y 它都是属于 C 里面的两个点,它们两点的连线中任何一点也是属于集合 C 的。例如立方体就是凸集。
它的意义在于,很多时候可行域就是欧式空间,那肯定是凸集。在凸集的前提下,才可以进行最优化问题求解。
九、凸函数
🚩凸函数在函数上任意找两点它们的连续就是割线上的值比对应的 f(x)的值要大
函数的二阶导数是和函数的凹凸性是有关系的,凹凸性怎么定义的?
先来做简单的介绍,这里先记住凸函数是向下凸的, 反正就是凹的,是否是凸函数可以通过二阶导数,如果二阶导数是大于 0 就是凸函数
如果一元函数,那么f′′(x)≥0就是凸函数。多元函数Hessian矩阵是半正定的,它就是凸函数;多元函数Hessian矩阵是正定的,它就是严格的凸函数。
十、凸优化表达形式
🚩凸优化的定义是目标函数是凸函数,可行域是个凸集,如果有这两个限定条件的话,局部最优解一定是全局最优解。
凸优化一般表达形式:
十一、拉格朗日乘子法
🚩高等数学和微积分的时候我相信大家都学过,用来求解等式约束下的极值问题的
拉格朗日乘子法,把对 x带约束条件的优化问题,转化为不带约束条件的优化问题
十二、KKT条件
🚩假设我们面对的是不等式条件约束优化问题,如下:
针对上式,显然是一个不等式约束最优化问题,不能再使用拉格朗日乘数法,因为拉格朗日乘数法是针对等式约束最优化问题。
拉格朗日乘数法的扩展,用来解决带不等式约束条件的一种理论结果:
约束条件为:
- ᐁL(x,λ)=0
- λ ≥ 0
- λh(x)=0
上面条件就称为KKT 条件。
十三、拉格朗日对偶
🚩凸优化,非线性规划问题,甚至是运筹学里面的线性规划问题都会涉及这个概念,它的意义是把原始问题转化为另外一个问题来求解,但是转化之后的问题要容易求解一点,拉格朗日乘数法的扩展,用来解决既带等式约束条件,又带不等式约束条件的一种方法通过把原问题转换为对偶问题来求解,很多时候对偶问题比原问题更容易求解。
原始问题
我们定义对偶问题为(对上面方程的求解等效求解下面方程):
其实就是把 m i n 和 m a x 对调了一下,当然对应的变量也要变换。