Gradient descent for unconstrained problems
梯度下降法常常用于寻找一个多元函数的最大值，最小值问题。
梯度下降比较关心的两个问题是：
1. 如何实现，在每一次更新
，其中M：
2. 收敛速度的控制，这主要涉及到每次更新的stepsize的选择。
一 更新公式的由来
对于一个可微函数:
，构造这样一组有序数列{
}，使得
，t=0,1,2,...
引入向量,那么我们有
=
=
<0，其中
为在
处的梯度,
为梯度
沿着向量d的方向导数值。
由<0，可以知道当
为正数的时候，那么沿着向量d方向的增量，可以满足
, 如此就可以构造出这样一个符合
的一组有序数列{
}。
我们乘这样的一个方向向量梯度方向向量。
于是乎，在每一次的更新中，我们可以寻找这样的梯度向量
，来使得每一次更新都可以实现
，公式中的
其实就是我们需要定义的迭代步长
。
那么迭代更新公式也基本已经明了：
，其中
,
固定步长(constant stepsize)
收敛性
非固定步长
固定步长的缺点是我们需要知道矩阵Q的谱，简单地即矩阵Q的特征值情况，但是在实际生活中，往往计算Q的谱，是一个比较昂贵的操作，尤其是在Q比较复杂的情况下，有的时候Q是满秩，有的时候Q是不满秩。
因此有必要使用其他的方法来选择每一次的迭代步长。对于非固定步长，常用的方法是exact line search 和 backtracking research，来选取每一次迭代更新的步长。
下面先介绍 exact line search 方法
Exact line search
该方法的主要策略是每一次都去寻找这样的一个步长,使得:
这里不加证明地给出步长的更新公式：
下面推导收敛性：
这里如果再把带进去，就是一个收敛式子。
这个方法由于计算量也比较大，所以在日常的研究中，使用的频率不是特别高，大家了解一下就好。
下面在说backtracking search之前，先说一下convex和smooth性质的二阶可微函数
如果是
,
证明主要涉及到正定矩阵的一个性质：对于一个正定矩阵A，其满足
这里的
同样地，可以证明：
那么根据定义就有：
