1 无约束问题定义

min f_o(x),其中f_o(x)为二次可微凸函数。

假定该问题可解，即：一定存在最优解x^*

2 迭代算法求解

一般情况下，优化问题都是采用迭代算法求解。

当k趋近于无穷大时，f(x^(k))趋近于最优值p^*

当f(x^(k))-p^* <= e时算法将终止。e>0为我们所能允许的误差

x^(k+1)=x^(k)+s^(k)+d^(k)

d^(k)为k时刻的搜索方向，s^(k)为k时刻的搜索步长

一个通用的下降算法可以描述为

给定初始点 x₀
重复进行：
1 确定下降方向d^(k)
2 确定步长s^(k)
3 修改x^(k+1)=x^(k)+s^(k)+d^(k)
直到 满足停止条件

3 搜索步长

1 精确搜索：

s^(k) = argmin f(x^(k) + td^(k))其中t>=0

表示从当前点出发，沿着搜索方向所在的射线上，找到使目标函数值最小的步长。（因为原问题是最小化目标函数）

当求解该问题成本较低时，可以采用该方法。该方法称为精确直线搜索。

实际中，如果计算成本很高的话，因为此问题也是一个优化迭代过程，相当于将问题复杂化了。因此我们一般采用不精确搜索

2 不精确搜索

找到一个还可以的步长，使其在搜索方向上让目标函数值有所下降

Amijo Rule

给定初始步长t_max,一般取1
如果f(x+t*\Deltax) > f(x) + af’(x)t\Deltax则令t = bt
否则，停止，得到步长t

其中，a一般取(0,0.5)衡量下降的显著程度,b一般取(0,1)按比例缩小步长
如下图所示。

4 离目标有多远

当我们使用迭代算法得到一个x’时，离我们最终的最优解x^*有多远
x’对应的值f(x’)与最优值p^*有多远

限定f(x)二阶可微且强凸
强凸即存在m,使得f(x)的二次hessien矩阵减去mI为正定。
此约束是限定目标函数不能有一个特别平的底部

这时候我们会得到一些有意义的结果：

对于定义域内任意x,y
二阶泰勒展开近似：
f(y)=f(x)+f’(x)(y-x)+0.5 f’’(x)(y-x)²
==》f(y)>=f(x)+f’(x)(y-x)+m/2*||(y-x)||²

当f(x)的导数趋近于0时，f(x’)与最优值p^*有多远

不等式右边是关于y的凸函数。求导可以得到：
f’(x)+m(y-x)= 0,得到y再带入不等式，有
f(y)>=f(x)-1/(2m)*f’(x)²
当f(y)为最优值p^*时不等式仍旧成立。
此时f(x)与p^*的距离小于等于1/(2m)*f’(x)²

当f(x)的导数趋近于0时，x’与最优解x^*有多远

p* = f(x’) >= f(x)+f’(x)(x’-x)+m/2*||(x’-x)||²
>= f(x)+f’(x)||x’-x||+m/2*||(x’-x)||²
由于f(x)大于等于p*成立。所以后面项一定小于等于0
所以x’与x^*的距离小于等于2/m||f’(x)||

总结

当m很小时，导数趋近于0时，最优解趋近时，最优值离的很远。我们得到最优值得同时，可能不能得到最优解
当函数强凸时，即底部不那么平时，我们可以通过求值或者求解来量化这个过程

5 搜索方向

1 梯度下降法：

负梯度的方向

2 最速下降法

根据一节泰勒展开的近似
f(x+v) = f(x)+f’(x)v,第二项为f在x处沿方向v的方向导数。定义一个规范化的最速下降方向
d = argmin{f’(x)v| v的范数为1}
当取1范数时，如果导数分量方向为正，那么该维度坐标轴为1.为负，为-1.组成的新的方向可能与梯度方向不是同一个方向
当取2范数时，与梯度下降方向相同
当取无穷范数时，导数分量最大元素为+1，最小元素为-1，其他为0

3 梯度下降与最速下降法变种

坐标轮换法：参考1范数
分块的坐标轮换法：参考1范数

次梯度下降法：

当f(x)在某些点不可微时，梯度下降法均不可用
次梯度算子

当左右极限的符号不相同时，说明已经达到了最优点

4 牛顿法

牛顿法依靠的是二阶泰勒展开近似
f(x+v) = f(x)+f’(x)v+0.5f’’(x)v²
对v求一阶偏导，得到梯度方向：
-[f’’(x)]^-1f’(x)
即对负梯度方向做了变换之后的方向
注意的是：
牛顿法在x接近x^*时能够更加快速的靠近
是因为，二阶泰勒展开，在很近的时候才会更准确。
所以当离的很远的时候，搜索的方向可能不是最正确的方向。
但是当离的很近的时候，泰勒二次展开已经接近于目标函数了，这时候得到的搜索方向也是最准确的
这也是为什么有阻尼牛顿法
注意2
涉及到二阶导（即hessien矩阵)的逆，实际中一般不直接对hessien矩阵求逆，而是将其转化成线性方程组H^(k)*d^(k)=-f’(x^(k))的方式，此时可根据H^(k)的特性选择合适的迭代法。如预条件共轭梯度法（PCG），代数多重网格法（AMG）等

4 牛顿法变种

现实中，直接求解二阶导（即hessien矩阵）不是很好求，因此出现了很多替代hessien矩阵的方式。例如BFGS等

5 拉格朗日法

理念：只要与原方向夹角小于90度，一定可以使函数值有所下降

6 增广的拉格朗日法

在拉格朗日函数上增加惩罚项

性质1：
若v=v^*（求得对偶问题最优解），
相当于求解鞍点值（最大最小等于最小最大），会得到原问题最优解

性质2：
若惩罚因子C趋近于无穷大，相当于求解KKT条件

在实际中，增广拉格朗日方法可以很有效的处理边界约束和线性约束最优化问题。

参考：
[1]、《凸优化》，Stephen Boyd等著，王书宁等译
https://blog.csdn.net/itplus/article/details/21896453
https://blog.csdn.net/itnerd/article/details/86012869