优化算法总结

这学期上了优化的这门课程,真的是蛮硬核的一门课了。这里略作总结。

首先所有的优化算法分为两大类,无约束的优化与有约束的优化。

所有的优化问题基本上都是主要需要计算的是方向(一般用$d_k$)和步长(一般用$alpha$来表示)

牛顿法。只用泰勒展开的二次展开项,计算得到了方向等于$hessian^-1 \cdot -g_k $(其实我们一般不计算G的逆,因为计算量和存储量太大,所以是相当于解一个线性方程组$G \cot d = g_k$. 然后牛顿法的缺点是当初始点离最优解较远的时候,其收敛性不太稳定(在不远的时候是二次收敛的)此外如果G非正定(此时没有逆),牛顿法的搜索将失败。

然后阻尼牛顿法就是在牛顿法的基础上,不再用步长为1的步长了,而是使用线搜索来计算求得步长(一般用armijo-goldstein或者wolfe准则)牛顿法具有全局收敛性,且为二次收敛。

稳定牛顿法就是Gill-Murary和Fletcher-Freeman,主要是用了修正cholesky分解(数值不稳定)来。修正牛顿法的思想是用G+μI来代替G,因为只要μ充分大,就能保证G+μI正定。

然后说一下这个分解吧。对于任意的非零对称矩阵而言,总可以分解成G=LDL^T,其中L是下三角矩阵,而D是由一阶块和二阶块组成的矩阵,

拟牛顿法(quasi-newton):用$B_k$来近似$H$,用$H_k$来近似$G_k^-1$,其中B是正定的。然后可以用拟牛顿法来解决大规模的问题,例如经典的BFGS算法。其中拟牛顿条件为:$B_k+1 ( x_{k+1} – x_k) = g_{k+1} – g_{k}$

然后就是信赖域方法:

先说一下LM方程,

考虑$q(d) = f + g^T d + \frac{1}{2}d^T G d$,$G\in SR^n$,那么$q(d)$有极小点当且仅当$G$半正定,$g\in{GX|X\in R^n}$。这里的SR就是实对称矩阵的意思。

【定理】$d_k$是问题2.1的解当且仅当$||d_k|| \leq \Delta_k$,存在$\nu \geq 0$,使得

方程2.2:

$$
(G_k + \nu I) d_k = -g_k \
\nu(\Delta_k – ||d_k||) = 0
$$

且$G_k + \nu I$半正定


然后进入到有约束的优化问题上。这个又可以归为两大类,等式约束的有约束优化和不等式约束的约束优化。

起作用(active)的不等式约束

对于有约束问题的最优解,其拉格朗日的函数的鞍点就是有约束的优化问题的局部最优解。

slater条件:存在点使得不等式约束都取>号成立。(一般情况下现在写拉格朗日函数都写成>=的形式,然后在拉格朗日函数中都写成$-lambda*c_i…$的形式

然后又有一些约束规范(CQ,condition )。比如LICQ约束规范,MF约束规范等等。

”’
LICQ:起作用的 函数(即 相当于等式约束的情况)和 函数在极值点处的梯度要线性无关,那么极值一定满足 KKT 条件。
Slater 条件:如果优化问题是个凸优化问题,且至少存在一个点满足 和 ,极值一定满足 KKT 条件。并且满足强对偶性质(下面会讲)。
     这里的 Slater 条件比较重要,因为它可以推导出强对偶性质(下面会讲到,它比 KKT 条件还好)。它需要原问题是凸优化问题。所谓凸优化就是这个优化问题的优化函数是凸函数,并且可行域是凸集。可行域数凸集就要求其中的 的条件中 必须也是凸函数,而 中的 必须是 形式的,也就是仿射函数(比如二维的情况,可行域就在 这条曲线上,那么 必须得是直线才能满足凸集的定义)。
”’

Ref

https://www.cnblogs.com/kisetsu/p/9157371.html

https://max.book118.com/html/2017/0908/132580561.shtm

https://wenku.baidu.com/view/4bfb424cf111f18583d05ab8.html

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注