预、概念陈述

一、最优化问题

最优化问题数学模型的一般形式：

$$ \min f(\boldsymbol x) \ \ {\rm s.t.} \ \begin{cases}

c_m(\boldsymbol x) = 0, & m=1, 2, \cdots, P \\ c_m(\boldsymbol x) \ge 0, & m=P+1, P+2, \cdots, M

\end{cases}

$$
- 其中，决策变量 $\boldsymbol x \in \R^N$；目标函数 $f: \R^N \to \R$； ${\rm s.t.}$ 表示 subject to（受约束）。
将其余形式转换为一般形式：
- 求目标函数极大可以转成极小，作 $\overline f(\boldsymbol x) = -f(\boldsymbol x)$；
- 等式或不等式移项构造 $\overline c_m(\boldsymbol x)$。

按照约束类型分类：
- 等式约束最优化问题：只有等式约束。
- 不等式约束最优化问题：只有不等式约束。
- 盒式约束优化问题：约束条件为 $l_n \le x_n \le r_n, \ n = 1, 2, \cdots, N$。
- 无约束最优化问题：约束条件为 $\boldsymbol x \in \R^N$。
连续最优化 vs. 离散最优化（如组合最优化，如整数规划、邮路问题）。
- 本书只介绍连续、光滑的最优化问题。
  - 光滑：目标函数和约束函数均在其定义域内无穷阶数连续可导。

满足所有约束条件的决策变量 $\boldsymbol x$ 被称为可行点 (feasible point)，其全体构成可行域 (feasible region)，称为 ${\mathcal F}$。
对于任何单条不等式约束 $c_m(\boldsymbol x) \ge 0$：
- 如果 $c_m(\boldsymbol x) = 0$，称点 $\boldsymbol x$ 为此约束的边界点，此约束为活跃约束 (active constraint)；
- 如果 $c_m(\boldsymbol x) > 0$，称点 $\boldsymbol x$ 为此约束的内点，此约束为非活跃约束 (inactive constraint)。
对于可行点 $\boldsymbol x$ ，如果其为是所有不等式约束的内点，即为可行域的内点；否则为可行域的边界点。
- 如下图中 $\boldsymbol x^1$，$\boldsymbol x^2$ 是可行域的边界点；$\boldsymbol x^1$ 是两条约束的边界点。

对于 $\boldsymbol x^* \in {\mathcal F}$ 如果满足 $\forall \boldsymbol x \in {\mathcal F}, \ f(\boldsymbol x^) \le f(\boldsymbol x)$，那么 $\boldsymbol x^$ 为全局最优解。
- 如果 $\forall \boldsymbol x \in {\mathcal F}, x \neq x^* , \ f(\boldsymbol x^) < f(\boldsymbol x)$，那么 $\boldsymbol x^$ 为严格的全局最优解。
类似地，如果存在邻域（一般是二范数邻域）在之中最小，那么为局部最优解。