01-凸集与凸函数

预备知识

• 凸组合：空间 ${\mathbb{R}}^n$ 中两点 $\mathbf{x}$ 和$\mathbf{y}$ 之间的线段。可以表示为 $\{\alpha \mathbf{x}+(1-\alpha )\mathbf{y}:\alpha \in [0,1]\}$

• 超平面： $\{\mathbf{x}\in {\mathbb{R}}^n:{\mathbf{u}}^{\top }\mathbf{x}=v\}$ 。其中 $\mathbf{u}=[u_1,u_2\cdots ,u_n{]}^{\top }$

• 正半空间 $H_{+}=\left\{\mathbf{x}\in {\mathbb{R}}^n:{\mathbf{u}}^{\top }\mathbf{x}⩾v\right\}$

• 负半空间 $H_{-}=\left\{\mathbf{x}\in {\mathbb{R}}^n:{\mathbf{u}}^{\top }\mathbf{x}⩽v\right\}$

• 凸集： 集合中任意两个元素的凸组合仍在集合中。

• 保凸运算： 凸集的数乘，Minkowski和，交集，仿射变换（平移，旋转，放缩，透视）。

• 极点：不能表示为两个点连线段的内点。

• 极值原理：连续函数在紧集上一定能取到极值。

• 多面体：如果一个集合能被表示为有限个半空间的交集，那么该集合可以称为多面体。

• 多胞形： 非空有界的多面体

• 梯度向量：如果 $\mathbf{f}$: ${\mathbb{R}}^n\to \mathbb{R}$ 是可微的， $\nabla f(\mathbf{x})=\left[\begin{array}{c}\frac{\partial f}{\partial x_1}(\mathbf{x})\\ ⋮\\ \frac{\partial f}{\partial x_n}(\mathbf{x})\end{array}\right]=Df(\mathbf{x}{)}^{\top }$

• 雅可比矩阵：向量值函数 $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$, 即

$$\mathbf{f}(\mathbf{x})=\left[\begin{array}{c}{f}_1(\mathbf{x})\\ ⋮\\ f_m(\mathbf{x})\end{array}\right]$$

其导数 (雅克比) 矩阵为

$$\left[\frac{\partial \mathbf{f}}{\partial x_1}\left({\mathbf{x}}_0\right)\cdots \frac{\partial \mathbf{f}}{\partial x_n}\left({\mathbf{x}}_0\right)\right]=\left[\begin{array}{ccc}\frac{\partial f_1}{\partial x_1}\left({\mathbf{x}}_0\right)& \cdots & \frac{\partial f_1}{\partial x_n}\left({\mathbf{x}}_0\right)\\ ⋮& & ⋮\\ \frac{\partial f_m}{\partial x_1}\left({\mathbf{x}}_0\right)& \cdots & \frac{\partial f_m}{\partial x_n}\left({\mathbf{x}}_0\right)\end{array}\right]$$

• 黑塞矩阵：给定函数 $f:{\mathbb{R}}^n\to \mathbb{R}$, 如果梯度 $\nabla f$ 可微, 则称 $f$ 是二次可微的, $\nabla f$ 的导数记为

$$D^{2}f=\left[\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_2\partial x_1}& \cdots & \frac{{\partial }^{2}f}{\partial x_n\partial x_1}\\ \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \frac{{\partial }^{2}f}{\partial x_2^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n\partial x_2}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_1\partial x_n}& \frac{{\partial }^{2}f}{\partial x_2\partial x_n}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right]$$

• 中值定理： 如果函数 $\mathbf{f}:{\mathbb{R}}^n\to {\mathbb{R}}^m$ 在开集 $\Omega \subset {\mathbb{R}}^n$ 上可微, 那么对于任意两点 $\mathbf{x},\mathbf{y}\in \mathbf{\Omega }$, 存在矩阵 $\mathbf{M}$, 使得 $\mathbf{f}(\mathbf{x})-\mathbf{f}(\mathbf{y})=\mathbf{M}(\mathbf{x}-\mathbf{y})$
• 多元实值向量值函数的Taylor展开：如果函数 $\mathbf{f}\in {\mathcal{C}}^3$

$$f(\mathbf{x})=f\left({\mathbf{x}}_0\right)+\frac{1}{1!}Df\left({\mathbf{x}}_0\right)\left(\mathbf{x}-{\mathbf{x}}_0\right)+\frac{1}{2!}{\left(\mathbf{x}-{\mathbf{x}}_0\right)}^{\top }{D}^{2}f\left({\mathbf{x}}_0\right)\left(\mathbf{x}-{\mathbf{x}}_0\right)+O\left({\Vert \mathbf{x}-{\mathbf{x}}_0\Vert }^3\right)$$

集合优化问题：

$$\begin{array}{c}minimizef(\mathbf{x})\\ subjectto\mathbf{x}\in \Omega \end{array}$$

其中, 函数 $f:{\mathbb{R}}^n\to \mathbb{R}$ 称为目标函数或价值函数, 是一个实值函数。该优化问题的含义是 寻找合适的 $\mathbf{x}$, 使得函数 $f$ 达到最小。 $\mathbf{x}$ 是一个 $n$ 维向量, 表示为 $\mathbf{x}={\left[x_1,x_2,\cdots ,x_n\right]}^{\top }\in$ ${\mathbb{R}}^n,x_1,x_2,\cdots ,x_n$ 相互独立，通常称为决策变量。集合 $\Omega$ 是 $n$ 维实数空间 ${\mathbb{R}}^n$ 的一个子 集, 称为约束集或可行集。约束集可以表示为$\Omega =\left\{x:h(x)=0,g(x)\le 0\right\}$ 其中 $h$ 和 $g$ 表示由函数组成的向量，这种形式的约束称为函数约束。

---

• 定义(极小点)：存在一个 $n$ 元实值函数 $f:{\mathbb{R}}^n\to \mathbb{R}$, 定义域为 $\Omega \subset {\mathbb{R}}^n$ 。对于定义域 $\Omega$ 中的 一个点 ${\mathbf{x}}^{\ast }$, 如果存在 $\epsilon >0$, 对于所有满足 $\Vert \mathbf{x}-{\mathbf{x}}^{\ast }\Vert <\epsilon ,\mathbf{x}\in \Omega \backslash \left\{{\mathbf{x}}^{\ast }\right\}$ 的向量 $\mathbf{x}$, 不等式 $f(\mathbf{x})⩾f\left({\mathbf{x}}^{\ast }\right)$ 都成立，则称 ${\mathbf{x}}^{\ast }$ 是函数 $f$ 在定义域 $\Omega$ 中的一个局部极小点。如果对千所 有 $\mathbf{x}\in \Omega \backslash \left\{{\mathbf{x}}^{\ast }\right\}$, 不等式 $f(\mathbf{x})⩾f\left({\mathbf{x}}^{\ast }\right)$ 都成立, 则称 ${\mathbf{x}}^{\ast }$ 是函数 $f$ 在定义域 $\Omega$ 中的一个全局极小点。

• 定义(可行方向)：对于向量 $\mathbf{d}\in {\mathbb{R}}^n,\mathbf{d}\ne 0$ 和约束集中的某个点 $\mathbf{x}\in \Omega$, 如果存在一个实数 ${\alpha }_0>0$, 使得对于所有 $\alpha \in \left[0,{\alpha }_0\right],\mathbf{x}+\alpha \mathbf{d}$ 仍然在约束集内, 即 $\mathbf{x}+\alpha \mathbf{d}\in \Omega$, 则称 $\mathbf{d}$ 为 $\mathbf{x}$ 处的可行方向。

• 定义(一阶必要条件)：多元实值函数 $f$ 在约束集 $\Omega$ 上一阶连续可微, 即 $f\in {\mathcal{C}}^1$, 约束集 $\Omega$ 是 ${\mathbb{R}}^n$ 的子集。如果 ${\mathbf{x}}^{\ast }$ 是函数 $f$ 在 $\Omega$ 上的局部极小点, 则对于 ${\mathbf{x}}^{\ast }$ 处的任意可行 方向 $\mathbf{d}$, 都有

$${\mathbf{d}}^{\top }\nabla f\left({\mathbf{x}}^{\ast }\right)⩾0$$

成立。（方向导数非负）

• 推论 $6.1$： 局部极小点位于约束集内部时的一阶必要条件。多元实值函数 $f$ 在约束集 $\Omega$ 上一阶连续可微, 即 $f\in {\mathcal{C}}^1$, 约束集 $\Omega$ 是 ${\mathbb{R}}^n$ 的子集。如果 ${\mathbf{x}}^{\ast }$ 是函数 $f$ 在 $\Omega$ 上的局部极小 点, 且是 $\Omega$ 的内,点, 则有

$$\nabla f\left({\mathbf{x}}^{\ast }\right)=0$$

成立。

---

• 二阶必要条件：多元实值函数 $f$ 在约束集 $\Omega$ 上二阶连续可 微, 即 $f\in {\mathcal{C}}^e$, 约束集 $\Omega$ 是 ${\mathbb{R}}^n$ 的子集。如果 ${\mathbf{x}}^{\ast }$ 是函数 $f$ 在 $\Omega$ 上的局部极小点, $\mathbf{d}$ 是 ${\mathbf{x}}^{\ast }$ 处 的一个可行方向, 且 ${\mathbf{d}}^{\top }\nabla f\left({\mathbf{x}}^{\ast }\right)=0$, 则${\mathbf{d}}^{\top }\mathbf{F}\left({\mathbf{x}}^{\ast }\right)\mathbf{d}⩾0$ 其中, $\mathbf{F}$ 为函数 $\mathbf{f}$ 的黑塞矩阵（二阶导数非负）

• 如果 ${\mathbf{x}}^{\ast }$ 是函数 $f:\Omega \to \mathbb{R},f\in {\mathcal{C}}^2$ 在 $\Omega$ 上的局部极小点, 且是 $\Omega$ 的内点, 则有 $\nabla f\left({\mathbf{x}}^{\ast }\right)=0$ 黑塞矩阵 $\mathbf{F}\left({\mathbf{x}}^{\ast }\right)$ 半正定

• 二阶充分条件：多元实值函数 $f$ 在约束集上二阶连续可微, 即 $f\in {\mathcal{C}}^e,{\mathbf{x}}^{\ast }$ 是约束集的一个内点, 如果同时满足

1. $\nabla f\left({\mathbf{x}}^{\ast }\right)=0_{\text{。 }}$
2. $\mathbf{F}\left({\mathbf{x}}^{\ast }\right)>0$ 。 则 ${\mathbf{x}}^{\ast }$ 是函数 $f$ 的一个严格局部极小点。

凸函数的保凸运算

课本中提到了第一二个| 课程PPT

**(局部 $\Leftrightarrow$ 全局极小)** : $f: \Omega \rightarrow \mathbb{R}$ 是定义在凸集 $\Omega \subset \mathbb{R}^n$ 上的凸函数, $\Omega$ 中某一点是 $f$ 的全局极小点 $\Leftrightarrow$ 它是 $f$ 的局部极小点

(不等式约束问题) $f:\Omega \to \mathbb{R}$ 为定义在凸集 $\Omega \subset {\mathbb{R}}^n$ 上的凸函数, $f\in {\mathcal{C}}^1$, 且 $\Omega =\left\{\mathbf{x}\in {\mathbb{R}}^n:\mathbf{h}(\mathbf{x})=0,\mathbf{g}(\mathbf{x})⩽0\right\}$ 是凸集。 假设存在点 ${\mathbf{x}}^{\ast }\in \mathbf{\Omega },{\mathbf{\mu }}^{\ast }\in {\mathbb{R}}^p$ 和 ${\mathbf{\lambda }}^{\ast }\in {\mathbb{R}}^m$, 使得

1. ${\mathbf{\mu }}^{\ast }⩾0$;
2. $D\mathbf{f}\left({\mathbf{x}}^{\ast }\right)+{\lambda }^{\ast \top }D\mathbf{h}\left({\mathbf{x}}^{\ast }\right)+{\mathbf{\mu }}^{\ast \top }D\mathbf{g}\left({\mathbf{x}}^{\ast }\right)=0^{\top }$;
3. ${\mathbf{\mu }}^{\ast \top }\mathbf{g}\left({\mathbf{x}}^{\ast }\right)=0_{\text{。 }}$ 那么, $\mathbf{x}\ast$ 是 $f$ 在 $\Omega$ 上的全局极小点