下面我们将讨论凸性问题，这在优化理论中具有非常重要的地位。

凸集（Convex Sets）

  • 在定义凸集之前，我们首先给出凸组合的概念：设向量x⃗1,⋯ ,x⃗k\vec{x}_1,\cdots,\vec{x}_k，则称 x⃗=∑i=1kθix⃗i\vec{x}=\sum_{i=1}^k\theta_i\vec{x}_i 为x⃗1,⋯ ,x⃗k\vec{x}_1,\cdots,\vec{x}_k的凸组合，当θi≥0\theta_i\geq 0且∑i=1kθi=1\displaystyle\sum_{i=1}^k\theta_i=1。
    • 由此可知，θ1,⋯ ,θk\theta_1,\cdots,\theta_k既可以看作向量的权重，也可以看作概率分布。
  • 下面对凸集进行定义：设集合C⊆RnC\subseteq\R^n，若对于任意x⃗1,x⃗2∈C\vec{x}_1,\vec{x}_2\in C，θ∈[0,1]\theta\in[0,1]，凸组合θx⃗1+(1−θ)x⃗2∈C\theta\vec{x}_1+(1-\theta)\vec{x}_2\in C，那么称CC为凸集。
    • 从几何意义上说，上述定义等价于集合CC中任意两点x⃗1\vec{x}_1与x⃗2\vec{x}_2连线线段包含于CC中。
    • 从代数上推广，若CC为凸集，那么对于任意x⃗1,⋯ ,x⃗k∈C\vec{x}_1,\cdots,\vec{x}_k\in C，它们的凸组合都属于CC。

    当然，这里集合的元素不一定是向量，也可以是矩阵，随机变量等等。

  • 那么如何构造凸集呢？一个直接的方法是对任意集合取它的凸包（Convex Hull），其定义如下：设集合S⊆RnS\subseteq\R^n，那么它的凸包（记作conv(S)\text{conv}(S)）就是其所有点的凸组合，即 conv(S)={∑i=1kθix⃗i|k∈N,θ1,…,θk≥0,∑i=1kθi=1,x⃗1,…,x⃗k∈S}\text{conv}(S)=\left\{ \sum_{i=1}^k \theta_i \vec{x}_i \middle| k \in \mathbb{N}, \theta_1, \dots, \theta_k \geq 0, \sum_{i=1}^k \theta_i = 1, \vec{x}_1, \dots, \vec{x}_k \in S \right\} 其具有以下性质：
    1. conv(S)\text{conv}(S)是包含SS的最小凸集（当SS为凸集时二者相等）；
    2. conv(S)\text{conv}(S)是SS所有有限子集凸包的并集，即 conv(S)=⋃A⊆SA有限conv(A)\text{conv}(S)=\bigcup_{\substack{A\subseteq S\\[2pt]A\text{有限}}}\text{conv}(A) 这一性质还可以加强为下述Carathéodory定理（是的，和测度论的卡氏条件提出者是同一个人）： conv(S)=⋃A⊆S∣A∣≤n+1conv(A)\text{conv}(S)=\bigcup_{\substack{A\subseteq S\\[2pt]|A|\leq n+1}}\text{conv}(A) 其中∣A∣|A|表示集合AA中元素的数量。

      一个比较直观的推论：平面上任意集合凸包都可以用集合中三个点组成的三角形（不限个数）覆盖。

仿射集与相对内部

  • 除了凸包，还有其他从集合构造凸集的方法，比如：
    • 锥包（Conic Hull）：设S⊆RnS\subseteq\R^n，那么SS的锥包conic(S)\text{conic}(S)定义为 conic(S)={∑i=1kθix⃗i|k∈N,θ1,…,θk≥0,x⃗1,…,x⃗k∈S}\text{conic}(S)=\left\{ \sum_{i=1}^k \theta_i \vec{x}_i \middle| k \in \mathbb{N}, \theta_1, \dots, \theta_k \geq 0, \vec{x}_1, \dots, \vec{x}_k \in S \right\} 从几何上，SS的锥包相当于以原点为顶点，囊括整个SS凸包的锥体（二维上是扇形）。
  • 在介绍另一种构造方法之前，先给出仿射集（Affine Set）的概念：设集合S⊆RnS\subseteq\R^n，若对于任意x⃗1,x⃗2∈S,θ∈R\vec{x}_1,\vec{x}_2\in S,\theta\in\R，θx⃗1+(1−θ)x⃗2∈S\theta\vec{x}_1+(1-\theta)\vec{x}_2\in S，那么称SS为仿射集。

    • 几何意义上，上述定义等价于SS中任意两点x⃗1\vec{x}_1与x⃗2\vec{x}_2连成的整条直线包含于SS中。【由此显然可知仿射集一定是凸集】

    • 实际上，仿射集与线性子空间之间存在密切的关系。具体而言，定义A+x⃗={a⃗+x⃗∣a⃗∈A}A+\vec{x}=\{\vec{a}+\vec{x}|\vec{a}\in A\}为集合AA的一个平移，那么：

      • 对任意非空仿射集S⊆RnS\subseteq\R^n，存在Rn\R^n子空间UU使得对任意x⃗∈S\vec{x}\in S，有S=U+x⃗S=U+\vec{x}；
      • 对于任意Rn\R^n子空间UU和向量x⃗∈Rn\vec{x}\in\R^n，U+x⃗U+\vec{x}为一个仿射集。

      证明略（只需使用线性代数知识即可）。本质上，仿射集可以看作线性子空间的一个平移变换。

  • 由此我们可以定义仿射包（Affine Hull）：设集合S⊆RnS\subseteq\R^n，那么它的仿射包（记作aff(S)\text{aff}(S)）就是其所有点的仿射组合，即 aff(S)={∑i=1kθix⃗i|k∈N,θ1,…,θk∈R,∑i=1kθi=1,x⃗1,…,x⃗k∈S}\text{aff}(S)=\left\{ \sum_{i=1}^k \theta_i \vec{x}_i \middle| k \in \mathbb{N}, \theta_1, \dots, \theta_k \in\R, \sum_{i=1}^k \theta_i = 1, \vec{x}_1, \dots, \vec{x}_k \in S \right\} 由此可知仿射包一定是凸包。
    • 另外，与凸包类似，仿射包是包含SS的最小仿射集（当SS为仿射集时二者相等），且 aff(S)=⋃A⊆SA有限aff(A)\text{aff}(S)=\bigcup_{\substack{A\subseteq S\\[2pt]A\text{有限}}}\text{aff}(A) 同样，这一性质也可以进行加强：设aff(S)\text{aff}(S)为dd维线性子空间平移得到的仿射集，那么有 aff(S)=⋃A⊆S∣A∣≤daff(A)\text{aff}(S)=\bigcup_{\substack{A\subseteq S\\[2pt]|A|\leq d}}\text{aff}(A)

      注：这个加强版的性质只适用于非离散集合，对于离散集合∣A∣|A|上界为d+1d+1。

  • 下面我们将讨论凸集问题的另一个概念：相对内部（Relative interior）。在集合论中，我们已经涉及内部这一概念，这里再进行详述：
    • 首先，定义开球（open ball）：对于向量x⃗∈Rn\vec{x}\in\R^n，其半径rr的开球（r>0r>0）定义为 Nr(x⃗)≔{y⃗∈Rn∣∥y⃗−x⃗∥2<r}N_r(\vec{x})\coloneqq\{\vec{y}\in\R^n\mid\|\vec{y}-\vec{x}\|_2< r\}
    • 然后定义内部：设集合S⊆RnS\subseteq\R^n，对于x⃗∈Rn\vec{x}\in\R^n，若存在r>0r>0使得Nr(x⃗)⊆SN_r(\vec{x})\subseteq S，那么就称x⃗\vec{x}为SS的一个内点；称SS所有内点的集合为SS的内部，记作int(S)\text{int}(S)。
    • 在上述定义下，高维空间中低维集合的内部就是空集（比如平面上的线段集合），但我们希望同一集合在任意维度下“内部”都不变，因此考虑对内部这一概念进行推广：
      • 设集合S⊆RnS\subseteq\R^n，x⃗∈S\vec{x}\in S，如果存在r>0r>0使得Nr(x⃗)∩aff(S)⊆SN_r(\vec{x})\cap\text{aff}(S)\subseteq S，则称x⃗\vec{x}为SS的相对内点；【相当于将开球对SS所在低维空间做投影】
      • SS的所有相对内点的集合称作SS的相对内部，记作relint(S)\text{relint}(S)。
  • 有了相对内部的概念，我们就可以定义严格凸集（strictly convex sets）：设集合C⊆RnC\subseteq\R^n，若对于任意x⃗1,x⃗2∈C\vec{x}_1,\vec{x}_2\in C，θ∈(0,1)\theta\in(0,1)，有θx⃗1+(1−θ)x⃗2∈relint(C)\theta\vec{x}_1+(1-\theta)\vec{x}_2\in \text{relint}(C)，那么称CC为严格凸集。
    • 从几何上看，严格凸集的边界不允许出现低维内容（如平面中直线，三维空间中平面）。平面上的示意图如下：relint
      其中S1S_1为非凸集，S2S_2为非严格凸集，S3S_3为严格凸集。

超平面与半空间

  • 接下来我们考虑一种特殊的凸集：超平面（hyperplane）。其定义如下：设a⃗,x⃗0∈Rn,b∈R\vec{a},\vec{x}_0\in\R^n,b\in\R，则称集合 {x⃗∈Rn∣a⃗⊤x⃗=b}\{\vec{x}\in\R^n|\vec{a}^\top\vec{x}=b\} 或 {x⃗∈Rn∣a⃗⊤(x⃗−x⃗0)=0}\{\vec{x}\in\R^n|\vec{a}^\top(\vec{x}-\vec{x}_0)=0\} 为超平面。由此可知，超平面属于凸集。
  • 在得到超平面的定义后，我们就可以再定义半空间（half-space）：设a⃗,x⃗0∈Rn,b∈R\vec{a},\vec{x}_0\in\R^n,b\in\R，则称集合 {x⃗∈Rn∣a⃗⊤x⃗≥b}或{x⃗∈Rn∣a⃗⊤(x⃗−x⃗0)≥0}\{\vec{x}\in\R^n|\vec{a}^\top\vec{x}\geq b\}\quad\text{或}\quad\{\vec{x}\in\R^n|\vec{a}^\top(\vec{x}-\vec{x}_0)\geq 0\} 为正半空间，称 {x⃗∈Rn∣a⃗⊤x⃗≤b}或{x⃗∈Rn∣a⃗⊤(x⃗−x⃗0)≤0}\{\vec{x}\in\R^n|\vec{a}^\top\vec{x}\leq b\}\quad\text{或}\quad\{\vec{x}\in\R^n|\vec{a}^\top(\vec{x}-\vec{x}_0)\leq 0\} 为负半空间。
    • 从几何上看，以x⃗0\vec{x}_0为原点，则正半空间上的向量与a⃗\vec{a}的点积为正（与超平面垂直投影和a⃗\vec{a}同向），负半空间则刚好相反。
  • 下面我们阐述一个比较重要的定理：分离超平面定理（Separating Hyperplane Theorem）。设非空集合C,D⊆RnC,D\subseteq\R^n交集为空（C∩D=∅C\cap D=\varnothing），那么存在a⃗,x⃗0∈Rn\vec{a},\vec{x}_0\in\R^n使得 a⃗⊤(x⃗−x⃗0)≥0,∀x⃗∈Ca⃗⊤(x⃗−x⃗0)≤0,∀x⃗∈D\begin{aligned} \vec{a}^\top(\vec{x}-\vec{x}_0)\geq 0,\quad \forall\vec{x}\in C\\ \vec{a}^\top(\vec{x}-\vec{x}_0)\leq 0,\quad \forall\vec{x}\in D\\ \end{aligned} 特别地，当CC和DD均为闭集且其中至少一个集合有界，那么就存在a⃗,x⃗0∈Rn\vec{a},\vec{x}_0\in\R^n使得 a⃗⊤(x⃗−x⃗0)>0,∀x⃗∈Ca⃗⊤(x⃗−x⃗0)<0,∀x⃗∈D\begin{aligned} \vec{a}^\top(\vec{x}-\vec{x}_0)> 0,\quad \forall\vec{x}\in C\\ \vec{a}^\top(\vec{x}-\vec{x}_0)< 0,\quad \forall\vec{x}\in D\\ \end{aligned}

    注：当CC和DD均为无限闭集时，上述结论不一定成立，反例如下：n=2,C={(x,y)∣x≥0,y=0},D={(x,y)∣x>0,xy≥1}n=2,C=\{(x,y)|x\geq 0,y=0\},D=\{(x,y)|x>0,xy\geq 1\}，则不存在超平面（直线）可以完全分离CC和DD。【证明略】

    • 那么，这个超平面究竟如何构造呢？对于两个完全分离的集合CC和DD，可以定义它们之间的距离： dist(C,D)≔inf⁡c⃗∈Cd⃗∈D∥c⃗−d⃗∥2.\text{dist}(C,D)\coloneqq\inf_{\substack{\vec{c}\in C\\\vec{d}\in D}}\left\|\vec{c}-\vec{d}\right\|_2. 可知其一定大于00，且这个下确界一定能取到（一定存在向量c⃗0∈C\vec{c}_0\in C和d⃗0∈D\vec{d}_0\in D满足∥c⃗0−d⃗0∥2=dist(C,D)\left\|\vec{c}_0-\vec{d}_0\right\|_2=\text{dist}(C,D)）。
    • 于是我们就令超平面法向量a⃗=c⃗−d⃗\vec{a}=\vec{c}-\vec{d}，而其在超平面上的垂直投影x⃗0\vec{x}_0取向量重点，即x⃗0=c⃗+d⃗2\vec{x}_0=\dfrac{\vec{c}+\vec{d}}{2}。具体示意图如下：hyperplane
      证明这能够构成超平面可使用反证法，此处作略。

锥

  • 前面我们简要提到了锥包这一概念，下面我们对锥这一概念本身进行拓展。给出如下定义：

    1. 锥（cone）： 若集合KK中任意元素v⃗\vec{v}都满足αv⃗∈K\alpha\vec{v}\in K（α≥0\alpha\geq 0），则称KK为锥；【零向量一定属于锥】
    2. 凸锥（convex cone）：若KK既是凸集又是锥，则称KK为凸锥；
    3. 尖锥（pointed cone）：若锥KK不包含经过原点的直线（即对任意v⃗∈K\vec{v}\in K，存在α\alpha使αv⃗∉K\alpha\vec{v}\not\in K），则称KK为尖锥；
    4. 实心锥（solid cone）：若锥KK的内部非空（存在v⃗∈K\vec{v}\in K与r>0r>0使{w⃗∈Rn∣∥w⃗−v⃗∥2<r}⊆K\{\vec{w}\in\R^n\mid\|\vec{w}-\vec{v}\|_2< r\}\subseteq K），则称KK为实心锥；
    5. 闭锥（closed cone）：若锥KK为闭集（包含边界），则称KK为闭锥；
    6. 正常锥（proper cone）：若锥KK同时满足上述所有性质，则称KK为正常锥。

    正常锥的概念在后续凸优化中有着比较重要的作用，这里先按下不表。

    注：在后续凸优化问题中，我们可能需要对线性空间Rn\R^n上的理论推导到更广义的内积空间中，比如矩阵元素空间。具体细节在后续会进行讨论。

  • 下面我们再定义两种特殊的锥：

    1. 多面体锥（polyhedral cone）：称有下述形式 C≔{(x⃗,t)∈Rn+1∣Ax⃗≤ty⃗,t≥0}C\coloneqq\{(\vec{x},t)\in\R^{n+1}\mid A\vec{x}\leq t\vec{y},t\geq 0\} 的集合CC为多面体锥。其可以理解为以原点为顶点，包含Ax⃗≤y⃗A\vec{x}\leq\vec{y}（多面体）的锥体。
    2. 椭球锥（ellipsoidal cone）：称有下述形式 C≔{(x⃗,t)∈Rn+1∣∥Ax⃗−ty⃗∥2≤tz,t≥0}C\coloneqq\{(\vec{x},t)\in\R^{n+1}\mid \|A\vec{x}-t\vec{y}\|_2\leq tz,t\geq 0\} 的集合CC为多面体锥。其可以理解为以原点为顶点，包含∥Ax⃗−y⃗∥2≤z\|A\vec{x}-\vec{y}\|_2\leq z（椭球）的锥体。

      特别地，当AA为单位阵（对应圆球），y⃗=0⃗,z=1\vec{y}=\vec{0},z=1时，称CC为二阶锥（second order cone）。关于它的性质后续会进行讨论。

    由定义可知，多面体锥与椭球锥都是凸锥。

  • 然后，我们给出锥的一种重要关系：设K⊆RnK\subseteq\R^n为锥，那么下述集合

    K∗≔{y⃗∈Rn∣y⃗⊤x⃗≥0,∀x⃗∈K}K^*\coloneqq \{\vec{y}\in\R^n\mid\vec{y}^\top\vec{x}\geq 0,\forall\vec{x}\in K\}

    为一个闭凸锥。称K∗K^*为KK的对偶锥（dual cone）。

    • 从几何上看，对偶锥可以理解为对KK中所有向量过原点的正半空间取交集。
    • 下面列举一些常见锥的对偶锥：
      • R+n≔{x⃗=(x1,⋯ ,xn)∈Rn∣xi≥0,i=1,2,⋯ ,n}\R^n_+\coloneqq\{\vec{x}=(x_1,\cdots,x_n)\in\R^n|x_i\geq 0,i=1,2,\cdots,n\}的对偶锥是其自身；
      • 设线性子空间S⊆RnS\subseteq\R^n，则SS显然是凸锥，而SS的对偶锥就是SS的正交补空间S⊥S^{\perp}。

  • 在得到对偶锥的定义后，我们将讨论两种被广泛使用的正常锥：半正定矩阵锥与二阶锥。

    • 首先定义半正定矩阵锥：考虑n×nn\times n实对称矩阵空间Sn\mathbb{S}^n，使用Frobenius内积 ⟨A,B⟩F≔tr(AB)=∑i=1n∑j=1nAijBij,A,B∈Sn\langle A,B\rangle_F\coloneqq\text{tr}(AB)=\sum_{i=1}^n\sum_{j=1}^n A_{ij}B_{ij},\quad A,B\in\mathbb{S}^n 和Frobenius范数，那么实对称半正定矩阵空间S+n\mathbb{S}_+^n是Sn\mathbb{S}^n中的一个正常锥，且S+n\mathbb{S}_+^n在Sn\mathbb{S}^n中的对偶锥是其自身。

      实际上，实对称矩阵空间Sn\mathbb{S}^n可以看作n2n^2维向量空间Rn2\R^{n^2}的子空间，从而向量空间的锥理论可以迁移到这个矩阵空间中。

      证明

      首先证明S+n\mathbb{S}_+^n为满足正常锥的四条性质：

      1. 凸锥：设A,B∈S+n,α,β≥0A,B\in\mathbb{S}_+^n,\alpha,\beta\geq 0，那么对于任意v⃗∈Rn\vec{v}\in\R^n， v⃗⊤(αA+βB)v⃗=αv⃗⊤Av⃗⏟≥0+βv⃗⊤Bv⃗⏟≥0≥0\vec{v}^\top(\alpha A+\beta B)\vec{v}=\alpha\underbrace{\vec{v}^\top A\vec{v}}_{\geq 0}+\beta\underbrace{\vec{v}^\top B \vec{v}}_{\geq 0}\geq 0 因此αA+βB∈S+n\alpha A+\beta B\in\mathbb{S}_+^n。【β=0\beta=0成立⟹S+n\Longrightarrow\mathbb{S}_+^n是锥，β=1−α\beta=1-\alpha成立⟹S+n\Longrightarrow\mathbb{S}_+^n是凸集】
      2. 尖锥：对任意非零矩阵A∈S+nA\in\mathbb{S}_+^n，有−A∉S+n-A\not\in\mathbb{S}_+^n（v⃗⊤(−A)v⃗<0,∀v⃗∈Rn\vec{v}^\top(-A)\vec{v}< 0,\forall\vec{v}\in\R^n），因此S+n\mathbb{S}_+^n不包含过原点直线。
      3. 实心锥：因为I∈S+nI\in\mathbb{S}_+^n，考虑定义集合 B≔{A∈Sn|∥A−I∥F<12}\mathcal{B}\coloneqq\left\{A\in\mathbb{S}^n\middle|\|A-I\|_F< \frac{1}{2}\right\} 下证B⊆S+n\mathcal{B}\subseteq\mathbb{S}_+^n：对任意A∈BA\in\mathcal{B}，任意v⃗∈Rn\vec{v}\in\R^n， v⃗⊤Av⃗=v⃗⊤((A−I)+I)v⃗=v⃗⊤(A−I)v⃗+∥v⃗∥22≥−∥A−I∥2∥v⃗∥22+∥v⃗∥22≥−∥A−I∥F∥v⃗∥22+∥v⃗∥22>−12∥v⃗∥22+∥v⃗∥22=12∥v⃗∥22≥0.\begin{aligned} \vec{v}^\top A \vec{v} &= \vec{v}^\top ((A - I) + I) \vec{v} \\ &= \vec{v}^\top (A - I) \vec{v} + \|\vec{v}\|_2^2 \\ &\geq - \|A - I\|_2 \|\vec{v}\|_2^2 + \|\vec{v}\|_2^2 \\ &\geq - \|A - I\|_F \|\vec{v}\|_2^2 + \|\vec{v}\|_2^2 \\ &> -\frac{1}{2} \|\vec{v}\|_2^2 + \|\vec{v}\|_2^2 = \frac{1}{2} \|\vec{v}\|_2^2\geq 0. \end{aligned} 其中第二个不等号是因为对任意矩阵谱范数（矩阵最大奇异值）一定不大于Frobenius范数（矩阵所有奇异值平方和的平方根）。
        因此A∈S+n⟹B⊆S+nA\in\mathbb{S}_+^n\Longrightarrow\mathcal{B}\subseteq\mathbb{S}_+^n。
      4. 闭锥：设{Ak,k≥1}\{A_k,k\geq 1\}为S+n\mathbb{S}_+^n中一个收敛到A∈SnA\in\mathbb{S}^n的序列，那么对任意v⃗∈Rn\vec{v}\in\R^n， v⃗⊤Av⃗=v⃗⊤(lim⁡k→∞Ak)v⃗=lim⁡k→∞v⃗⊤Akv⃗⏟≥0≥0.\vec{v}^\top A \vec{v} = \vec{v}^\top \left( \lim_{k \to \infty} A_k \right) \vec{v} = \lim_{k \to \infty}\underbrace{\vec{v}^\top A_k \vec{v}}_{\geq 0} \geq 0. 因此A∈S+nA\in\mathbb{S}_+^n，即S+n\mathbb{S}_+^n为闭集。

      下面再证明S+n\mathbb{S}_+^n的对偶锥是其自身，即

      (S+n)∗={A∈Sn∣⟨A,B⟩F≥0,∀B∈S+n}=S+n.(\mathbb{S}_+^n)^*=\{A\in\mathbb{S}^n|\langle A,B\rangle_F\geq 0,\forall B\in\mathbb{S}_+^n\}=\mathbb{S}_+^n.
      1. 先证明(S+n)∗⊆S+n(\mathbb{S}_+^n)^*\subseteq\mathbb{S}_+^n：对任意A∈(S+n)∗A\in(\mathbb{S}_+^n)^*，任意v⃗∈Rn\vec{v}\in\R^n，因为v⃗v⃗⊤∈S+n\vec{v}\vec{v}^\top\in\mathbb{S}_+^n，所以 v⃗⊤Av⃗=tr(v⃗⊤Av⃗)=tr(Av⃗v⃗⊤)=⟨A,v⃗v⃗⊤⟩F≥0\vec{v}^\top A \vec{v}=\text{tr}(\vec{v}^\top A \vec{v})=\text{tr}(A\vec{v}\vec{v}^\top)=\langle A,\vec{v}\vec{v}^\top\rangle_F\geq 0 其中第二个等号利用了迹的循环不变性。由此得到A∈S+nA\in\mathbb{S}_+^n，即(S+n)∗⊆S+n(\mathbb{S}_+^n)^*\subseteq\mathbb{S}_+^n。
      2. 再证明(S+n)∗⊇S+n(\mathbb{S}_+^n)^*\supseteq\mathbb{S}_+^n：对任意B∈S+nB\in\mathbb{S}_+^n，考虑任意C∈S+nC\in\mathbb{S}_+^n，根据谱定理，CC可表示为∑i=1nλiv⃗iv⃗i⊤\displaystyle\sum_{i=1}^n\lambda_i\vec{v}_i\vec{v}_i^\top，其中λi≥0\lambda_i\geq 0。因此 ⟨B,C⟩F=tr⁡(BC)=tr⁡(B(∑i=1nλiv⃗iv⃗i⊤))=tr⁡(∑i=1nλiBv⃗iv⃗i⊤)=∑i=1nλitr⁡(Bv⃗iv⃗i⊤)=∑i=1nλi⏟≥0tr(v⃗i⊤Bv⃗i)⏟≥0≥0.\begin{aligned} \langle B, C \rangle_F &= \operatorname{tr}(BC) = \operatorname{tr}\left( B \left( \sum_{i=1}^n \lambda_i \vec{v}_i \vec{v}_i^\top \right) \right) \\ &= \operatorname{tr}\left( \sum_{i=1}^n \lambda_i B \vec{v}_i \vec{v}_i^\top \right) \\ &= \sum_{i=1}^n \lambda_i \operatorname{tr}\left( B \vec{v}_i \vec{v}_i^\top \right) \\ &= \sum_{i=1}^n \underbrace{\lambda_i}_{\ge 0} \underbrace{\text{tr}(\vec{v}_i^\top B \vec{v}_i)}_{\ge 0} \ge 0. \end{aligned} 于是B∈(S+n)∗B\in(\mathbb{S}_+^n)^*，即(S+n)∗⊇S+n(\mathbb{S}_+^n)^*\supseteq\mathbb{S}_+^n。

      综上，命题得证。

    • 然后给出二阶锥的正式定义：Rn+1\R^{n+1}中的二阶锥形式为 K≔{(x⃗,t)∈Rn×R∣∥x⃗∥≤t}K\coloneqq\{(\vec{x},t)\in\R^n\times \R\mid\|\vec{x}\|\leq t\} 其性质与半正定矩阵锥类似：属于正常锥，且在Rn+1\R^{n+1}中的对偶锥为其自身。【证明留给读者】

  • 关于对偶锥，还有如下定理：设K⊆RnK\subseteq\R^n为非空闭凸锥，那么有(K∗)∗=K(K^*)^*=K。【证明同样略】

凸函数（Convex Function）

在有了凸集的概念之后，我们就能对凸函数（以及凹函数）进行定义：

  • 设函数f:Rn→Rf:\R^n\to\R，若ff的定义域Ω\Omega为凸集，且对任意x⃗1,x⃗2∈Ω,θ∈[0,1]\vec{x}_1,\vec{x}_2\in\Omega,\theta\in[0,1]，有

    f(θx⃗1+(1−θ)x⃗2)≤θf(x⃗1)+(1−θ)f(x⃗2)f(\theta\vec{x}_1+(1-\theta)\vec{x}_2)\leq\theta f(\vec{x}_1)+(1-\theta)f(\vec{x}_2)

    则称ff为凸函数，而对应的−f-f则为凹函数（concave function）。

  • 事实上，上述定义也是Jensen不等式的一个特殊情形。Jensen不等式的完整形式如下：

    • 设Ω\Omega为凸集，f:Ω→Rf:\Omega\to\R为凸函数，那么对任意x⃗1,⋯ ,x⃗k∈Ω,θ1,⋯ ,θk∈[0,1],∑i=1kθi=1\vec{x}_1,\cdots,\vec{x}_k\in\Omega,\theta_1,\cdots,\theta_k\in[0,1],\displaystyle\sum_{i=1}^k\theta_i=1，有 f(∑i=1kθix⃗i)≤∑i=1kθif(x⃗i)f\left(\sum_{i=1}^k\theta_i\vec{x}_i\right)\leq\sum_{i=1}^k\theta_if(\vec{x}_i)
    • 凸（凹）函数的几何示意图如下：convex function
      直观上看，凸函数的形状类似碗状，且其中任意两点之间的连线段都在函数之上。【凹函数恰好相反】

  • 为了更好地将凸函数与凸集联系起来，我们引入epigraph这个概念【一般翻译为上境图】：设Ω\Omega为凸集，f:Ω→Rf:\Omega\to\R为凸函数，则ff的上境图（记作epi(f)⊆Ω×R\text{epi}(f)\subseteq\Omega\times\R）定义为

    epi(f)={(x⃗,t)∣x⃗∈Ω,t≥f(x⃗)}.\text{epi}(f)=\{(\vec{x},t)\mid \vec{x}\in\Omega,t\geq f(\vec{x})\}.

    从几何上看，上境图可以理解为Ω×R\Omega\times\R（即定义域-值域）空间中ff自身及其上方的点集区域。

    • ff为凸函数当且仅当上境图为凸集。

  • 下面我们讨论凸函数的导数（梯度）性质。首先是凸函数的一阶凸性性质：设Ω\Omega为凸集，f:Ω→Rf:\Omega\to\R为一阶可微函数，则ff为凸函数当且仅当对任意x⃗,y⃗∈Ω\vec{x},\vec{y}\in\Omega，

    f(y⃗)≥f(x⃗)+[∇f(x⃗)]⊤(y⃗−x⃗).f(\vec{y})\geq f(\vec{x})+[\nabla f(\vec{x})]^\top(\vec{y}-\vec{x}).

    实际上上式右边可以看作函数在x⃗\vec{x}处进行泰勒一阶近似后在y⃗\vec{y}处的值。因此从几何角度上看，凸函数位于其每个点切线的上方。

    • 简单证明如下（只证明必要性，充分性略）：对任意h∈(0,1)h\in(0,1)， f(hy⃗+(1−h)x⃗)≤hf(y⃗)+(1−h)f(x⃗)=f(x⃗)+h(f(y⃗)−f(x⃗))⟹f(hy⃗+(1−h)x⃗)−f(x⃗)h≤f(y⃗)−f(x⃗)⟹f(y⃗)≥f(x⃗)+f(hy⃗+(1−h)x⃗)−f(x⃗)h=f(x⃗)+f(x⃗+h(y⃗−x⃗))−f(x⃗)h.\begin{aligned} f(h\vec{y} + (1 - h)\vec{x}) &\leq hf(\vec{y}) + (1 - h)f(\vec{x}) \\ &= f(\vec{x}) + h(f(\vec{y}) - f(\vec{x})) \\ \Longrightarrow \frac{f(h\vec{y} + (1 - h)\vec{x}) - f(\vec{x})}{h} &\leq f(\vec{y}) - f(\vec{x}) \\ \Longrightarrow f(\vec{y}) &\geq f(\vec{x}) + \frac{f(h\vec{y} + (1 - h)\vec{x}) - f(\vec{x})}{h} \\ &= f(\vec{x}) + \frac{f(\vec{x} + h(\vec{y} - \vec{x})) - f(\vec{x})}{h}. \end{aligned} 两边让h→0h\to 0，得到 f(y⃗)≥lim⁡h→0{f(x⃗)+f(x⃗+h(y⃗−x⃗))−f(x⃗)h}=f(x⃗)+lim⁡h→0f(x⃗+h(y⃗−x⃗))−f(x⃗)h=f(x⃗)+[∇f(x⃗)]⊤(y⃗−x⃗)\begin{aligned} f(\vec{y}) &\geq \lim_{h \to 0} \left\{ f(\vec{x}) + \frac{f(\vec{x} + h(\vec{y} - \vec{x})) - f(\vec{x})}{h} \right\} \\ &= f(\vec{x}) + \lim_{h \to 0} \frac{f(\vec{x} + h(\vec{y} - \vec{x})) - f(\vec{x})}{h} \\ &= f(\vec{x}) + [\nabla f(\vec{x})]^\top (\vec{y} - \vec{x}) \end{aligned} 其中最后一个等号利用了梯度与方向导数的关系。

  • 相应地，凸函数也有二阶凸性性质：设Ω\Omega为凸集，f:Ω→Rf:\Omega\to\R为二阶可微函数，则ff为凸函数当且仅当对任意x⃗∈Ω\vec{x}\in\Omega，

    ∇2f(x⃗)⪰0\nabla^2f(\vec{x})\succeq 0

    即ff在x⃗\vec{x}处的Hessian矩阵为半正定矩阵。

    • 由此可得到一个推论：设Q∈Sn,b⃗∈Rn,c∈RQ\in\mathbb{S}^n,\vec{b}\in\R^n,c\in\R，则二次型函数 f(x⃗)=x⃗⊤Qx⃗+b⃗⊤x⃗+cf(\vec{x})=\vec{x}^\top Q\vec{x}+\vec{b}^\top\vec{x}+c 为凸函数当且仅当QQ为半正定矩阵。

  • 当我们将上述凸函数定义中的≤\leq改为<< （要求x⃗1≠x⃗2\vec{x}_1\neq\vec{x}_2），那么得到的ff（−f-f）就是严格凸（凹）函数（与严格单调定义类似）。

    • 严格凸函数也有对应的一阶/二阶严格凸性条件，这里作略。（但注意，二阶严格凸性条件只能由Hessian矩阵正定推出ff严格凸，反之不能推出）

  • 凸函数还可以在保持凸性的前提下进行变换：

    1. 逐点最大值：当f1,f2f_1,f_2均为凸函数，那么max⁡{f1,f2}\max\{f_1,f_2\}也为凸函数；
    2. 加权求和：当f1,⋯ ,fkf_1,\cdots,f_k均为凸函数，则α1f1+⋯+αkfk\alpha_1f_1+\cdots+\alpha_kf_k（α1,⋯ ,αk≥0\alpha_1,\cdots,\alpha_k\geq 0）也为凸函数；
    3. 线性变换：当f(x⃗)f(\vec{x})为Ω\Omega上凸函数，那么g(x⃗)=f(a⃗⊤x⃗+b⃗)g(\vec{x})=f(\vec{a}^\top\vec{x}+\vec{b})也为Ωg={a⃗⊤x⃗+b⃗∣x⃗∈Ω}\Omega_g=\{\vec{a}^\top\vec{x}+\vec{b}\mid \vec{x}\in\Omega\}上的凸函数；
    4. 复合函数：若hh为凸函数且单调不减，gg为凸函数，那么f=h∘gf=h\circ g为凸函数。

仿射函数（Affine Function）

那么有没有函数既是凸函数又是凹函数呢？当然有！这类函数我们称之为仿射函数，它们在后续会有重要作用。

  • 仿射函数主要有以下三种形式：

    1. f:Rn→R,a⃗∈Rn,b∈R⟹f(x⃗)=a⃗⊤x⃗+b,∀x⃗∈Rnf:\R^n\to\R,\vec{a}\in\R^n,b\in\R\Longrightarrow f(\vec{x})=\vec{a}^\top\vec{x}+b,\forall\vec{x}\in\R^n；
    2. f⃗:Rn→Rm,A∈Rm×n,b⃗∈Rm⟹f⃗(x⃗)=Ax⃗+b⃗,∀x⃗∈Rn\vec{f}:\R^n\to\R^m,A\in\R^{m\times n},\vec{b}\in\R^m\Longrightarrow \vec{f}(\vec{x})=A\vec{x}+\vec{b},\forall\vec{x}\in\R^n；
    3. f:Rm×n→R,A∈Rm×n,b∈R⟹f(X)=∑i=1m∑j=1nAijXij+b=tr(A⊤X)+b,∀X∈Rm×nf:\R^{m\times n}\to\R,A\in\R^{m\times n},b\in\R\Longrightarrow f(X)=\displaystyle\sum_{i=1}^m\sum_{j=1}^nA_{ij}X_{ij}+b=\text{tr}(A^\top X)+b,\forall X\in\R^{m\times n}。

    本质上，仿射函数可看作线性函数带上一个截距。

  • 关于仿射函数既是凸函数又是凹函数的证明此处作略，留给读者思考。【提示：对于第一种形式，构造g(x⃗)=f(x⃗)−f(0⃗)g(\vec{x})=f(\vec{x})-f(\vec{0})，证明g(rx⃗)=rg(x⃗),∀r∈Rg(r\vec{x})=rg(\vec{x}),\forall r\in\R，后两种类似】

凸优化问题

  • 在定义了凸集和凸函数后，我们终于可以对凸优化问题的形式进行正式定义：设Ω\Omega为一集合，f:Ω→Rf:\Omega\to\R为一函数，则如果Ω\Omega为凸集，ff为凸函数，则称 min⁡x⃗∈Ωf(x⃗)\min_{\vec{x}\in\Omega}f(\vec{x}) 为凸优化问题。【Ω\Omega也被称为可行域】
  • 当然，实际情况下x⃗∈Ω\vec{x}\in\Omega一般会用若干约束条件进行替代。具体而言，对于下述优化问题： min⁡x⃗∈Rnf0(x⃗)s.t.fi(x⃗)≤0,i=1,2,⋯ ,mhj(x⃗)=0,j=1,2,⋯ ,p\begin{aligned} &\min_{\vec{x}\in\R^n}f_0(\vec{x})\\ \text{s.t.}\quad &f_i(\vec{x})\leq 0,\quad i=1,2,\cdots,m\\ &h_j(\vec{x})=0,\quad j=1,2,\cdots,p \end{aligned} 当f0,f1,⋯ ,fmf_0,f_1,\cdots,f_m均为凸函数，h1,⋯ ,hph_1,\cdots,h_p均为仿射函数时，就称其为凸优化问题。【这也是凸优化问题的标准形式】
  • 然后我们给出凸优化问题的一阶凸性条件，这也是凸优化的一个重要定理：设Ω\Omega为凸集，f:Ω→Rf:\Omega\to\R为一阶可微函数。若x⃗∗∈Ω\vec{x}^*\in\Omega满足∇f(x⃗∗)=0⃗\nabla f(\vec{x}^*)=\vec{0}，那么x⃗∗∈arg min⁡x⃗∈Ωf(x⃗)\displaystyle\vec{x}^*\in\argmin_{\vec{x}\in\Omega}f(\vec{x})，即x⃗∗\vec{x}^*是ff在Ω\Omega上的一个全局最小值。
    • 实际上，对于凸函数而言，其局部最小值就是全局最小值。具体而言，若x⃗∗∈Ω\vec{x}^*\in\Omega满足存在ϵ>0\epsilon>0使得 f(x⃗∗)≤f(x⃗),∀x⃗∈Ω,∥x⃗−x⃗∗∥<ϵf(\vec{x}^*)\leq f(\vec{x}),\quad\forall\vec{x}\in\Omega,\|\vec{x}-\vec{x}^*\|< \epsilon 那么x⃗∗\vec{x}^*就是一个ff在Ω\Omega上全局最小值。
    • 那么这个全局最小值是否唯一呢？如果ff为严格凸函数，那么它就是唯一的。【当然，也可能根本不存在全局最小值，比如f(x)=exf(x)=e^x】

解决凸优化问题

在解决凸优化问题之前，我们先引入活跃约束与非活跃约束这两个概念：

  • 考虑上述凸优化问题标准形式中的不等式约束fi(x⃗)≤0f_i(\vec{x})\leq 0，如果在可行域中存在解x0⃗∈Rn\vec{x_0}\in\R^n，使得fi(x0⃗)=0f_i(\vec{x_0})=0，那么称对应的约束为活跃约束，否则称为非活跃约束。

    也可以从另一个角度理解：活跃约束对应的参数如果变化，那么对应的解就会发生变化，而非活跃约束则不会产生变化。

  • 实际上，活跃约束对应的解恰好就在可行域Ω\Omega的边界上。由此，我们就能归纳出解决凸优化问题的通用策略：
    1. 对于mm个不等式约束，考虑其是否为活跃约束，得到活跃约束指标集S⊆{1,2,⋯ ,m}S\subseteq\{1,2,\cdots,m\}【共2m2^m种组合】；
    2. 对于每个SS：
      • 求解修改后的问题 min⁡x⃗∈Rnf0(x⃗)s.t.fi(x⃗)≤0,i∈Shj(x⃗)=0,j=1,2,⋯ ,p\begin{aligned} &\min_{\vec{x}\in\R^n}f_0(\vec{x})\\ \text{s.t.}\quad &f_i(\vec{x})\leq 0,\quad i\in S\\ &h_j(\vec{x})=0,\quad j=1,2,\cdots,p \end{aligned} 即SS中的不等式约束都取等号，不考虑其他不等式约束，由此得到备选解x⃗S∗\vec{x}_S^*。
      • 如果存在某个解x⃗S∗\vec{x}_S^*是原始问题的可行解，则记录f0(x⃗S∗)f_0(\vec{x}_S^*)的值，否则忽略该解。
    3. 遍历所有满足原始问题可行性的x⃗S∗\vec{x}_S^*之后，选取f0(x⃗S∗)f_0(\vec{x}_S^*)最优的一个（或多个）解，作为原始问题的最优解。
  • 然而，上述策略的计算量是指数级的（每种SS都要进行计算），对于不等式约束较多的问题效率较低。之后我们会讨论如何对算法进行优化。

优化问题转换（重参数化）

  • 下面我们考虑优化问题的形式转换，通过重参数化构造优化问题的等价形式。在一些情况下，我们可以将非凸优化问题转化为凸优化问题。

目标函数单调变换

  • 首先给出一个基本结论：对优化目标函数施加单调变换，其得到的最优解与原始目标函数得到的解相同。具体而言，设Ω\Omega为任意集合，f0:Ω→Rf_0:\Omega\to\R为任意函数，定义值域f0(Ω)≔{f0(x⃗)∣x⃗∈Ω}⊆Rf_0(\Omega)\coloneqq\{f_0(\vec{x})\mid\vec{x}\in\Omega\}\subseteq\R，那么：

    • 对任意单调增函数ϕ:f0(Ω)→R\phi:f_0(\Omega)\to\R，有 arg min⁡x⃗∈Ωf0(x⃗)=arg min⁡x⃗∈Ωϕ(f0(x⃗))或arg max⁡x⃗∈Ωf0(x⃗)=arg max⁡x⃗∈Ωϕ(f0(x⃗))\argmin_{\vec{x}\in\Omega}f_0(\vec{x})=\argmin_{\vec{x}\in\Omega}\phi(f_0(\vec{x}))\quad\text{或}\quad\argmax_{\vec{x}\in\Omega}f_0(\vec{x})=\argmax_{\vec{x}\in\Omega}\phi(f_0(\vec{x}))
    • 对任意单调减函数ψ:f0(Ω)→R\psi:f_0(\Omega)\to\R，有 arg min⁡x⃗∈Ωf0(x⃗)=arg max⁡x⃗∈Ωψ(f0(x⃗))或arg max⁡x⃗∈Ωf0(x⃗)=arg min⁡x⃗∈Ωψ(f0(x⃗))\argmin_{\vec{x}\in\Omega}f_0(\vec{x})=\argmax_{\vec{x}\in\Omega}\psi(f_0(\vec{x}))\quad\text{或}\quad\argmax_{\vec{x}\in\Omega}f_0(\vec{x})=\argmin_{\vec{x}\in\Omega}\psi(f_0(\vec{x}))

    注意上述函数ϕ,ψ\phi,\psi都需要在f0(Ω)f_0(\Omega)上单调。

  • 一个经典的应用就是极大似然估计中将似然函数转换为对数似然函数。【y=log⁡xy=\log x在(0,+∞)(0,+\infty)上为单调函数】

松弛变量（slack variables）

另一种转换方法是使用松弛变量，可以将不等式约束与等式约束互相转换。其形式如下：

  • 考虑上述凸优化问题标准形式，设S⊆{1,2,⋯ ,m}S\subseteq\{1,2,\cdots,m\}（不等式约束指标集），那么这一问题与下述问题等价： min⁡x⃗∈Rn,s⃗∈R+Sf0(x⃗)s.t.fi(x⃗)+si=0,∀i∈S,fi(x⃗)≤0,∀i∈{1,…,m}∖S,hj(x⃗)=0,∀j∈{1,…,p}.\begin{aligned} &\min_{\substack{\vec{x} \in \mathbb{R}^n, \\ \vec{s} \in \mathbb{R}_+^{S}}} f_0(\vec{x})\\ \text{s.t.} \quad & f_i(\vec{x}) + s_i = 0, && \forall i \in S, \\ & f_i(\vec{x}) \leq 0, && \forall i \in \{1, \dots, m\} \setminus S, \\ & h_j(\vec{x}) = 0, && \forall j \in \{1, \dots, p\}. \end{aligned} 其中R+S={(xi)i∈S∣xi≥0,∀i∈S}\mathbb{R}_+^{S}=\{(x_i)_{i\in S}\mid x_i\geq 0,\forall i\in S\}，而s⃗\vec{s}也被称作松弛变量。

上境图重述

那么目标函数与约束之间能否进行转换？可以！考虑上述凸函数的标准形式，那么其可以进行上境图重述如下：

min⁡t∈R,  x∈Rnts.t.t≥f0(x⃗),fi(x⃗)≤0,∀i∈{1,…,m}ht(x⃗)=0,∀j∈{1,…,p}.\begin{aligned} \min_{t \in \mathbb{R}, \; x \in \mathbb{R}^n} \quad & t \\ \text{s.t.} \quad & t \geq f_0(\vec{x}), \\ & f_i(\vec{x}) \leq 0, \quad \forall i \in \{1, \dots, m\}\\ &h_t(\vec{x})=0,\quad\forall j \in \{1, \dots, p\}. \end{aligned}

这样就将目标函数大大简化，但代价是约束变得更加复杂（特别当f0f_0为非线性函数时）。【为什么叫上境图重述？因为t≥f0(x⃗)t \geq f_0(\vec{x})对应的可行域就是上境图】

  • 下面给一个使用的实例（Elastic Net正则化问题）：设A∈Rn×m,y⃗∈RnA\in\R^{n\times m},\vec{y}\in\R^n，考虑下述优化问题 min⁡x⃗∈Rn{∥Ax⃗−y⃗∥22+α∥x⃗∥22+β∥x⃗∥1}\min_{\vec{x} \in \mathbb{R}^n} \left\{ \|A\vec{x} - \vec{y}\|_2^2 + \alpha \|\vec{x}\|_2^2 + \beta \|\vec{x}\|_1 \right\} 其中α∥x⃗∥22+β∥x⃗∥1\alpha \|\vec{x}\|_2^2 + \beta \|\vec{x}\|_1被称作Elastic Net正则化项，它结合了一阶范数与二阶范数的正则惩罚。
    • 由于目标函数不可微，我们考虑进行上境图重述： min⁡t∈Rx⃗∈Rn∥Ax⃗−y⃗∥22+α∥x⃗∥22+βts.t.t≥∥x⃗∥1.\begin{aligned} \min_{\substack{t \in \mathbb{R}\\\vec{x}\in\R^n}} & \quad \|A\vec{x} - \vec{y}\|_2^2 + \alpha \|\vec{x}\|_2^2 + \beta t \\ \text{s.t.} & \quad t \geq \|\vec{x}\|_1. \end{aligned} 然而此时约束又不可微了。对此，注意到 ∥x⃗∥1=∑i=1n∣xi∣=∑i=1nmax⁡{−xi,xi}\|\vec{x}\|_1=\sum_{i=1}^n|x_i|=\sum_{i=1}^n\max\{-x_i,x_i\} 因此我们可以将这个约束拆分为 t≥∑i=1nsisi≥xi,∀i∈{1,…,n}si≥−xi,∀i∈{1,…,n}.\begin{aligned} t &\geq \sum_{i=1}^n s_i \\ s_i &\geq x_i, \quad \forall i \in \{1, \ldots, n\} \\ s_i &\geq -x_i, \quad \forall i \in \{1, \ldots, n\}. \end{aligned} 其中s⃗=(s1,⋯ ,sn)\vec{s}=(s_1,\cdots,s_n)为松弛变量。【tt和s⃗\vec{s}优化方向是相同的，因此最终最优解一定能使si=∣xi∣s_i=|x_i|】