总目录

一、 凸优化基础（Convex Optimization basics）

1. 凸优化基础（Convex Optimization basics）

二、 一阶梯度方法（First-order methods）

1. 梯度下降（Gradient Descent）
2. 次梯度（Subgradients）
3. 近端梯度法（Proximal Gradient Descent）
   待更新。。。

Introduction

对于一个可微的凸函数$f$f，其一阶特性有：
$f(y)\geq f(x)+\nabla f(x)^T(y-x)$f(y)≥f(x)+∇f(x)T(y−x)

而当凸函数$f$f是不可微的，我们也可以根据该性质来定义其次梯度。

次梯度

一个凸函数$f$f在$x$x的次梯度$g$g定义为：
$f(y)\geq f(x)+g^T(y-x)$f(y)≥f(x)+gT(y−x)

次梯度的一些特性：

1. 总是存在于定义域$dom(f)$dom(f)的内部；
2. 如果$f$f在$x$x是完全可微的，那么其存在唯一的次梯度$g=\nabla f(x)$g=∇f(x)；
3. 该次梯度的定义也可以推广到非凸函数中，但非凸函数的次梯度$g$g可能不存在。

例子：考虑函数$f: R\rightarrow R$f:R→R的形式为$f(x)=|x|$f(x)=∣x∣，其在$x=0$x=0处有一个不可微的点。

• 对于$x\neq 0$x​=0,其次梯度是唯一的且为$g=sign(x)$g=sign(x)；
• 对于$x=0$x=0，其次梯度可以是$[-1,1]$[−1,1]区间中的任意一个数。

次微分

凸函数$f$f的所有亚梯度组成的集合叫做次微分（subdifferential）:
$\partial f=\{g\in R^n: g\ {\rm is\ a\ subgradient\ of}\ f\ {\rm at}\ x\}$∂f={g∈Rn:g is a subgradient of f at x}

次微分的一些性质：

• 非空（仅仅对于凸函数）；
• $\partial f(x)$∂f(x)是封闭且凸的（即使对于非凸函数也成立）；
• 如果$f$f在$x$x点是可微的，则$\partial f(x)=\{\nabla f(x)\}$∂f(x)={∇f(x)}；
• 如果$\partial f(x)=\{g\}$∂f(x)={g}，那么$f$f在$x$x点是可微的，且$\nabla f(x)=g$∇f(x)=g。

最优化条件

对于任意$f$f（无论是不是凸函数）都有，
$f(x^*)=\min_x f(x) \Leftrightarrow 0\in \partial f(x^*)$f(x∗)=xmin​f(x)⇔0∈∂f(x∗)

也就是说，$x^*$x∗是最小值点当且仅当0是$f$f在$x^*$x∗点的一个亚梯度。

例子：软阈值
对于一个lasso问题，令$X=I$X=I将问题简化可得到：
$\min_\beta \frac{1}{2}\|y-\beta\|^2_2+\lambda\|\beta\|_1$βmin​21​∥y−β∥22​+λ∥β∥1​

其中，$\lambda>0$λ>0。利次梯度最优化条件可得：
$\begin{aligned} 0&\in \partial(\frac{1}{2}\|y-\beta\|^2_2+\lambda\|\beta\|_1) \\ &\Leftrightarrow 0\in y-\beta + \lambda \partial \|\beta\|_1\\ &\Leftrightarrow \left\{ \begin{aligned} &y_i-\beta_i = \lambda\cdot sign(\beta_i) \ & if\ beta_i\neq 0\\ &|y_i-\beta_i| \leq \lambda & if\ beta_i= 0 \end{aligned} \right. \end{aligned}$0​∈∂(21​∥y−β∥22​+λ∥β∥1​)⇔0∈y−β+λ∂∥β∥1​⇔{​yi​−βi​=λ⋅sign(βi​) ∣yi​−βi​∣≤λ​if betai​​=0if betai​=0​​

则最优解可得$\beta=S_{\lambda}(y)$β=Sλ​(y)，其中$S_{\lambda}$Sλ​叫做软阈值算子：
$[S_\lambda(y)]_i =\left\{ \begin{aligned} &y_i-\lambda \ & if\ y_i>\lambda\\ &0\ & if\ -\lambda\leq y_i\leq \lambda\\ &y_i+\lambda & if\ y_i<-\lambda \end{aligned} \right.$[Sλ​(y)]i​=⎩⎪⎨⎪⎧​​yi​−λ 0 yi​+λ​if yi​>λif −λ≤yi​≤λif yi​<−λ​

次梯度法

考虑一个定义域为$dim(f)=R^n$dim(f)=Rn的凸函数$f$f，但允许其可以是不可微的。类比于梯度下降法，次梯度法只是将其中的梯度替换为次梯度，其他步骤不变： 初始化$x^{(0)}$x(0)，然后重复:
$x^{(k)}=x^{(k-1)}-t_k\cdot g^{(k-1)},\quad k=1,2,3,...$x(k)=x(k−1)−tk​⋅g(k−1),k=1,2,3,...

其中$g^{k-1}\in \partial f(x^{(k-1)})$gk−1∈∂f(x(k−1))，是$f$f在$x^{(k-1)}$x(k−1)的任意一个次梯度。
值得注意的是，次梯度法并不一定是下降的，因此需要跟踪每次迭代，从中找到最优的迭代次数：
$f(x^{(k)}_{best})=\min_{i=0,...,k}f(x^{(i)})$f(xbest(k)​)=i=0,...,kmin​f(x(i))

步长的选择

次梯度法可以使用固定的步长，也可以随着迭代减小步长。但与梯度下降不同的是，次梯度法的步长需要提前设定，而不能自适应地计算得到。

收敛率分析

次梯度法有$O(1/\epsilon^2)$O(1/ϵ2)的收敛率，其慢于梯度下降的$O(1/\epsilon)$O(1/ϵ)收敛率。

投影次梯度法

考虑有约束的优化问题，在一个凸集$C$C上优化凸函数$f$f：
$\min_xf(x)\quad subject\ to\ x\in C$xmin​f(x)subject to x∈C

我们可以使用投影次梯度法（projected subgradient method）。在每次迭代中，首先像处理无约束问题一样，使用次梯度法进行求解，然后将得到的解投影到$C$C上：
$x^{(k)}=P_c(x^{(k-1)}-t_k\cdot g^{(k-1)}),\quad k=1,2,3,...$x(k)=Pc​(x(k−1)−tk​⋅g(k−1)),k=1,2,3,...

其中，$P_c$Pc​是投影算子。假设我们总可以做投影，那么在相同步长下，可以得到与普通次梯度法相同的收敛率。

参考资料

CMU：Convex Optimization