优化算法（一）——无约束优化问题

JoshWindsor

迭代下降算法（Iterative Descent Algorithm）

一个序列 \{x_1,x_2,\cdots,x_k\} 依次由固定的函数 x_{k+1}=G_k(x_k) 所生成。

• 固定迭代法（Stationary iterative algorithm）
  

其中典型例子包括：
1) 对于无约束的可微函数 f(x)，它的最优值满足 \nabla f(x^\star)=0 。
因此可以使用固定步长的梯度下降法 x_{k+1}=x_k-\alpha\nabla f(x_k) 进行迭代。
2）求解线性方程组 Ax=b ，使用理查德松迭代(Richardson iteration)，找到满足方程组的解 x 。
x_{k+1}=x_k-\alpha(Ax_k-b)=(I-\alpha A)x_k+\alpha b 。
（为了使得 I-\alpha A 在 \alpha 足够小的情况下，可以使得 x_k 一直收敛至同一个方向，需要保证矩阵 A 的特征值实部大于 0  。）
当可微函数是一个二次函数 f(x)=\frac{1}2x^TAx+b^Tx 时，两个例子等价。
收敛性分析证明方式有很多种，寻找满足条件的参数 \rho ，使得 \|x_{k+1}-x^\star\|\leq\rho\|x_{k}-x^\star\| （线性收敛速度），巴拿赫不动点定理(Banach Fixed Point Theorem)， 等等。

• 非固定迭代法 (Non-stationary iterative algorithm）
  

每轮迭代的过程中，迭代方程的表达式不一样。但通常来讲，这一步长都会与前一轮或者前几轮的迭代结果相关，如在inexact line search中，使用adaptive的步长 \alpha_k 进行梯度下降,  x_{k+1}=x_k-\alpha_k\nabla f(x_k) ，步长的选取就是一个非常关键的问题。
同样地，这里从 x_k 到 x_{k+1} 的生成过程，需要保证算法始终向着最优解的方向流动。也即，当 x_k  尚未达到最优值的时候，需要保证 f(x_{k+1})<f(x_k) 或者 \|x_{k+1}-x^\star\|<\|x_{k}-x^\star\| （ \|\cdot\| 不一定指的是Euclidean norm，适当的距离函数即满足条件）。
可微无约束优化问题（Differentiable constrained problems）

对于最优的无约束极小化问题 \min\limits_{x}f(x) ，假定 f(x) 一阶可微， d_k 是在 x_k 点处可以使得函数 f(x) 下降的方向，因此有
f(x_{k+1})=f(x_k+\alpha_kd_k)<f(x_k)\\
对中间一项使用一阶Taylor展开，可以得到
f(x_k)+\alpha_k\nabla^T f(x_k)d_k+o(\|\alpha_kd_k\|)<f(x_k)\\
因此下降方向需要满足 f'(x_k;d_k)=\nabla^T f(x_k)d_k<0 。
因此为解最优化问题，需要考虑两个基本要素，一个是确定合适的下降方向 d_k ，另一个是确定合适的步长 \alpha_k 。这也就是说，不同的方式得到的下降方向和步长不同，因此这一方式被称为线搜索（line search）。