最优化|凸集

Posted by Derek on January 19, 2021

1. 凸集的定义


凸集在最优化中有非常好的性质,因此我们首先复习凸集的定义.

定义 1.1(凸集,Convex set)    对于任意的$\mathbf{x}, \mathbf{y} \in C$与任意的$\lambda \in [0, 1]$有$$\lambda \mathbf{x}+(1-\lambda)\mathbf{y} \in C$$

在平面图形中,我们可以快速地判断一个集合是否是凸集. 比如圆形$\lbrace (x, y)|x^2+y^2=1 \rbrace$是一个凸集,因为圆内任意两点的连线仍在圆内.

根据这个定义,我们还可以推出凸集的一个等价充要条件:对于任意的$\mathbf{x}_1, \cdots, \mathbf{x}_k \in C$与任意的$\lambda_1, \cdots, \lambda_k \geq 0$($\lambda_1+\cdots+\lambda_k=1$)有$$\lambda_1\mathbf{x}_1+\cdots+\lambda_k\mathbf{x}_k \in C$$

根据这个表达式,我们可以提出一个凸组合与凸包的定义.

定义 1.2(凸组合,Convex combination of $\mathbf{x}_1, \cdots, \mathbf{x}_k$)    $\lambda_1\mathbf{x}_1+\cdots+\lambda_k\mathbf{x}_k$称为$\mathbf{x}_1, \cdots, \mathbf{x}_k$的凸组合,其中$\lambda_1, \cdots, \lambda_k \geq 0, \displaystyle\sum_{i=1}^k\lambda_i=1.$

定义 1.3(凸包,Convex hull of set $C$)    由任意一个集合$C$中点的凸组合构成.

凸包在最优化中的作用也是非常大的,比如说如果我们能够找到线性整数规划可行集的凸包,那么我们就能很求解对应的线性规划问题.

2. 常见的凸集


常见的凸集有:

    1. 超平面(Hyperplane):$$H=\lbrace \mathbf{x}|\mathbf{a}^T\mathbf{x}=b \rbrace, \mathbf{a} \neq \mathbf{0}$$     2. 半空间(Halfspace):$$H^+=\lbrace \mathbf{x}|\mathbf{a}^T\mathbf{x} \geq b \rbrace, \mathbf{a} \neq \mathbf{0}$$或$$H^-=\lbrace \mathbf{x}|\mathbf{a}^T\mathbf{x} \leq b \rbrace, \mathbf{a} \neq \mathbf{0}$$     3. 多面体(Polyhedra):多个线性不等式所刻画的集合$$\lbrace \mathbf{x}|\mathbf{a}_i^T\mathbf{x} \leq b_i, i=1, \cdots, m \rbrace$$     4. 球(Ball):$$B(\mathbf{x}_c, r)=\lbrace \mathbf{x}| \|\mathbf{x}-\mathbf{x}_c\|_2 \leq r \rbrace=\lbrace \mathbf{x}_c+r\mathbf{u}| \|\mathbf{u}\|_2 \leq 1 \rbrace$$     5. 椭球(Ellipsoid):$$\lbrace \mathbf{x}|(\mathbf{x}-\mathbf{x}_c)^TP^{-1}(\mathbf{x}-\mathbf{x}_c) \leq 1 \rbrace$$其中$P$为正定矩阵.

    6. 二阶锥(Second-order cone):$$\lbrace (\mathbf{x}, t)|\|\mathbf{x}\|_2 \leq t \rbrace$$

3. 凸集的性质


性质 3.1    设$C_1, C_2 \subset \mathbb{R}^n$是凸集. 则$$C_1 \cap C_n=\lbrace \mathbf{x}|\mathbf{x} \in C_1, \mathbf{x} \in C_2 \rbrace$$和$$C_1 \pm C_2=\lbrace \mathbf{x} \pm \mathbf{y}|\mathbf{x} \in C_1, \mathbf{y} \in C_2 \rbrace$$是凸集.

性质 3.2    设$f: \mathbb{R}^n \to \mathbb{R}^m$是仿射函数,即$f(\mathbf{x})=A\mathbf{x}+\mathbf{b}, A \in \mathbb{R}^{m \times n}, \mathbf{b} \in \mathbb{R}^m.$ 若$C$为凸集,则$$f(C)=\lbrace f(\mathbf{x})|\mathbf{x} \in C \rbrace$$和$$f^{-1}(C)=\lbrace \mathbf{x}|f(\mathbf{x}) \in C \rbrace$$是凸集.

在这里我们补充几个特殊的仿射变换:

  1. 放缩:$$\alpha C=\lbrace \alpha\mathbf{x}|\mathbf{x} \in C \rbrace, \alpha \in \mathbb{R}$$
  2. 平移:$$\mathbf{x}_0+C=\lbrace\mathbf{x}_0+\mathbf{x}|\mathbf{x} \in C\rbrace$$

定理 3.3(投影定理)    设$C \subset \mathbb{R}^n$是非空闭凸集,$\mathbf{y} \in \mathbb{R}^n, \mathbf{y} \notin C,$ 则存在唯一的一点$\overline{\mathbf{x}} \in C$使$\overline{\mathbf{x}}$是$\mathbf{y}$到$C$的距离最小的点,即$$\|\overline{\mathbf{x}}-\mathbf{y}\|=\inf\lbrace\|\mathbf{x}-\mathbf{y}\||\mathbf{x} \in C \rbrace>0$$$\overline{\mathbf{x}}$是$\mathbf{y}$到$C$的最小距离点(投影点)的充要条件是$$(\mathbf{y}-\overline{\mathbf{x}})^T(\mathbf{x}-\overline{\mathbf{x}}) \leq 0, \forall \mathbf{x} \in C$$

接下来我们探讨一下凸集的分离.

定义 3.4(分离)    设$C_1, C_2$是两个非空凸集,若存在非零$\alpha \in \mathbb{R}^n$和$b \in \mathbb{R}$使得$$\alpha^T\mathbf{x} \geq b, \forall \mathbf{x} \in C_1, \alpha^T\mathbf{z} \leq b, \forall \mathbf{z} \in C_2$$或$$\alpha^T\mathbf{z} \leq \alpha^T\mathbf{x}, \forall \mathbf{x} \in C_1, \mathbf{z} \in C_2$$则称超平面$H=\lbrace \mathbf{x}|\alpha^T\mathbf{x}=b \rbrace$分离集合$C_1$与$C_2.$ 严格分离的定义也是类似的.

定理 3.5(凸集分离定理)    设$C \subset \mathbb{R}^n$是非空闭凸集,$\mathbf{y}\in\mathbb{R}^n, \mathbf{y}\notin C,$ 则存在超平面将$\mathbf{y}$和$C$(严格)分离.

定理 3.6(支撑超平面定理)    设$C \subset \mathbb{R}^n$是非空凸集,$\overline{\mathbf{x}} \in \partial C,$ 则存在非零向量$\alpha \in \mathbb{R}^n$使得$$\alpha^T\mathbf{x} \leq \alpha^T\overline{\mathbf{x}}, \forall \mathbf{x} \in \overline{C}$$此时也称超平面$H=\lbrace \mathbf{x} \in \mathbb{R}^n|\alpha^T\mathbf{x}=\alpha^T\overline{\mathbf{x}} \rbrace$是集合$C$在$\overline{\mathbf{x}}$处的支撑超平面.

证明    在证明之前,我们先明确几个在多元微积分中的符号(不同的教材可能会有不同的符号表示). 我们用$\partial C$表示$C$的边界,$S^\circ$表示$S$所有的内点组成的集合,$\overline{C}$表示$C$的闭包.

由于$\overline{\mathbf{x}} \in \partial C,$ 则存在$\lbrace \mathbf{x}_k \rbrace \not\subseteq \overline{C}$使得$\mathbf{x}_k \to \overline{\mathbf{x}}.$ 令$\mathbf{z}_k^*$为$\mathbf{x}_k$在$C$上的投影点,且$$\alpha_k=\frac{\mathbf{x}_k-\mathbf{z}_k^*}{\|\mathbf{x}_k-\mathbf{z}_k^*\|_2}$$不难发现,$\lbrace \alpha_k \rbrace$也有极限点,不妨设$\alpha_k \to \alpha.$ 根据投影定理,我们有$$(\mathbf{x}_k-\mathbf{z}_k^*)^T(\mathbf{x}-\mathbf{z}_k^*) \leq 0, \forall \mathbf{x} \in \overline{C}$$也即$$\alpha_k^T\mathbf{x} \leq \alpha_k^T\mathbf{z}_k^*, \forall \mathbf{x} \in \overline{C}$$因为$$\alpha_k^T\mathbf{z}_k^*=\alpha_k^T(\mathbf{z}_k^*-\mathbf{x}_k)+\alpha_k^T\mathbf{x}_k<\alpha_k^T\mathbf{x}_k$$所以$$\alpha_k^T\mathbf{x}<\alpha_k^T\mathbf{x}_k, \forall \mathbf{x} \in \overline{C}$$令$k \to \infty,$ 我们有$$\alpha^T\mathbf{x} \leq \alpha^T\overline{\mathbf{x}}, \forall \mathbf{x} \in \overline{C}$$

4. Farkas引理


Farkas引理是凸优化中经典和常用的引理.

引理 4.1(Farkas引理)    给定矩阵$A_{m \times n}$与$n$维向量$\mathbf{c},$ 则以下两个问题有且只有一个有解:(1)存在$\mathbf{x} \in \mathbb{R}^n$使得$A\mathbf{x} \leq \mathbf{0}, \mathbf{c}^T\mathbf{x}>0$;(2)存在$\mathbf{y} \in \mathbb{R}^m$使得$A^T\mathbf{y}=\mathbf{c}, \mathbf{y} \geq \mathbf{0}.$

我们从线性代数的角度进一步理解这一引理. 令$$A_{m \times n}=\begin{pmatrix}\mathbf{a}_1^T \\ \vdots \\ \mathbf{a}_m^T\end{pmatrix}, \mathbf{a}_i \in \mathbb{R}^n$$ 那么第一个问题等价于$\mathbf{a}_i^T\mathbf{x}<0, i=1, \cdots, m, \mathbf{c}^T\mathbf{x}>0$; 第二个问题等价于$y_1\mathbf{a}_1+\cdots+y_m\mathbf{a}_m=\mathbf{c}, y_i\geq0.$ 从而我们可以从几何上解释这一引理——$A$的行向量与$\mathbf{c}$的位置关系.

我们可以利用线性规划中的对偶理论来证明Farkas引理.

推论 1(Gordan定理)    给定矩阵$A_{m \times n},$ 则以下两个问题有且只有一个有解:(1)存在$\mathbf{x} \in \mathbb{R}^n$使得$A\mathbf{x}<\mathbf{0}$; (2)存在$\mathbf{y} \in \mathbb{R}^m$使得$A^T\mathbf{y}=\mathbf{0}, \mathbf{y}>\mathbf{0}.$