凸优化期中 cheat sheet

2020-11-25
目录 展开

Ch2 凸集

  • 凸锥：$x = \theta_1x_1 + \theta_2x_2, \quad \theta_1,\theta_2 \ge 0$
    • 满足凸组合、锥组合（感觉更简单？
  • 球：$B(x_c,r) = \{x|\;\|x – x_c\|_2\le r\} = \{x_c + ru | \|u\|_2\le 1\}$
  • 椭球：$\{x | (x-x_c)^TP^{-1}(x-x_c)\le 1\}, P\in\mathbb{S}^n_{++}$
  • 范数球：$\{x|\;\|x-x_c\|\le r\}$
  • 范数锥：$\{(x,t)|\;\|x\|\le t\}$
  • 半定锥：所有半定矩阵的集合 $\mathbb{S}^n_{+} = \{X\in\mathbb{S}^n | X\succeq 0\}$

保凸运算：

  • 定义：凸组合
  • 交集
  • affine func: $f(x) = Ax + b$
  • perspective func: $P(x,t) = x/t, t > 0$
  • linear-fractional func: $f(x) = \dfrac{Ax+b}{c^Tx + d}, c^Tx + d > 0$

正常锥：闭集（包含所有序列的极限）、有非空内点、不包含线（$K\bigcap -K = 0$）

  • 正常锥可以定义不等式：$x\preceq_Ky$

对偶锥：$K^* = \{y|y^Tx\ge 0, \forall x \in K\}$

半定锥的对偶锥、范数锥的对偶锥

Ch3 凸函数

多元函数求导：$$\langle \triangledown f(x), v\rangle = \lim_{t\rightarrow 0}\frac{f(x+tv)-f(x)}{t}$$

log-sum-exp 求导

判凸条件：

  1. 定义：如果 $\textbf{dom}f$ 是凸集，且

$$f(\theta x + (1-\theta)y)\le\theta f(x) + (1-\theta)f(y)$$

对所有 $x,y\in \textbf{dom}f, 0\le \theta\le 1$ 都成立

  1. 将函数限制在任意直线在定义域内的部分上时仍是凸的：$f(x)$ 是凸函数当且仅当 $\forall x\in \textbf{dom}f, v\in\mathbb{R}^n,g:\mathbb{R}\rightarrow\mathbb{R},$

$$g(t) = f(x+tv), \quad\textbf{dom}\;g = \{t|x+tv\in\textbf{dom}f\}$$ 

是凸函数

  1. 一阶条件：对于定义在凸集上的可微函数 $f$ ， $f$ 是凸函数当且仅当

$$f(y)\ge f(x) + \triangledown f(x)^T(y-x),\quad \forall\; x,y\in \textbf{dom}f$$

  1. 二阶条件（二阶连续可微时）：$\triangledown^2 f(x)\succeq 0, \forall\; x\in \textbf{dom}f$。$\triangledown^2 f(x)\succ 0$ 严格凸；$\triangledown^2 f(x)$ 特征值有下界，强凸。
  2. 上镜图是凸集
  3. 梯度单调性：$f$ 为可谓函数，则 $f$ 为凸函数当且仅当 $\textbf{dom}f$ 为凸集且 $\triangledown f$ 为单调映射，即

$$(\triangledown f(x) – \triangledown f(y))^T(x-y)\ge 0, \quad \forall\; x,y\in \textbf{dom}f$$

  1. 保凸运算：
    1. $f\Rightarrow\alpha f$
    2. $f_1,f_2\Rightarrow f_1+f_2$
    3. $f\Rightarrow f(Ax+b)$
    4. $f_1,f_2,…,f_m\Rightarrow f(x) = \max\{f_1,f_2,…,f_m\}$
    5. $\forall\;y\in\mathcal{A}, f(x,y)$ is convex in $x\Rightarrow g(x) = \sup_{y\in\mathcal{A}}f(z,y)$ is convex
    6. $f(x) = h(g(x))$, $f$ convex if ① $g$ convex, $h$ convex, $h$ nondecreasing ② $g$ concave, $h$ convex, $h$ nonincreasing
    7. $f(x) = h(g(x)) = h(g_1(x),g_2(x),…,g_k(x))$, $f$ convex if ① $g_i$ convex, $h$ convex, $h$ nondecreasing in each argument ② $g_i$ concave, $h$ convex, $h$ nonincreasing in each argument
    8. $f(x,y)$ is convex in $(x,y)$ and $C$ is a convex set, $g(x) = \inf_{y\in C}f(x,y)$ is convex
    9. $g(x,t) = tf(\frac{x}{t})$

强凸：

  1. $g(x) = f(x) – \frac{m}{2}\|x\|^2$ 为凸函数，则 $f(x)$ 为强凸函数
  2. 定义：$f(\theta x + (1-\theta)y)\le\theta f(x) + (1-\theta)f(y) – \frac{m}{2}\theta(1-\theta)\|x-y\|^2$
  3. 梯度单调性：$(\triangledown f(x) – \triangledown f(y))^T(x-y)\ge m\|x-y\|^2$
  4. 二阶准则：$\triangledown^2 f(x)$ 特征值有下界

共轭函数：一定 convex$$f^*(y) = \sup_{x\in \text{dom}f}(y^Tx – f(x))$$

Ch4 凸优化问题

等价问题的 trick：引入等式约束、线性不等式引入松弛变量、求上镜图、多元问题分步求最优

SOCP 标准形式：$$ \begin{aligned} \min\quad&f^Tx\\ s.t.\quad&\|A_ix+b_i\|_2\le c_i^Tx + d_i,\quad i=1,…,m \\ & Fx=g \\ \end{aligned} $$ 

等价 SOCP：

  1. 二次规划

$$ \begin{aligned} \min\quad & q(x) = x^TQx + a^Tx + \beta,\;\text{assume }Q\succ 0,Q=Q^T\\ s.t.\quad & Ax=b\\ & x\ge 0\\ \end{aligned} $$ 

SOCP 等价形式：$$ \begin{aligned} \min\quad & u_0\\ s.t.\quad & \bar{u} = Q^{-\frac{1}{2}}x + \frac{1}{2}Q^{-\frac{1}{2}} a \\ & Ax=b\\ & x\ge 0\\ & (u_0, \bar{u}) \succeq_Q 0 \end{aligned} $$ 

  1. 二次约束

$$q(x) = x^TB^TBx + a^Tx + \beta \le 0$$

二次锥约束等价形式：$$(u_0, \bar{u}) \succeq_Q 0$$ $$\bar{u} = \bigg(\begin{matrix} Bx\\ \dfrac{a^Tx + \beta + 1}{2} \end{matrix}\bigg)\quad u_0 = \frac{1-a^Tx – \beta}{2}$$ 

  1. 最小化范数

$$\bar{v}_i = A_ix + b_i \in \mathbb{R}^{n_i}$$ $\min\sum_i\|\bar{v}_i\|$ 等价于 $$ \begin{aligned} \min\quad & \sum_i v_{i0}\\ s.t.\quad & \bar{v}_i = A_ix + b_i\\ & (v_{i0}, \bar{v}) \succeq_Q 0 \end{aligned} $$ $\max_{a\le i\le r}\|\bar{v}_i\|$ 等价于 $$ \begin{aligned} \min\quad & t\\ s.t.\quad & \bar{v}_i = A_ix + b_i\\ & (t, \bar{v}) \succeq_Q 0 \end{aligned} $$ $\min\sum_i^k\|\bar{v}_{[i]}\|$ 等价于 $$ \begin{aligned} \min\quad & \sum_{i=1}^m u_{i} + kt\\ s.t.\quad & \bar{v}_i = A_ix + b_i,\quad i=1,…,m\\ & \|{v}_i\|\le = u_i + t,\quad i=1,…,m\\ & u_i\ge 0,\quad i=1,…,m \end{aligned} $$ 

  1. 旋转锥

$$ w^Tw\le xy(x,y\ge 0) \iff \bigg\|\bigg(\begin{matrix} 2w \\ x-y \end{matrix}\bigg)\bigg\| \le x+y $$ 

SDP 标准形式：$$ \begin{aligned} \min\quad & \langle C, X \rangle\\ s.t.\quad & \mathcal{A}(x) = b\\ & X \succeq 0 \end{aligned} $$ $$\mathcal{A}(x) = (\langle A_1, X \rangle , …, \langle A_m, X \rangle)^T$$

对偶形式：$$ \begin{aligned} \min\quad & b^Ty\\ s.t.\quad & \mathcal{A}^*(y) + S = C\\ & S \succeq 0 \end{aligned} $$ $$\mathcal{A}^*(y) = \sum_{i=1}^m y_i A_i$$

Ch5 Dual

计算对偶式子：$$g(\lambda, v) = \inf_{x\in\mathbb{D}}L(x, \lambda, v) = \inf_{x\in\mathbb{D}} \bigg(f_0(x) + \sum_{i=1}^m\lambda_if_i(x) + \sum_{i=1}^pv_ih_i(x)\bigg)$$

slater 条件：存在一点，使得所有不等式严格成立（弱化：仿射函数除外）、所有等式成立

共轭和对偶：$$\begin{aligned} min \quad & f_0(x) \\ s.t. \quad & Ax \preceq b \\ & Cx = d \\ \end{aligned}$$ $$\begin{aligned} g(\lambda, v) =& \inf_x(f_0(x) + \lambda^T(Ax-b) + v^T(Cx-d)) \\ =& -b^T\lambda – d^Tv + \inf_x(f_0(x) + (A^T\lambda + C^T v)^T x) \\ =& -b^T\lambda – d^Tv – f_0^*(-A^T\lambda – C^Tv) \end{aligned}$$ 

KKT condition$$\triangledown f_0(x^*) + \sum_{i=1}^m \lambda_i^*\triangledown f_i(x^*) + \sum_{i=1}^p v_i^*h_i(x^*) = 0$$ $$\begin{aligned} f_i(x^*) \le& 0,\quad i = 1,…,m \\ h_i(x^*) = & 0,\quad i = 1,…,p \\ \lambda_i^* \ge& 0,\quad i = 1,…,m \\ \lambda_i^*f_i(x^*) =& 0,\quad i = 1,…,m \\ \end{aligned}$$

发表评论