凸优化

Posted on Edited on In
Symbols count in article: 1.8k Reading time ≈ 2 mins.
学着玩一玩

基础定义

  • affine set ：包含所有元素的线性组合（\(\theta x_1 + (1-\theta)x_2 \in C, \forall \theta \in R\)）

    • 对于任意集合\(S\)，其所有元素的线性组合为包含\(S\)的最小仿射集，记为\(\text{aff} S\)

  • convex set ：包含所有元素的凸组合（\(\theta x_1 + (1-\theta)x_2 \in C, \forall \theta \in [0,1]\)）

    • 对于任意集合\(S\)，其所有元素的线性组合为包含\(S\)的最小仿射集，记为\(\text{conv} S\)

  • cone：包含所有元素的非负组合（\(\theta_1 x_1 + \theta_2 x_2 \in C, \forall \theta_1, \theta_2 \geq 0\)）

  • hyperplane：\(\{x | a^Tx = b\}\)，halfspaces：\(\{x|a^Tx \leq b\}\)

  • 球体（包括范数球），椭球体，锥（含范数锥）都是凸集

保凸集凸性

  • 相交：如果\(C_1, C_2\)为凸集，那么\(C_1 \cap C_2\)为凸集

  • 仿射变换及其逆变换：如果\(C\)为凸集，\(f(x)=Ax+b\)为仿射变换

    那么\(f(C) = \{f(x) | x \in C\}\)和\(f^{-1}(C) = \{x|f(x) \in C\}\)构成凸集

    • 注意到\(\theta f( x_1) + (1-\theta) f(x_2) = f(\theta x_1 + (1-\theta)x_2)\)，因此\(f(C)\)构成凸集
    • 对于\(f^{-1}\)，等价于证明\(f(x_1) \in C, f(x_2) \in C \Rightarrow f(\theta x_1 + (1-\theta)x_2) \in C\)，由上面的式子是显然的

  • 透视变换：记\(P : R^n \times R_{++} \to R^n\)为\(P(x, t) = x/t\)

    那么，当\(C\)为凸集时，\(P(C)\)和\(P^{-1}(C)\)为凸集

    • 按照定义去配凑即可，由于这并不是一个线性函数，因此在理解时可能由大问题

  • 线性分式函数：对于\(x\)，定义\(f(x) = \frac{Ax + b}{c^T x + d}\)，则对于凸集\(C\)，\(f(C)\)和\(f^{-1}(C)\)都是凸集

    • 线性分式函数可以视为仿射变换和透视变换的复合

分离超平面定理

  • 对于凸集\(C\)和\(D\)，如果\(C \cap D = \emptyset\)，那么存在超平面\(\{x|a^Tx = b\}\)，使得\(\forall x \in C, a^Tx \leq b\)并且\(\forall x \in D, a^Tx \geq b\)
    • 证明的思路是构造性的，取\(C, D\)上距离最小的两点\(c, d\)，作垂直于直线\(cd\)，过\(c, d\)中点的平面
  • 对于凸集\(C\)边界上的每一点\(x_0\)，存在超平面，使得\(\forall x \in C, a^Tx \leq b\)并且\(a^Tx_0 = b\)成立
    • 这个称为支撑超平面定理
    • 取凸集的内部\(\text{int} C\)和\(\{x_0\}\)，对他们运用分离超平面定理

凸函数

  • 设\(f : R^n \to R\)为凸，当且仅当\(\text{dom} f\)为凸，并且\(\forall x, y \in dom\;f, 0 \leq \theta \leq 1\)，有\(f(\theta x + (1-\theta) y) \leq \theta f(x) + (1-\theta) f(y)\)

  • 第二定义：对于任意\(x \in dom\;f, v \in R^n\)，\(g(t) = f(x + tv)\)为凸函数

    （注意\(g\)是一维的函数）

根据上述两个定义，在研究高维时，先对一维情况入手，再使用第二定义将是不错的方法

  • 一阶条件：\(f\)可微时，\(f\)为凸函数当且仅当\(\forall x, y \in dom\;f\)，有\(f(y) \geq f(x) + \nabla f(x)^T(y-x)\)

    一维情况下，左边推右边的证明是构造性的，右边推左边则是进行逼近

    多维证明一维就使用第二定义

    • 如果\(\nabla f(x_0) = 0\)，那么根据一阶条件，有\(\forall y \in dom\;f, f(y) \geq f(x_0)\)

  • 二阶条件：\(f\)二阶可微时，\(f\)为凸函数当且仅当\(\nabla^2f(x) \geq 0\)

KKT条件

...前面的所有的知识都是为了推导这个条件，我先在这里给咕咕咕了