这一章我们介绍凸优化的基本概念和极大极小理论，并探讨最优解的存在性问题。

　　考虑如下形式的优化问题\begin{align*} \min_{\boldsymbol{x}} & \ f(\boldsymbol{x}) \\ \mbox{s.t.} & \ \boldsymbol{x} \in X. \end{align*}其中函数$f: \mathbb{R}^n \mapsto (-\infty, \infty]$，$X$是$\mathbb{R}^n$的非空子集。若向量$\boldsymbol{x} \in X \cap dom(f)$，则称$\boldsymbol{x}$为可行解(feasible point)。若$X \cap dom(f) \neq \emptyset$，则称问题是可解的(feasible)，否则称问题不可解(infeasible)。因此，若$f$是扩展实值函数，那么$\boldsymbol{x} \in dom(f)$是一条隐式的约束。此外，问题可解等价于$\inf_{\boldsymbol{x} \in X} f(\boldsymbol{x}) < \infty$。

　　若向量$\boldsymbol{x}^* \in X \cap dom(f)$且$f(\boldsymbol{x}^*) = \inf_{\boldsymbol{x} \in X} f(\boldsymbol{x})$，则称$\boldsymbol{x}^*$为$f$在$X$上的全局最小值点(global minimum)，或$f$在$\boldsymbol{x}^*$处取得最小值：\begin{align*} \boldsymbol{x}^* \in \arg \min_{\boldsymbol{x} \in X} f(\boldsymbol{x}). \end{align*}若$\boldsymbol{x}^*$还是$X$上唯一的最小值点，则\begin{align*} \boldsymbol{x}^* = \arg \min_{\boldsymbol{x} \in X} f(\boldsymbol{x}). \end{align*}对于最大值问题，我们也有相对应的术语，这里就不赘述了。

　　在优化问题中，我们经常会碰到全局最小的一个弱化形式，即在某点的一个“邻近”范围里，该点是最小的，这时称该点为局部最小值点(local minimum)。其严格定义如下：设函数$f: \mathbb{R}^n \mapsto (-\infty, \infty]$，$X$是$\mathbb{R}^n$的非空子集，若存在$\epsilon > 0$使得对于$\forall \boldsymbol{x} \in X$有\begin{align*} f(\boldsymbol{x}^*) \leq f(\boldsymbol{x}), \ \|\boldsymbol{x} - \boldsymbol{x}^*\| < \epsilon, \end{align*}则称$\boldsymbol{x}^*$为$f$在$X$上的局部最小值点。若以$\boldsymbol{x}^*$为球心的某个开球内没有其他局部最小值点，则称$\boldsymbol{x}^*$为严格局部最小值点。局部最大值点可类似定义。

　　实际应用中，我们感兴趣的只是全局最小值点，局部最小值点我们并不需要。但获取全局最小值点是很困难的，因为很多时候，算法无法甄别这两者，幸运的是，若$f$和$X$都是凸的，则$f$在$X$上的所有局部最小值点都是全局最小值点。

　　命题3.1.1：若$f: \mathbb{R}^n \mapsto (-\infty, \infty]$是凸函数，$X$是$\mathbb{R}^n$的非空凸子集，则$f$在$X$上的所有局部最小值点都是全局最小值点。

　　证明：用反证法，设$\boldsymbol{x}^*$是$f$在$X$上的局部最小值点，但不是全局最小值点。那么存在向量$\boldsymbol{x} \in X$满足$f(\boldsymbol{x}) < f(\boldsymbol{x}^*)$，于是由$f$的凸性知对于\(\forall \alpha \in (0, 1)\)有\begin{align*} f(\alpha \boldsymbol{x}^* + (1-\alpha) \boldsymbol{x}) \leq \alpha f(\boldsymbol{x}^*) + (1-\alpha) f(\boldsymbol{x}) < f(\boldsymbol{x}^*), \end{align*}也即$f$在以$\boldsymbol{x}^*$和$\boldsymbol{x}$为端点的线段上的取值都严格小于$f(\boldsymbol{x}^*)$，这与$\boldsymbol{x}^*$是局部最小值点矛盾。