凸优化笔记22：近似点算法
在进入具体的优化算法后，我们首先讲了基于梯度的，比如梯度下降(GD)、次梯度下降(SD)；然后又讲了近似点算子，之后讲了基于近似点算子的方法，比如近似点梯度下降(PG)、对偶问题的近似点梯度下降(DPG)、加速近似点梯度下降(APG)。而这一节讲的，还是基于近似点的！他叫近似点方法(Proximal
Point Algorithm,
PPA)，除此之外还会介绍增广拉格朗日方法(Augmentt
凸优化笔记21：加速近似点梯度下降
我们证明了梯度方法最快的收敛速度只能是 \(O(1/k^2)\)（没有强凸假设的话），但是前面的方法最多只能达到
\(O(1/k)\)
的收敛速度，那么有没有方法能达到这一极限呢？有！这一节要讲的加速近似梯度方法(APG)就是。这个方法的构造非常的巧妙，证明过程中会发现每一项都恰到好处的抵消了！真不知道作者是怎么想出来这么巧妙地方法，各位可以看看证明过程自行体会。
凸优化笔记20：对偶近似点梯度下降
前面讲了梯度下降、次梯度下降、近似点梯度下降方法并分析了收敛性。一开始我们还讲了对偶原理，那么如果原问题比较难求解的时候，我们可不可以转化为对偶问题并应用梯度法求解呢？当然可以，不过有一个问题就是对偶函数的梯度或者次梯度怎么计算呢？这就是这一节要关注的问题。
首先一个问题是哪些形式的问题，其对偶问题相比于原问题更简单呢？可能有很多种，这一节主要关注一种：线性等式/不等式约束的优化问题。之所以考虑
凸优化笔记19：近似点梯度下降
前面讲了梯度下降法、次梯度下降法，并分析了他们的收敛性。上一节讲了近似梯度算子，我们说主要是针对非光滑问题的，这一节就要讲近似梯度算子在非光滑优化问题中的应用。先回顾一下上一节最重要的一部分内容：对于指示函数
\(\delta_C\)
来说近似梯度算子得到的实际上就是向集合 \(C\) 的投影。
1. 近似点梯度下降
这一部分考虑的问题主要是 \[
\text{minimize } f(
凸优化笔记18：近似点算子 Proximal Mapping
前面讲了梯度下降法，分析了其收敛速度，对于存在不可导的函数介绍了次梯度的计算方法以及次梯度下降法，这一节要介绍的内容叫做近似点算子(Proximal
mapping)，也是为了处理非光滑问题。
凸优化笔记17：次梯度下降
对于光滑函数，我们可以用梯度下降法，并且证明了取不同的步长，可以得到次线性收敛，如果加上强凸性质，还可以得到线性收敛速度。那如果现在对于不可导的函数，我们就只能沿着次梯度下降，同样会面临步长的选择、方向的选择、收敛性分析等问题。
凸优化笔记16：次梯度 Subgradient
前面讲了梯度下降的方法，关键在于步长的选择：固定步长、线搜索、BB方法等，但是如果优化函数本身存在不可导的点，就没有办法计算梯度了，这个时候就需要引入次梯度(Subgradient)，这一节主要关注次梯度的计算。