> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/math-convex_optimization/ista.md).

# ISTA

## L1范数产生稀疏解##\#

$$\min F(x) = ||Ax-b||^2 + \lambda ||x||\_p^p$$\
假设最优解为$$x^*$$，则原问题等价于： $$\min\_x F(x) = ||Ax-b||^2 \qquad s.t. \quad ||x||\_p^p \le C \quad C=||x^*||\_p^p$$

## proximal gradient descent##\#

在梯度下降中，如果 $$\nabla f(x)$$ 满足L-Lipschitz，即： $$\left | \nabla f(x\_{k+1}) - \nabla f(x\_k) \right | \le L \left | x\_{k+1} - x\_k \right |$$ ,\
在$$x\_k$$点泰勒展开：

$$
f(x,x\_k) = f(x\_{k}) + \left \langle x-x\_{k},\nabla f(x\_{k}) \right \rangle + \frac {L}{2} \left | x-x\_{k} \right |^2  \\
\= \frac {L}{2} \left | x- (x\_{k} -t\_k \nabla f(x\_{k})) \right |^2 + \varphi (x\_k)
$$

最小在 $$x\_{k+1} = x\_{k} - \frac {1}{L} \nabla f(x\_{k+1})$$。\
如果优化目标中，加入非光滑的惩罚项，比如L1，对光滑的部分做上述展开，则称为proximal gradient descent(PGD)。

[Proximal Gradient Descent for L1 Regularization](http://www.cnblogs.com/breezedeus/p/3426757.html)

## ISTA##\#

ISTA算法解决非平滑的，不可求导的凸优化问题，比如带能够产生稀疏解的L1范数问题，$$\min { f(x) + \lambda \left | x \right |\_1 }$$。

通过对目标函数进行分解，将其平滑的部分用近端正则逼近。即每步在优化原问题的一个变化上界。 每一步迭代中，优化变量完全解耦，且子问题存在闭式解。

列：$$\min F(x) = \left | Ax-b \right |^2 + \lambda \left | x \right |\_p^p$$。\
该问题等价于：$$\min\_x \left | Ax-b \right |^2 \quad s.t. \left | x \right |\_p^p \lt C \quad C=\left | x^\* \right |\_p^p \quad x^\*\text{是最优解}$$。

每一步迭代求解：

$$
x\_k = \arg \min\_x  { {\color{Blue} {f(x\_{k-1}) + \left \langle x-x\_{k-1},\nabla f(x\_{k-1}) \right \rangle + \frac {1}{2t\_k} \left | x-x\_{k-1} \right |^2 }} + \lambda \left | x \right |*1 } \\
\approx \arg \min\_x  {  \frac {1}{2t\_k} \left | x- (x*{k-1} -t\_k \nabla f(x\_{k-1})) \right |^2  + \lambda \left | x \right |\_1 }
$$

存在闭式解：

$$
x\_k = \tau\_{\lambda t\_k} (x\_{k-1} -t\_k \nabla f(x\_{k-1})) \\
\tau\_{\alpha}(x) = sign(x) \max {0, \left| x \right| -\alpha}
$$

收敛：\
$$\left | x\_k - x\_{k-1} \right |^2 \to 0$$时收敛，上界等于原目标函数。

如何确定$$t\_k$$？

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F0d036e03bb43a59fa17159ae0466a3acaf06aee4.png?generation=1589383934378084\&alt=media)

> from MLAPP: Chapter 13. Sparse linear models (page 446)

## FISTA##\#

《A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems》

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fd936ed4d87d9c3b2e83a339b3b783a53c2290fcd.png?generation=1589383934377189\&alt=media)

> 关于Nesterov’s method可以见SGD的Nesterov Momentum。

[Python implementation of the Fast Iterative Shrinkage/Thresholding Algorithm.](https://github.com/JeanKossaifi/FISTA)