GAMES103课程笔记08-Finite Element Method II

这个系列是GAMES103：基于物理的计算机动画入门(GAMES 103: Intro to Physics Based Animation)的同步课程笔记。本课程是计算机动画的入门课程，着重介绍各种基于物理的动画仿真模拟技术。本节课继续介绍有限元在物理仿真中的应用。

Hessian of Elastic Energy

Implicit Integration

Nonlinear Optimization

很多仿真问题可以等价地表示为一个优化问题，因此我们需要介绍如何来求解非线性优化。

Gradient Descent

求解非线性优化的基本方法是梯度下降(gradient descent)。对于目标函数$F(\mathbf{x})$，我们可以通过不断地沿负梯度方向前进来获得极小值点：

显然步长(step size)对于整个优化的过程非常重要。更新步长的方法包括line search以及backtracking line search等：

Descent Methods

同样地，前进的方向$\mathbf{d}(\mathbf{x})$也对优化问题非常重要。实际上我们并不需要严格地按照梯度方向来前进，只要夹角在负梯度方向在同一面上即可。只要步长足够小就可以保证优化目标不断下降：

$$F(\mathbf{x})<F(\mathbf{x}+\alpha \mathbf{d}(\mathbf{x}))$$

不同的优化算法定义了不同的优化方向，很多高阶的优化算法还会修正梯度方向从而加快收敛的速度。其中牛顿法就使用了Hessian矩阵的逆来修正梯度方向，当Hessian矩阵正定时牛顿法可以保证收敛：

在很多情况下计算$F$的Hessian矩阵可能非常困难，在这样的情况下就需要对Hessian矩阵进行近似：

在物理仿真中我们需要关注优化算法的求解效率，因此图形学中常用的优化算法和科学计算中的优化算法还是具有一定的差异。

Reference

• Lecture 8: Finite Element Method II
• Nonlinear Material Design Using Principal Stretches
• Descent Methods for Elastic Body Simulation on the GPU