GAMES001课程笔记13-优化基础

这个系列是GAMES001-图形学中的数学(GAMES 001: Mathematics in Computer Graphics)的同步课程笔记。课程旨在总结归纳图形学学习过程中重要的数学概念、理论和方法，并将以索引的形式在每一章节中穿插讲解该数学专题在图形学中的应用。本课程既可以作为GAMES系列其它课程学习的基础或「手册」，也可以作为站在不一样的视角复习图形学知识的平台。本节主要介绍求解数学优化的相关技术。

数学优化是一个非常广泛且重要的研究领域。从形式上来看，优化问题的目标是最小化一个函数$f(x)$。在这个过程中，优化目标函数$f$和待优化的变量$x$既可以是离散的，也可以是连续的。同时，变量$x$还可能需要满足一定的约束条件$C$，记为$x\in C$。针对不同类型的优化问题，人们设计了各种优化算法来进行求解。

无约束优化

优化问题中最基础的是无约束优化问题。此时可以令$C$为全空间，同时假设$x\in {\mathbb{R}}^n$是连续的向量，且目标函数$f(x)$是连续可微的函数。

在这样的框架下，许多问题，例如最小二乘法、曲面参数化以及弹性体仿真等，都可以等价地表示为无约束优化问题。

线搜索

线搜索(line search)是求解无约束优化的一类经典方法，它的基本思想是从当前位置$x_k$出发向$p_k$方向移动${\alpha }_k$步长来逐步最小化目标函数。显然，线搜索方法的核心在于如何确定移动方向$p_k$以及步长${\alpha }_k$这两个量。

梯度下降

梯度下降(gradient descent)是线搜索中最常见的一种方法。在梯度下降算法中，我们选择目标函数的负梯度方向作为前进方向，即$p_k=-\mathrm{\nabla }f(x_k)$。而要确定移动步长${\alpha }_k$则相对复杂一些，实践中常使用Armijo条件来进行计算。

结合Armijo条件的梯度下降算法流程可以参考下面ppt。

牛顿迭代

梯度下降法只考虑了优化目标函数的一阶信息。为了获得更快的收敛速度，可以结合目标函数的二阶信息，此时得到的算法称为牛顿法。使用牛顿法时，通常要求目标函数在当前位置的Hessian矩阵为正定矩阵。如果Hessian矩阵不是正定的，则需要使用一些额外的方法将其转换为正定矩阵来进行处理。

牛顿法的算法流程可以参考下面的ppt。

与梯度下降法相比，牛顿法通常具有更快的收敛速度，并且可以避免一些震荡的情况。

拟牛顿法

牛顿法的一个缺陷在于每一步迭代中需要计算Hessian矩阵并求解线性方程组来获得前进方向。在某些问题中，这两个步骤可能比较困难且相对耗时。针对这样的问题，我们可以使用一个更容易计算的矩阵$B_k$来近似Hessian矩阵，这样的一类方法称为拟牛顿法。

BFGS算法是目前应用最为广泛的一种拟牛顿法。

BFGS算法的流程可以参考下面的ppt。

在BFGS算法的基础上，进一步发展出了L-BFGS算法，旨在降低算法在计算和存储方面的开销。目前，L-BFGS是许多数值计算软件中默认的优化算法。

不动点迭代

从优化的角度来看，我们之前介绍过的不动点迭代实际上也是一种拟牛顿法。

带约束优化

对于带约束的优化问题，约束可以分为等式约束以及不等式约束两类。

在物理仿真中的常见约束都可以转换为等式约束以及不等式约束。

等式约束

对于等式约束的情况，我们首先需要考虑在什么情况下目标函数能够达到最优。

以二维情况为例，只有在目标函数的梯度$\mathrm{\nabla }f(x,y)$与约束$g(x,y)$的梯度相互平行时能够达到最优，即$\mathrm{\nabla }f=\lambda \mathrm{\nabla }g$。

根据上面的分析可以得到等式约束条件下最优点$x^{\ast }$需要满足的条件：

$$g_i(x^{\ast })=0$$ $$\mathrm{\nabla }f(x^{\ast })=\sum _i{\lambda }_i\mathrm{\nabla }{g}_i(x^{\ast })$$

拉格朗日乘子法

更进一步，等式约束条件的最优化问题可以利用拉格朗日乘子进行处理。我们定义原始优化问题的拉格朗日函数为

$$L(x,{\lambda }_1,...,{\lambda }_n)=f(x)-\sum _i{\lambda }_i{g}_i(x)$$

则等式约束的最优解可以表示为

$$\mathrm{\nabla }L=0$$

这样约束优化问题就通过拉格朗日乘子转换为了无约束优化问题。然而，需要注意的是仅通过最小化$L$并不能保证得到问题的解，还必须确保$g_i(x)=0$始终成立。

Min-Max问题

实际上，与原始约束优化问题等价的拉格朗日优化问题是一个Min-Max问题：

$$\underset{x}{min}\underset{{\lambda }_i}{max}L(x,{\lambda }_1,...,{\lambda }_n)$$

对于Min-Max问题，我们无法直接使用前面介绍过的无约束优化方法进行求解。

对偶问题

直接求解Min-Max问题往往效率较低。在实践中，通常会将Min-Max问题转换为其对偶问题进行处理。这时需要交换最大化和最小化的顺序，先对$x$进行最小化，然后对$\lambda$进行最大化，从而将Min-Max问题转化为Max-Min问题。

对于一般的函数$L(x,\lambda )$，可以证明对偶问题是原始问题的下界，这称为弱对偶关系。而对于凸函数，可以证明原始问题和对偶问题是等价的，称为强对偶条件。

假设强对偶条件成立，则可以使用无约束优化问题的相关求解方法进行处理。

对偶上升法

对于对偶问题，我们可以使用对偶上升法交替更新$x$和$\lambda$进行求解。对偶上升法将原始的约束优化问题转换为了两个无约束优化问题，在优化$\lambda$时可以利用梯度下降法进行处理。

罚函数法

除了拉格朗日乘子法之外，对于等式约束的优化问题还可以使用罚函数法。其基本思想是将等式约束视为一个惩罚项，当$x$违反约束时施加相应的惩罚来约束$x$。然而，罚函数法无法保证约束一定能够严格满足，只能保证近似满足。实践中一般需要调节惩罚项系数$\mu$来保证优化能够收敛。

不等式约束

带有不等式约束的优化问题处理起来比等式约束更加复杂。关键在于，不等式约束只有在变成等式约束时才会直接影响最优解；否则，不等式约束相当于不起作用，此时可以按照无约束优化进行处理。

对于一般形式的不等式约束优化问题，我们同样可以定义拉格朗日函数并推导相应的对偶问题以及对偶优化算法。

Reference

• Lecture 14: 优化基础