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

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 \]

相关