LASSO回归中的凸优化问题
本文主要是关于最优化的学习笔记，参考的来源有各个博客，教材。
梯度类方法(gradient)
梯度类方法是无约束优化中非常常用的方法。其基本依据是梯度的负方向是函数值下降最快的方向。
Gradient Descent
梯度下降法的迭代公式为：
x^{(k)} = x^{(k-1)} - t_k \nabla f(x^{(k-1)}) 上标(k)表示第k次迭代，而t_k则表示步长，\nabla f(x^{(k-1)})表示在点x^{(k-1)}的梯度。
不同的步长t_k会影响收敛的速度。最简单的方法是选一个恒定的步长，当然也可以选择可变的(adaptive)的步长，即根据每次迭代依照一定的规则来改变步长。下面介绍两种：(1)backtracking line search (2) exact line search。
backtracking line search
先选择两个固定参数\alpha, \beta，要求0 < \beta < 1，0< \alpha < 1/2
每次迭代的时候，判断以下公式成不成立：
f(x - t \nabla f(x)) > f(x) - at||\nabla f(x)||^2_2 成立则改变步长为t = \beta t, 否则步长保持不变。其逻辑是假如步长太大使得假想点超过来最优点，则减少步长。否则就保持步长不变。
extact line search
先计算当前点的梯度\nabla f(x^{(k-1)})。设t_k = z,则求以下函数的导数：
f(z) = f(x^{(k-1)} - z \nabla f(x^{(k-1)})) \\ \frac {\partial f(z)} {\partial z} = 0
求出的t_k则为最优步长，使得当前的迭代下降的距离最大。这种方法也被称为最速下降法。
Subgradient Descent
subgradient descent相比于gradient descent可用于求导某些连续不可导的函数梯度不存在的问题。对于可微的凸函数，一阶特性可以表达为：
f(y) \ge f(x) + \nabla^T f(x)(y-x)
对于函数f(x) = |x|, subgradient为
\begin{eqnarray} g = \{_{[-1, 1] \space \space x = 0}^{sign(x) \space \space x \neq 0}\\ \end{eqnarray}
Lasso的凸优化
LASSO对应如下的一个优化问题 \color{red}{\min_w \sum_{i=1}^N {(w^Tx_i - y_i)}^2} + \color{skyblue}{\lambda\sum_{j=1}^n |w^j|} 整体上来看，红色的部分是Likelihood function，而蓝色的部分则叫做regularizer。其中x_i是数据或特征量，y_i是对应的值，w^j便是向量w的第j该 component，该优化问题使用线性回归模型去拟合给定的数据，而向量w \in \mathbb{R^n}。当regularizer系数\lambda控制得当的话，最优解w则会有很多的component会是零。
要得到最优解，则一个重要部分是需要对regularizer中的\mathbb{l}_1-norm求导。首先，得要知道对于一个可测函数，存在以下性质： f(x) = f^+(x) -f^-(x), |f(x)| = f^+(x) + f^-(x)
f^+(x)和f^-(x)分别称为f(x)的正部和负部。回到LASSO优化问题，任意实数w^j也可以表示成正部和负部之差w^j = w_+^j - {w^j}_-。因此，LASSO优化可以等价于 \min_{w^+, w^-}\sum_{i =1}^{N}((w^+ - w^-)^Tx_i - y_i)^2 + \color{skyblue}{\lambda\sum_{j=1}^{N}{(w_j^+ + w_j^-)}} \\ s.t. \space{ } w^+ \ge 0,w^- \ge0