本文主要是关于最优化的学习笔记,参考的来源有各个博客,教材。
梯度类方法(gradient)
梯度类方法是无约束优化中非常常用的方法。其基本依据是梯度的负方向是函数值下降最快的方向。
Gradient Descent
梯度下降法的迭代公式为:
x(k)=x(k−1)−tk∇f(x(k−1)) 上标(k)表示第k次迭代,而tk则表示步长,∇f(x(k−1))表示在点x(k−1)的梯度。
不同的步长tk会影响收敛的速度。最简单的方法是选一个恒定的步长,当然也可以选择可变的(adaptive)的步长,即根据每次迭代依照一定的规则来改变步长。下面介绍两种:(1)backtracking line search (2) exact line search。
backtracking line search
先选择两个固定参数α,β,要求0<β<1,0<α<1/2
每次迭代的时候,判断以下公式成不成立:
f(x−t∇f(x))>f(x)−at∣∣∇f(x)∣∣22 成立则改变步长为t=βt, 否则步长保持不变。其逻辑是假如步长太大使得假想点超过来最优点,则减少步长。否则就保持步长不变。
extact line search
先计算当前点的梯度∇f(x(k−1))。设tk=z,则求以下函数的导数:
f(z)=f(x(k−1)−z∇f(x(k−1)))∂z∂f(z)=0
求出的tk则为最优步长,使得当前的迭代下降的距离最大。这种方法也被称为最速下降法。
Subgradient Descent
subgradient descent相比于gradient descent可用于求导某些连续不可导的函数梯度不存在的问题。对于可微的凸函数,一阶特性可以表达为:
f(y)≥f(x)+∇Tf(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对应如下的一个优化问题 wmini=1∑N(wTxi−yi)2+λj=1∑n∣wj∣ 整体上来看,红色的部分是Likelihood function,而蓝色的部分则叫做regularizer。其中xi是数据或特征量,yi是对应的值,wj便是向量w的第j该 component,该优化问题使用线性回归模型去拟合给定的数据,而向量w∈Rn。当regularizer系数λ控制得当的话,最优解w则会有很多的component会是零。
要得到最优解,则一个重要部分是需要对regularizer中的l1−norm求导。首先,得要知道对于一个可测函数,存在以下性质: f(x)=f+(x)−f−(x),∣f(x)∣=f+(x)+f−(x)
f+(x)和f−(x)分别称为f(x)的正部和负部。回到LASSO优化问题,任意实数wj也可以表示成正部和负部之差wj=w+j−wj−。因此,LASSO优化可以等价于 w+,w−mini=1∑N((w+−w−)Txi−yi)2+λj=1∑N(wj++wj−)s.t. w+≥0,w−≥0
Back to top