无约束规划问题

本章节讨论无约束规划问题

$$\text{Find } \min_{\boldsymbol x \in \mathbb{R}^n} f(\boldsymbol x)$$

在数学分析中，我们已经学习过了极值问题，这里仅作回顾

• 全域最小解：指的是在定义域内的任意点处，函数值都不小于该点处的函数值
• 局部最小解：指的是在定义域内的某个邻域内的任意点处，函数值都不小于该点处的函数值

局部最小值的必要条件：令 $\boldsymbol x^*$ 是 $f:\mathbb R^n \to \mathbb R$ 的一个局部最小值解

• 若 $f$ 在 $\boldsymbol x^*$ 邻域可微，则 $\nabla f(\boldsymbol x^*) = \boldsymbol 0$
• 若 $f$ 在 $\boldsymbol x^*$ 邻域二阶可微，则 $\nabla^2 f(\boldsymbol x^*)$ 是半正定的（即 $\nabla^2 f(\boldsymbol x^*) \succeq 0$）

局部最小值的充分条件：

• 若 $f$ 在 $\boldsymbol x^*$ 邻域二阶可微，且 $\nabla f(\boldsymbol x^*) = \boldsymbol 0$，$\nabla^2 f(\boldsymbol x^*)$ 是正定的（即 $\nabla^2 f(\boldsymbol x^*) \succ 0$），则 $\boldsymbol x^*$ 是 $f$ 的一个局部最小值解

算法上，我们主要有三种考察

• 线搜索方法：先定方向 $\boldsymbol d$，再定步长 $\alpha$，最后更新 $\boldsymbol x \leftarrow \boldsymbol x + \alpha \boldsymbol d$
• 信赖域方法：先定一个区域 $D$，在该区域内寻找一个合适的 $\boldsymbol d$，最后更新 $\boldsymbol x \leftarrow \boldsymbol x + \boldsymbol d$
• 无导数方法：不使用导数信息，直接基于函数值进行搜索