优化方法（2020.08.04）

前言

刚开开始学习图形学的小白，博客中如果有错误的地方欢迎评论指正，大家一起进步。

数值优化问题

• x通常是多维的x=[x₁,x₂,x₃……,x_n]

凸优化和非凸优化

区分凸优化和非凸优化

如果优化问题中的目标函数和约束函数都是凸函数，即对于任意的x,y∈Rⁿ和α，β∈R且满足α+β=1，α≥0，β≥0，下述不等式成立

• 约束函数为凸函数
  

凸优化和非凸优化的主要区别

凸优化和非凸优化的主要区别在于凸优化可以很方便的找到一个全局的最优解，从任意一点出发很容易找到极值所在。非凸优化可找到局部最优解，但是很难找到全局最优解。

梯度和Hessian矩阵

函数ƒ(x)的梯度：
$$\nabla f(x)={\left(\frac{\partial f}{\partial x_1},...,\frac{\partial f}{\partial x_n}\right)}^T$$
梯度就是对每个函数求导，结果是一个n*1的向量
函数ƒ(x)的Hessian矩阵：
$${\nabla }^{2}f(x):={\left[\frac{{\partial }^{2}f}{\partial x_i\partial y_i}\right]}_{i=1,...,n,j=1,...,n}$$
Hessian矩阵就是梯度再对x求导，结果是一个n*n的矩阵

举个例子

Karush-Huhn-Tucker(KKT)条件——判断x*是否为最优解的必要条件

无约束条件下的极值

无约束条件指的是只有目标函数而没有约束函数。
这种情况下只要x*满足$\nabla f(x^{\ast })=0$,即在极值点函数的梯度等于0，我们可以通过图像很清楚的体会到，这二维平面上，图形的梯度可以理解为我们高中学习过的导数。

等式约束条件下的极值

不等式约束下的极值

另外一种情况（最小值不受约束条件边界约束）

总计KKT条件

无约束和带约束条件的解决方法

• 无约束优化最为简单，直接令梯度等于0计算就可以
• 但是带等式约束优化，带等式约束和不等式约束优化的问题，则需要KKT条件求解

无约束优化

无约束优化——梯度下降法

缺点：在靠近最优解周围时会下降的特别缓慢

无约束优化——牛顿法

需要对函数求二阶导，求函数在x处的二阶泰勒展开
缺点：

• 纯牛顿法步长为1，但是可能导致不收敛。阻尼牛顿法会通过直线搜索确定合适的步长
• 牛顿法每一次迭代都求解一个线性方程组，可能计算代价大
• 牛顿法需要梯度和Hessian矩阵
• 如果Hessian矩阵不正定：
  

无约束优化——拟牛顿法

拟牛顿法使用一个代理矩阵近似Hessian矩阵的逆：B≈H^-1。
求解牛顿方向变为矩阵乘法：s= -Bg
避免了一些牛顿法的一些弊端：

• 如果Hessian矩阵不正定，牛顿法失效
• 牛顿法需要二阶导数
• 牛顿法每次迭代要求解线性方程组

BFGS拟牛顿法

缺点：BFGS的缺点是代理矩阵B是一个实矩阵，因此不适合用于大规模优化问题。

L-BFGS拟牛顿法（limited BFGS拟牛顿法）

所谓L-BFGS是对BFGS进行了空间优化：BFGS的代理矩阵需要相当大的内存，L-BFGS算法并没有直接存储整个矩阵，只保存了最近的m词迭代的结果，所以L-BFGS算法又对BFGS做了近似。

等式约束优化

等式约束的牛顿法

消除等式约束

不等式约束优化

内点法

作业

给定一系列三维点，使用matlab求这些点的最小二乘平面。