五、优化算法
前置定义
所有优化算法都是迭代算法。
$x^{k+1}=x^k+\alpha^k d^k$ ，其中 $\alpha^k$ 是标量，表示步长； $d^k$ 是向量，表示更新方向。
$\alpha_k=arg\ \min_{\alpha \geq 0} f_0(x^k+\alpha d^k)$ ，若 $f_0(x)$ 为凸函数，则该问题转变为一维凸优化问题，由此有以下两种解决方法。
黄金分割法
黄金分割法 (0.618 法) - 优选法：
- $[l,r]$ => 选取 $l+0.618(r-l)$ 以及 $l+0.382(r-l)$ 两个位置进行比较，更新区间
Back tracking
Amijo Rule - Back tracking：
-
若 $f_0(x^k+\alpha d^k)>f_0(x^k)+\gamma \alpha \nabla f_0^T(x^k)d^k$ ，则 $\alpha\leftarrow \alpha \beta$ ，否则停止
-
$\gamma\in (0,0.5),\beta\in (0,1)$
强凸性
强凸性：
-
$\exists m>0,\forall x\in dom(f),\nabla^2f(x)\succeq mI$ ，等价于 $\forall x,y\in dom(f),f(y)\geq f(x)+\nabla f^T(x)(y-x)+\frac{1}{2}m||y-x||^2_2$
-
可以继续推导出 $p^*+\frac{1}{2m}||\nabla f(x)||^2_2\geq f(x)\geq p^*$ 以及 $\nabla f(x)\rightarrow 0,f(x)\rightarrow f(x^*)$ 时 $||x^*-x||\leq \frac{2}{m}||\nabla f(x)||$
强凸性对应性质：
- $\exists M>0,\forall x\in dom(f),\nabla^2f(x)\preceq MI$ ，等价于 $\forall x,y\in dom(f),f(y)\leq f(x)+\nabla f^T(x)(y-x)+\frac{1}{2}M||y-x||^2_2$ 以及 $p^*\leq f(x)-\frac{1}{2M}||\nabla f(x)||^2_2$
无约束优化
梯度下降法 (Gradient Descent)
算法过程：
-
$d^k=-\nabla f(x^k)$
-
$\alpha^k=arg\ \min_{\alpha_{max}\geq \alpha\geq 0}f(x^k+\alpha d^k)$
-
$x^{k+1}=x^k+\alpha^kd^k$
分析算法收敛性：
-
精确搜索：$\displaystyle\frac{f(x^{k+1}-p^*)}{f(x^{k}-p^*)}\leq 1-\displaystyle\frac{m}{M}$，线性收敛
-
非精确搜索：$\displaystyle\frac{f(x^{k+1}-p^*)}{f(x^{k}-p^*)}\leq 1-\min\{2m\gamma \alpha_{max},\frac{2m\gamma\beta}{M}\}$，线性收敛
最速下降法 (Steepest Descent)
算法过程：
-
$d^k=arg\ \min_v\{f(x^k+v)|||v||=1\}$
-
将 $f(x^k+v)$ 在 $x^k$ 处展开，得到 $d^k=arg\ \min_v{f(x^k)+\nabla^Tf(x^k)v|||v||=1}$
-
一范数： $v$ 平行于梯度最大值的维度
-
二范数： $v$ 取值为负梯度，等价于梯度下降
-
无穷范数： $v$ 在梯度为正维度取 -1，负维度取 1
- $\alpha^k$ 用 exact 或 Amijo 方法求得
分块坐标轮换法 (Block Coordinate Descent)
算法描述：
-
对于 $\min f(x,y)$ 问题，每次仅针对某一维度进行优化，不断轮换
-
$x^{k+1}=arg\ \min_x f(x,y^k)$
-
$y^{k+1}=arg\ \min_y f(x^{k+1},y)$
特点：
- 要求 $f(x,y)$ 为凸函数且光滑
次梯度法 (Subgradient Descent)
定义：
-
当函数在该点可微，则 $\displaystyle\frac{\partial f(x)}{\partial x}=\nabla f(x)$
-
当函数在该点不可微，则 $\displaystyle\frac{\partial f(x)}{\partial x}$ 取值范围由左右梯度组成， $\in [(\nabla f(x))^-,(\nabla f(x))^+]$
功能：
- 解决不可微问题的优化，引入次梯度改进 GD、SD、BCD 方法
牛顿法 (Newton’s method)
算法过程：
-
$d^k=arg\ \min_v\{f(x^k+v)|||v||=1\}=-(\nabla^2f(x^k))^{-1}\nabla f(x^k)$
-
将 $f(x^k+v)$ 泰勒展开，得 $d^k=arg\ \min_v{f(x^k)+\nabla f^T(x^k)v+\frac{1}{2}v^T\nabla^2 f(x^k)v}$
-
由于中间函数为 $v$ 的二次函数，且由于 Hessian 矩阵半正定，因此最优解唯一，即不再需要 $||v||=1$ 的约束避免取到负无穷
-
$\alpha^k=arg\ \min_{\alpha_{max}\geq \alpha\geq 0} f(x^k+\alpha d^k)$
-
$x^{k+1}=x^k+\alpha^k d^k$
- 重复上述步骤，直至 $|\nabla f^T(x^k)(\nabla^2 f(x^k))^{-1}\nabla f(x^k)|\leq \epsilon$
收敛性分析：
-
$\exists \eta>0$ ，可以根据初值点距离最优解的远近，划分为两种不同收敛情况
-
(1) 若 $||\nabla f(x)||_2>\eta$ ，则为阻尼牛顿段 (damped Newton phase)
-
(2) 若 $||\nabla f(x)||_2\leq \eta$，则为二次收敛段 (Quadratically Convergent phase)，即 $\displaystyle\frac{f(x^{k+1}-p^*)}{(f(x^k)-p^*)^2}～\mu$
拟牛顿法 (Quasi-Newton Method)：
-
牛顿方向： $\nabla^2 f(x^k)d^k=-\nabla f(x^k)$
-
拟牛顿方向： $B\cdot d^k=-\nabla f(x^k)$ ，用 $B$ 代替 Hessian 矩阵，例如 BFGS 方法
有约束优化
有约束牛顿法
线性等式约束的凸优化问题：
对应 KKT 条件：
若 $f(x)$ 为线性函数，则可以使用高斯消元等方法求解 KKT 条件；若 $f(x)$ 为非线性函数，则可以对 $f(x)$ 在 $x_k$ 这点做一个线性展开，即泰勒展开至二阶。
当 $f(x)$ 为非线性函数时，迭代求解 $x^{k+1}=x^k+\alpha d^k$ ，即求解如下式子：
上式拉格朗日函数为 $L(d,v)=f(x^k)+\nabla f^T(x^k)d+\frac{1}{2}d^T \nabla^2 f(x^k)d+v^TAd$ ，对应的 KKT 条件为：
由此可以求解得到 $d^k$ ：
由于我们只能使 $f(x^k+d)$ 泰勒展开后的近似函数最小，因此我们还需计算迭代步长，即 $\alpha$ ：
最后迭代计算 $x$ ，即 $x^{k+1}=x^k+\alpha^k d^k$ ，且 $x^{k+1}$ 仍然满足约束。
拉格朗日乘子法
上述迭代式子可以从两方面理解：
-
求解鞍点的角度
-
上述更新的梯度与 KKT 条件求得的负梯度内积大于 0
缺点：
- 对 $\alpha^k$ 选择的要求很高，很容易不收敛，实际运用效果不好
增广拉格朗日法 (Augmented Lagrangian Method)
原问题：
增广拉格朗日函数：
增广拉格朗日函数为下述问题的拉格朗日函数：
-
下述问题与原问题的最优解一致
-
下述问题的对偶问题，与原问题的对偶问题，最优解也一致
增广拉格朗日法：
-
收敛性、鲁棒性比较好
-
$c$ 通常为常数，如 $1$ ，绝大部分情况下都能收敛；或者 $c$ 取递增的序列，也可保证大多数情况收敛
性质：
-
若 $v=v^*$，则 $\forall c>0$，$x^*=arg\ \min_x L_c(x,v^*)$
- 若 $c\rightarrow +\infty$ ，则 $\forall v,x^*=arg\ \min_x L_c(x,v)$
交替方向乘子法 (ADMM - Alternating Direction Method of Multipliers)
原问题：
转换后等价于下述问题：
增广拉格朗日函数：
ADMM 方法：
-
第一步， ${x_i^{k+1}}=arg\ \min_{{x_i}}\sum\limits_{i=1}^n f_i(x_i)+\displaystyle\frac{c}{2}\sum\limits_{i=1}^n ||x_i-z^k+\frac{v_i^k}{c}||^2_2$
-
即， $x_i^{k+1}=arg\ \min_{x_i} f_i(x_i)+\displaystyle\frac{c}{2}||x_i-z^k+\frac{v_i^k}{c}||^2_2,\forall i$
-
第二步， $z^{k+1}=arg\ \min_z \displaystyle\frac{c}{2}\sum\limits_{i=1}^n ||z-x_i^{k+1}-\displaystyle\frac{v_i^k}{c}||^2_2$
-
即， $z^{k+1}=\displaystyle\frac{1}{n}\sum\limits_{i=1}^n(x_i^{k+1}+\displaystyle\frac{v^k_i}{c})$
-
第三步， $v_i^{k+1}=v_i^k+c(x_i^{k+1}-z^{k+1}),\forall i$