凸优化学习（2）——梯度类方法求解(gradient descent)

🍅 写在前面
👨‍🎓 博主介绍：大家好，这里是hyk写算法了吗，一枚致力于学习算法和人工智能领域的小菜鸟。
🔎个人主页：主页链接（欢迎各位大佬光临指导）
⭐️近期专栏：机器学习与深度学习
                       LeetCode算法实例
                       张量分解

凸优化系列知识，详见下方链接：

凸优化学习(1)——什么是凸优化、凸集、凸函数
凸优化学习（2）——梯度类方法求解(gradient descent)
本系列文章主要参考：卡耐基梅隆 凸优化系列课程

综述

1、梯度类方法是无约束方法中最常用的方法之一， 其依据是梯度的负方向就是函数值下降最快的方向。但是，常用的梯度下降(gradient descent)方法中，必须要求目标函数连续且可导，对于连续不可导的问题，梯度下降方法无能为力。
2、这里还将介绍另外两种针对目标函数连续不可导可用的优化方法，分别是subgradient descent 和 proximal gradient descent

gradient descent

一般梯度下降的基本迭代公式为：

$$x^k=x^{k-1}-t_k\nabla f(x^{(k-1)})$$
式子中的k表示的是第k次迭代，$t_k$表示的是学习率（步长），$\nabla f(x)$表示的是点在x处的梯度。
这里针对学习率是否改变以及如何改变又有不同的方法。最简单的当然是固定学习率为一个恒定值，但是学习率如果过大或者过小，可能会导致结果难以收敛或者收敛速度很慢。因此，产生了可变学习率的方法。可变学习率的思想是：每次迭代中根据一定规则更新现有的学习率。下面介绍两种可变学习率的方法。

backtracking line search

backtracking line search 方法需要先固定两个参数 $\alpha \beta$，并要求$0<\alpha <1/2$，$0<\beta <1$。每次迭代时，计算下列式子判断是否需要更新学习率：

$$f(x-t\nabla f(x))>f(x)-\alpha t{{\Vert \nabla f(x)\Vert }_2}^2$$
如果式子成立，则改变学习率为$t=\beta t$。这种方法的思想是当步长过大的时候 (即跨过了最优点)，减小步长，否则保持步长不变

exact line search

exact line search方法则是先计算出梯度$\nabla f(x^{(k-1)})$，然后带入下列函数中，此时函数中只有$t_k$学习率未知，因此有对$t_k$求导并另导数等于零，求得的$t_k$则为当前的最优学习率，因为这个学习率能够令当前迭代下降的距离最大。该方法也被称为最速梯度下降法。

$$f(x^{(k-1)}-t_k\nabla f(x^{(k-1)}))$$

subgradient descent

subgradient descent用于解决某些函数存在连续不可导，梯度不存在的问题。

次梯度

一个凸函数f在x的次梯度g定义为：

$$f(y)\ge f(x)+g^T(y-x)$$
次梯度的一些特性：
1、总是存在于定义域dom(f)的内部；
2、如果f在x上是完全可微的，那么其存在唯一的次梯度$g=\nabla f(x)$；
3、该次梯度的定义也可以推广到非凸函数中，但非凸函数的次梯度g gg可能不存在。
举例：
$f(x)=\left|x\right|$，在x=0处不可导，图像如下。

其次梯度为：

proximal gradient descent

proximal 通过对原问题的拆分并利用 proximal mapping，能够解决 subgradient descent 无法解决的问题。一般来说，该方法将目标函数转化为一下形式：
$$f(x)=g(x)+h(x)$$
其中，g(x)是凸且可微的，h(x)是凸函数。则proximal gradient descent方法的迭代过程如下：
$$x^{(k)}=x^{(k-1)}-t_k{G}_{tk}(x^{(k-1)})G_t(x)=\frac{x-pro{x}_{th}(x-t\nabla g(x))}{t}pro{x}_{th}(x)$$
其中：
$$pro{x}_{th}(x)=\arg \underset{z\in R^n}{\min }\frac{1}{2t}{{\Vert x-z\Vert }_2}^2+h(z)$$

以上是本节梯度方法求解凸优化问题，下一节总结对偶方法解决梯度问题。