GAMES103笔记 弹性体模拟中的非线性优化

GAMES103课程主页：GAMES103：基于物理的计算机动画入门 - 计算机图形学与混合现实研讨会

GAMES103 系列笔记目录

这是一个和数学相关的小篇章。

之前在 GAMES103笔记 Lecture5 基于物理的布料模拟（Physics-based Cloth Simulation 中讲隐式积分求解弹簧系统的时候提到了用牛顿迭代法来解优化问题，GAMES103笔记 Lecture 6 基于约束的布料模拟方法（Constrained Approaches）中讲 PD 方法时又提到 PD 方法相当于用常数矩阵替代隐式积分的 Hessian 来简化计算。为什么这么做有效？今天我们从非线性优化框架的角度来理解这个问题。

相信很多人都听说过梯度下降法，这是现在深度学习技术中必不可少的基础方法。

要最小化目标函数，沿着梯度的反方向走一小步，不断走下去就能到达函数的最低点。

其中走的步长 $\alpha$ （深度学习中叫学习率）非常重要。

除了手工调整以外，有一种让程序自己尝试的方法 backtracking line search。

只要走的这一步确实让目标函数值下降了，就接受这个步长，否则减少步长。

梯度下降法走让函数值下降最快的方向。除了按梯度的方向走，还有很多方向也可以让函数值下降，只要保证走的方向 $\mathbf{d}(\mathbf{x})$ 与负梯度的夹角小于180度（点乘大于 0） 即可。

如此一来，牛顿迭代法也可以归纳到这个框架中来。

牛顿法走的方向 $\mathbf{d}(\mathbf{x})=-\left(\frac{\partial^2 F(\mathbf{x})}{\partial\mathbf{x}^2}\right)^{-1} \nabla F(\mathbf{x})$

把它和负梯度做点乘发现，只要 Hessian 是正定的，点乘的结果就一定大于 0。

之前说 Hessian 一直正定会导致函数只有一个全局最小值，现在我们又发现只要在某个点 Hessian 正定，牛顿法就能向使函数值变小的方向走。

众多求解隐式积分的方法都能在这个框架中得到解释。

不同方法只是选取了不同的方向使函数值下降。

那么在图形学中哪种方法更好呢？每种方法都有效，还是要算总的开销。

要达到相同的误差，梯度下降法使目标函数值下降最快，总的迭代次数最少，但是每一轮迭代都要用求出准确的梯度，在每一轮中的开销较大。而牛顿法的总迭代次数最多，每轮的开销最小。其他方法介于两者之间。

更详细的分析可以参考王老师本人的论文 Wang. 2016. Descent Methods for Elastic Body Simulation on the GPU. TOG (SIGGRAPH Asia).