一些非光滑凸优化算法

在很多凸优化问题中会遇到目标函数非光滑的情况，例如稀疏优化中的 $\ell_1$ 范数的正则项，将约束条件转化为可行集合的指示函数的无约束优化问题，目标函数为多个子目标的最大值的优化问题等.

我们将会考虑三种不同的非光滑优化算法：次梯度方法，近似点梯度方法和加速的近似点梯度方法.它们的误差和迭代次数 $k$ 的关系大致上为 $\mathcal O(1/\sqrt{k})$ , $\mathcal O(1/k)$ 和 $\mathcal O(1/k^2)$ .

次梯度方法可以看成是通常针对光滑函数的梯度方法的一种扩展，它通过推广梯度的概念，给出了一个和梯度方法类似的迭代格式.对于一些目标函数能够分解为一个光滑项和非光滑项的情况，近似点梯度方法通过引入近似点算子来处理非光滑项，同时对于光滑项仍然使用梯度方法，它的迭代分别两步，首先用梯度方法更新光滑项，之后再将非光滑项近似点算子作用在更新后的结果上.如果光滑项是一个强凸的函数，那么这个方法能够达到线性的收敛率.加速的近似点梯度方法是由Nesterov提出的一个方法，它能够解决和近似点梯度相同的问题，但是能够有更快的收敛速度.

为了尽量做到自包含，我们在第2节中会给出一部分后续需要的概念和命题.在第3节和第4节中我们会重点考察这三种优化算法的收敛性和收敛速度的证明，同时在第5节还会介绍针对一类目标函数可分但是约束条件不可分的优化问题的交替方向乘子法.最后在第6节和第7节中，我们在LASSO和离散最优传输问题中针对不同的方法进行测试.

这是今年数值分析的期末报告，具体内容查看附件.

non-smooth-convex-optimization (1.0 MiB, 6 hits)