可微凸優化臨近點梯度法
求解約束優化問題：
\begin{align*}
\mathop{min}\limits_{x} & \quad f(x)\\
s.t. & \quad x \in S
\end{align*}
其中，$f$是可微凸函數，$S$是凸集合。這個問題等價于:
\begin{align*}
\mathop{min}\limits_{x} & \quad f(x)+I_S(x)\\
\end{align*}
其中$I_S$為集合$S$的指示函數。
取$\beta \in \mathbb{R}^+$，使得$I+\beta \partial I_S$為極大單調算子，設$x^*$為問題的最優解，則
\begin{align*}
&0 \in \nabla f(x^*) + \partial I_S(x)\\
\iff & 0 \in \beta \nabla f(x^*) + \beta \partial I_S(x)\\
\iff & 0 \in x^* - \left( x^* -\beta \nabla f(x^*)\right) + \beta \partial I_S(x^*)\\
\iff & \left( x^* -\beta \nabla f(x^*)\right) \in x^* +\beta \partial I_S(x^*)\\
\iff & \left( I -\beta \nabla f\right)(x^*) \in \left( I +\beta \partial I_S\right) (x^*)\\
\iff & x^* =\left( I +\beta \partial I_S\right)^{-1}\left( I -\beta \nabla f\right) (x^*)
\end{align*}
由此將最優化問題轉化為不動點問題，根據不動點迭代的做法，我們得到迭代方式：
$$ x^{k+1} =\left( I +\beta \partial I_S\right)^{-1}\left( I -\beta \nabla f\right) (x^k)$$
再將這個格式打開：
\begin{align*}
& x^{k+1} =\left( I +\beta \partial I_S\right)^{-1}\left( I -\beta \nabla f\right) (x^k)\\
\iff & \left( I +\beta \partial I_S\right)(x^{k+1}) =\left( I -\beta \nabla f\right) (x^k)\\
\iff & x^k-\beta \nabla f(x^k)-x^{k+1}\in \beta \partial I_S(x^{k+1})\\
\iff & (x-x^{k+1})^\top \frac{1}{\beta}\left( x^k-\beta \nabla f(x^k)-x^{k+1} \right) \leq 0,\forall x \in S\\
\iff & (x-x^{k+1})^\top \frac{1}{\beta}\left( x^{k+1}-\left( x^k-\beta \nabla f(x^k) \right) \right) \geq 0,\forall x \in S\\
\iff & x^{k+1}=\mathop{argmin}\limits_{x} \{\frac{1}{2\beta}\Vert x-\left( x^k-\beta \nabla f(x^k)\right) \Vert^2 | x\in S\}
\end{align*}
這就推導出來臨近點梯度法的迭代格式：
$$x^{k+1}=\mathop{argmin}\limits_{x} \{\frac{1}{2\beta}\Vert x-\left( x^k-\beta \nabla f(x^k)\right) \Vert^2 | x\in S\}$$
進一步：
\begin{align*}
x^{k+1}=&\mathop{argmin}\limits_{x} \{\frac{1}{2\beta}\Vert x-\left( x^k-\beta \nabla f(x^k)\right) \Vert^2 | x\in S\}\\
=&\mathop{argmin}\limits_{x} \{\frac{1}{2\beta}\Vert x-x^k\Vert^2+\nabla f(x^k)^\top (x-x^k)+\frac{1}{2} \beta \Vert \nabla f(x^k) \Vert^2 | x\in S\}\\
=&\mathop{argmin}\limits_{x} \{f(x^k)+\nabla f(x^k)^\top (x-x^k) +\frac{1}{2\beta}\Vert x-x^k \Vert^2 | x\in S\}
\end{align*}
可以看出臨近梯度法實際上是將目標函數在當前迭代點進行二次近似得到下一個迭代點。

復合凸優化臨近點梯度法
求解復合凸優化問題：
\begin{align*}
\mathop{min}\limits_{x} & \quad f(x)+\theta (x)\\
s.t. & \quad x \in S
\end{align*}
其中，$f$是可微凸函數，$f$是凸函數但不一定可微，$S$是凸集合。這個問題等價于:
\begin{align*}
\mathop{min}\limits_{x} & \quad f(x)+\theta (x)+I_S(x)\\
\end{align*}
其中$I_S$為集合$S$的指示函數。
對此，可以將目標函數中的$\theta (x)+I_S(x)$看成一個凸函數$(\theta+I_S)(x)$，則和第一部分一樣的操作，將優化問題轉化為不動點問題：
$$x^* =\left( I +\beta ( \partial \theta + \partial I_S) \right)^{-1}\left( I -\beta \nabla f\right) (x^*)$$
于是得到迭代方式：
$$x^{k+1} =\left( I +\beta ( \partial \theta + \partial I_S) \right)^{-1}\left( I -\beta \nabla f\right) (x^k)$$
再將這個格式打開：
\begin{align*}
& x^{k+1} =\left( I +\beta ( \partial \theta + \partial I_S) \right)^{-1}\left( I -\beta \nabla f\right) (x^k)\\
\iff & \left( I +\beta ( \partial \theta + \partial I_S\right)(x^{k+1}) =\left( I -\beta \nabla f\right) (x^k)\\
\iff & x^k-\beta \nabla f(x^k)-x^{k+1}\in \beta \partial( \theta + I_S)(x^{k+1})\\
\iff & \theta(x) + I_S(x) -\left(\theta(x^{k+1}) + I_S(x^{k+1}) \right) -(x-x^{k+1})^\top \frac{1}{\beta}\left( x^k-\beta \nabla f(x^k)-x^{k+1} \right) \geq 0 , \forall x
\end{align*}
根據最后一個不等式，取$x \in S$，這樣可以通過反證法得到$x^{k+1} \in S$，于是：
\begin{align*}
& \theta(x) + I_S(x) -\left(\theta(x^{k+1}) + I_S(x^{k+1}) \right) -(x-x^{k+1})^\top \frac{1}{\beta}\left( x^k-\beta \nabla f(x^k)-x^{k+1} \right) \geq 0 , \forall x \\
\iff & \theta(x) + I_S(x) -\theta(x^{k+1}) +(x-x^{k+1})^\top \left( x^{k+1} -\left( x^k-\beta \nabla f(x^k)\right) \right) \geq 0 , \forall x \\
\iff & \theta(x) -\theta(x^{k+1}) +(x-x^{k+1})^\top \frac{1}{\beta}\left( x^{k+1} -\left( x^k-\beta \nabla f(x^k)\right) \right) \geq 0 , \forall x \in S \\
\iff &x^{k+1}=\mathop{argmin}\limits_{x} \{\theta(x)+\frac{1}{2\beta}\Vert x-\left( x^k-\beta \nabla f(x^k)\right) \Vert^2 | x\in S\}
\end{align*}
這就推導出來臨近點梯度法的迭代格式：
$$x^{k+1}=\mathop{argmin}\limits_{x} \{\theta(x)+\frac{1}{2\beta}\Vert x-\left( x^k-\beta \nabla f(x^k)\right) \Vert^2 | x\in S\}$$
進一步：
\begin{align*}
x^{k+1}=&\mathop{argmin}\limits_{x} \{\theta(x)+\frac{1}{2\beta}\Vert x-\left( x^k-\beta \nabla f(x^k)\right) \Vert^2 | x\in S\}\\
=&\mathop{argmin}\limits_{x} \{\theta(x)+ \frac{1}{2\beta}\Vert x-x^k\Vert^2+\nabla f(x^k)^\top (x-x^k)+\frac{1}{2} \beta \Vert \nabla f(x^k) \Vert^2 | x\in S\}\\
=&\mathop{argmin}\limits_{x} \{\theta(x)+f(x^k)+\nabla f(x^k)^\top (x-x^k) +\frac{1}{2\beta}\Vert x-x^k \Vert^2 | x\in S\}
\end{align*}
可以看出臨近梯度法實際上是將目標函數中的可微的部分在當前迭代點進行二次近似得到下一個迭代點。