数值优化：计算基本理论

1. 优化问题

　　最一般的优化问题的表述是这样的：

求解等式约束 $\boldsymbol{g}(\boldsymbol{x})=0$ 和不等式约束 $\boldsymbol{h}(\boldsymbol{x})\leq 0$ 下使得取得 $\min f(\boldsymbol{x})$ 的解 $\boldsymbol{x}$

其中 $f:\mathbb{R}^n\Rightarrow \mathbb{R}$，$\boldsymbol{g}:\mathbb{R}^n\Rightarrow \mathbb{R}^m$（即m个等式约束），$\boldsymbol{h}:\mathbb{R}^n\Rightarrow \mathbb{R}^k$（即k个不等式约束）

　　这里映射 $\boldsymbol{h}$ 所使用的小于号表示各个分量均小于零。当目标函数 $f$，等式约束函数 $\boldsymbol{g}$ 和不等式约束函数 $\boldsymbol{h}$ 要么缺省要么为线性函数时，该优化问题又称线性规划；否则（只要存在任意一函数非线性）即称为非线性规划。优化问题是数值计算中非常重要的一个问题。和非线性方程组求解一样，这个看似简单的问题也并没有可以直截了当地处理多数问题的silver-bullet，这一方面的理论比较复杂；此外，优化算法的应用领域极其广泛、地位极其重要，除了求解非线性方程组可以使用（matlab中最常用于解非线性方程组的函数fsolve就是使用优化方法，见MATLAB解方程内置函数详解）以外，在人工智能和机器学习领域也有很重要的地位。而不论是高中文科数学总要掌握的线性规划，还是基本的最小二乘问题（也是通常的线性回归使用的方法），其本质都是优化问题的一个特例。

　　高等数学的知识告诉我们，一维连续光滑函数取得极值的必要非充分条件是该点导数值为零。如果试图寻找函数在一定区间上的最值（最大/最小值），一般的方法是找出所有的极值点和端点比较其函数值。和这一方法一样，虽然优化问题的一般表述总是将“最值”作为追求的目标，在实际的算法中却几乎总是以求极值为出发点。至于求解总区间上的最值，总是比较复杂和困难，而且总是能够构造处一些函数，它的最值对于计算方法几乎不太可能求出。以下的讨论基本总是求解极值的算法。

2. 问题的性质

2.1 解的存在唯一性：

　　若函数 $f$ 在n维有界闭区域 $S$ 上连续，那么 $f$ 在 $S$ 上一定有全局最小值；

　　若函数 $f$ 在n维闭区域 $S$ 上连续并且向正无穷发散(coercive，即 $\lim\limits_{||x||\Rightarrow \infty}f(\boldsymbol{x})=+\infty$ )，那么 $f$ 在 $S$ 上一定有全局最小值。

　　以上定理只能保证最小值存在，没有建立最小值和极小值之间的关系。但是，对于一类特殊的函数，它在一定区域内的极小值一定是最小值，这类函数即凸函数。凸函数为定义在凸区间上的一种函数，它满足任意两点的连线位于抽象的函数曲面之下；而凸区间则满足任意两点连线仍然在区间中。定义在凸区间内的严格凸函数有唯一的极小值，该极小值为该函数在该区间上的最小值。

2.2 最优化条件：

　　一阶最优化条件：一维函数 $f:\mathbb{R}\Rightarrow \mathbb{R}$ 的一阶极值条件：$f'(x)=0$ ；高维函数 $f:\mathbb{R}^n\Rightarrow \mathbb{R}$ 的一阶极值条件：$ abla f(\boldsymbol{x})=0$ 。

　　二阶最优化条件：一维函数 $f:\mathbb{R}\Rightarrow \mathbb{R}$ 的一阶极值条件：$f''(x)>0$ ；高维函数 $f:\mathbb{R}^n\Rightarrow \mathbb{R}$ 的二阶极值条件：$H_f(\boldsymbol{x})$ 正定。其中，$(H_f(\boldsymbol{x}))_{ij}=\frac{\partial^2 f(\boldsymbol{x})}{\partial x_i \partial x_j}$ 称为海塞(Hessian)矩阵，它是高维函数泰勒展开的二次项系数，等价于一维函数泰勒展开的二次项系数（二阶导数）。当一阶最优化条件满足时，海塞矩阵正定$\Rightarrow$该点为极小值点；海塞矩阵负定$\Rightarrow$该点为极大值点；海塞矩阵不定$\Rightarrow$该点为鞍点；海塞矩阵为奇异矩阵$\Rightarrow$无法判断点的类型，此时理论上来说需要有更高阶最优化条件。

2.3 问题的条件：

　　考虑一维函数的泰勒级数展开：$f(\hat{x})\approx f(x^*)+f'(x^*)h+f''(x^*)h^2/2$ 。在极值附近，$f'(x^*)=0$， 以函数值距离最小值的差距为向后误差，$|f(x)-f(x^*)|\leq \epsilon$，则有 $h\leq \sqrt{2\epsilon/|f''(x^*)|}$ ，精度比较求解非线性方程是减半的（2n位有效数字$\Rightarrow$n位有效数字）。但是，有许多的数值解法等效于求解一阶最优化条件，此时不应当将函数值距离最小值的差作为向后误差，而应当将一阶导数的绝对值作为向后误差。

3. 数值方法

和数值求解方程的问题类似，数值优化的方法也多为迭代方法。

3.1 一维优化问题

　　一维优化问题的数值方法包括：黄金分割搜索法（区间分割），牛顿法（一阶最优化求解），连续二次插值法，等。

3.2 高维优化问题

　　高维优化问题的数值方法包括：Nelder-Mead单纯形方法（直接搜索），最速下降法，信赖域方法，高维牛顿法（一阶最优化求解），拟牛顿法（割线更新迭代）—— BFGS方法、共轭梯度法，等。