最优化

贡献者： 欄、停敘

　　 优化（Optimization，或称最优化），主要研究模型与算法。优化问题有三个最重要的因素：目标函数、优化变量、优化约束。注意这里的最优化只是名义上的，指的是当前给定约束下和目标下的最优，而非无条件的最好。

　　 若 $\chi=\mathbb{R}^n$，则称优化问题为无约束问题，否则称为有约束问题。有约束问题的可行域一般记作 $\chi=\{x\in \mathbb{R}^n|c_i(x)\le 0,i=1,\dots,m;c_i(x)=0,i=m+1,\dots,m+l\}$。

　　 由于最小目标并不一定存在，但下确界一定存在，故一般将 $\min f(x)$ 修改为 $\inf f(x)$。

1. 分类

　　 根据约束 $c$ 和目标函数 $f$ 的性质分类：

• 若 $f,c$ 均为线性称为线性规划（LP）
• 若 $f,c$ 中有非线性即称为非线性规划
• 若 $f$ 为二次函数，$c$ 为线性称为二次规划（QP）

　　 目标建模方法：范数、正则化、最大似然、松弛等

2. 求解方法

　　 一般无约束优化问题的求解方法通常可以分为：

• 线搜索法：线搜索法采用 $x_{k+1}=x_k+\alpha_k d_k$ 的方式进行迭代，其中 $\alpha_k$ 是步长，$d_k$ 是方向。步长的选取方法差不多，根据方向的选取方法不同，分为：梯度下降法和牛顿法。
• 信赖域法：信赖域法采用二阶微分在邻域内用二阶函数代替。

　　 最小二乘问题因为非常常见，因而研究了与其相应的特殊的求解方法。可以将最小二乘问题分为小残量问题和大残量问题。小残量问题一般采用高斯-牛顿（GN）法或 LM 方法，其中：高斯-牛顿法是线搜索方法，LM 法是信赖域法。大残量问题用拟牛顿法来实现。