无约束最优化方法（一）

无约束最优化问题大致分成两类，一类在计算过程中用到目标函数的导数；另一类只用到目标函数的值。本文先从使用导数的最优化问题切入。

考虑无约束最优化问题：

$min_{x\in R^{n}} f(x)$

其中$f(x)$具有一阶连续偏导数。

【最速下降方法思想】

自然的想法，从某一点出发，选择一个目标函数值下降最快的方向，以利于尽快达到极小点。函数$f(x)$在点$x$处沿方向$d$的变化率可用方向导数来表示。对于可微函数，方向导数等于梯度与方向的内积，即$Df(x;d)=\bigtriangledown f(x)^{T}d$

因此，求函数$f(x)$在点$x$处的下降最快的方向，可以归结为求解下列非线性规划：

$min \quad\bigtriangledown f(x)^{T}d$

$s.t. \lVert d \rVert \leq 1$

 根据Schwartz不等式有$\lvert\bigtriangledown f(x)^{T}d \rvert \leq \lVert\bigtriangledown f(x) \rVert \lVert d \rVert \leq \lVert\bigtriangledown f(x) \rVert$

去掉绝对值符号可得    $\bigtriangledown f(x)^{T}d \ge -\lVert\bigtriangledown f(x) \rVert$

可知当              $d=-\frac{\lVert\bigtriangledown f(x) \rVert}{\bigtriangledown f(x)}$

时等号成立。因此在点$x$处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。

注意：在不同尺度下最速下降方向是不同的。这里定义的最速下降方向，是在向量$d$的欧式范数$\lVert d \rVert_{2}$不大于1的限制下得到的，属于欧式度量意义下的最速下降方向。

另外，梯度下降的迭代公式可由函数的一阶泰勒展开近似得到，将$f(x)$在$x^{(k)}$附近一阶泰勒展开

$f(x)\approx f(x^{(k)})+g^T_k(x-x^{(k)})$

这里，$g_k=g(x^{(k)})=\nabla f(x^{(k)})$为$f(x)$在$x^{(k)}$的梯度。

【最速下降算法】

最速下降法第$k+1$次的迭代公式是

$x^{(k+1)}\leftarrow x^{(k)}+\lambda_{k} d^{(k)}$

其中$d^{(k)}$是从$x^{(k)}$出发的搜索方向，取在点$x^{(k)}$处的最速下降方向，即$d^{(k)}=-\nabla f(x^{(k)})$，可使函数下降最快，$\lambda_{k}$是从$x^{(k)}$出发沿方向$d^{(k)}$进行一维搜索的步长，即满足

$f(x^{(k)}+\lambda_kd^{(k)})=\min_{\lambda\ge0} f(x^{(k)}+\lambda d^{(k)})$

计算步骤如下：

（1）给定初始点$x^{(1)}\in R^{n}$，允许误差$\epsilon>0$，置$k=1$

（2）计算搜索方向$d^{(k)}=-\nabla f(x^{(k)})$

（3）若$\lVert d^{(k)} \rVert \leq\epsilon$，则停止计算；否则，从$x^{(k)}$出发沿方向$d^{(k)}$进行一维搜索的步长，求$\lambda_{k}$，使

$f(x^{(k)}+\lambda_kd^{(k)})=\min_{\lambda\ge0} f(x^{(k)}+\lambda d^{(k)})$

（4）令$x^{(k+1)}=x^{(k)}+\lambda d^{(k)}$，置$k:=k+1$，转步骤（2）

最速下降法的收敛性：

最速下降算法在一定条件下是收敛的。

定理1：设$f(x)$是连续可微实函数，解集合$\Omega={\bar{x}|\bigtriangledown f(\bar{x})=0}$，最速下降法产生的序列$x^{(k)}$含于某个紧集，则序列$x^{(k)}$的每个聚点$\hat{x}\in\Omega$。证明略。

最速下降法产生的序列是线性收敛的，且收敛性质与极小点处Hesse矩阵$\bigtriangledown^{2}f(\bar{x})$的特征值有关。

定理2：设$f(x)$存在连续二阶偏导数，$\bar{x}$是局部极小点，Hesse矩阵$\bigtriangledown^{2}f(\bar{x})$的最小特征值$a>0$，最大特征值为$A$，算法产生的的序列$x^{(k)}$收敛于点$\bar{x}$，则目标函数值的序列$\{f(\bar{x})\}$以不大于$(\frac{A+a}{A-a})^{2}$的收敛比线性地收敛于$f(\bar{x})$。

在上述定理中，若令$r=A/a$，则$(\frac{A+a}{A-a})^{2}=(\frac{r+1}{r-1})^{2}<1$，$r$是对称正定矩阵$\bigtriangledown^{2}f(\bar{x})$的条件数(condition number)。这个定理表明，条件数越小，收敛越快；条件数越大，收敛越慢。

首先需要提出的是用最速下降法极小化目标函数时，相邻两个搜索方向是正交的。

简要的进行证明，令

$\varphi(\lambda)=f(x^{(k)}+\lambda_kd^{(k)})$，

$d^{(k)}=-\nabla f(x^{(k)})$

为求出从从$x^{(k)}$出发沿$d^{(k)}$的极小点，进行一维搜索，令

$\varphi^{'}(\lambda)=\bigtriangledown f(x^{(k)}+\lambda_kd^{(k)})^{T}d^{(k)}=0$，

所以$-\bigtriangledown f(x^{(k+1)})^{T}\bigtriangledown f(x^{(k)})=0$，即方向$d^{(k+1)}=-\nabla f(x^{(k+1)})$与$d^{(k)}=-\nabla f(x^{(k)})$正交。这就造成了最优步长的最速下降法逼近极小点过程是“之”字形，并且越靠近极小点步长越小，移动越慢，这样就呈现出“锯齿现象”以至在实际运用中在可行的计算时间内得不到需要的结果。

这似乎与“最速下降”的名称矛盾。其实不然，因为梯度是函数局部性质，从局部看，最速下降方向确实是函数值下降最快的方向，然而从整体看，由于锯齿现象的影响，则走过了许多弯路，使收敛速度大为减慢。最速下降法并不是收敛最快的方向。

所以，最速下降法一般适用于计算过程的前期迭代或作为间插步骤，当接近极小点时，再使用最速下降法，试图用这种方法达到迭代的终止，则并不有利。

LR模型及梯度下降法应用：

关于随机梯度下降法与批量下降法，大多数用梯度下降是求无约束目标函数，例如求经验损失最小时函数的参数，含有大量的训练数据。批量下降法是同时使用所有数据对梯度进行更新，很显然需要好多次迭代。随机梯度下降是每次只使用一个数据对函数参数进行更新，这样往往只通过一部分数据更新参数就会收敛，但是由于每次根据一个数据跟新，容易造成噪音问题。

随机梯度下降法步长的选择

以前网上有看到过，说是最好按3倍来调整，也就是0.00001、0.00003、0.0001、0.0003、0.001、0.003、0.01、0.03、0.1、0.3……然后确定范围之后再微调。

如果α取值过大，可能会导致迭代不收敛，从而发散。所以，一开始α的取值也要比较小心才行。

随着迭代次数的增加，一般需要慢慢减小α，因为这样能得到一个更好的结果。至于怎么减小α，也是有很多种策略，可以每次迭代都更新α的值，如α *= 0.96， 也可以 α*=α, 也可以每迭代几次更新一次α的值，方法很多，什么方式更好呢？实验吧……这跟数据有很大关系。

关于正则化参数λ的取值，因为才疏学浅，了解得不多，所以不便多说。不过一般来说λ不会取太小，我的感觉是0.001和1之间吧，也可以每次迭代都更新λ的值。比如一开始取比较小的值，然后随着迭代次数的增加，慢慢增加λ。

总结下，学习速率α越大，收敛越快，正则化参数λ越大，收敛越慢。收敛速度太快，可能一下子就越过极值点，导致发散；太慢则可能需要迭代非常多次，导致时间成本非常高。所以，α和λ取到一个合适的值，还是非常重要的。

刚看到一种调整α的方法，就是 $\alpha_{k} = \alpha_{0} \frac{\tau}{\tau+k}$ ， 当然，α的初始值也不能太大，不然还是会发散。

这个策略一个不好的地方就是 $\tau$ 的取值问题，糟糕的取值可能会导致收敛非常慢。

 

参考资料：
1、陈宝林编著，“最优化理论与算法”
2、http://blog.csdn.net/lilyth_lilyth/article/details/8973972
3、http://www.tuicool.com/articles/auQFju
4、