4. 凸优化问题(1)

Convex-Optimization Problems(1)

0. 前言

• 介绍了一些经典的优化问题，不止于凸优化问题
• 仍然有很多问题（几何规划、向量规划、广义不等式约束等等）以及关于SDP和SOCP的一些拓展未在此处给出，未来用到的时候再继续写点。

1. Convex optimization problems

• Standard form:

  minimize $f_0(x)$

  subject to $f_i(x)\leq 0, i=1,\cdots,m, a^T_ix=b_i,i=1,\cdots,p$

  Note: $f_0$ is convex, $f_1,\cdots,f_n$ are convex, $a^T_ix=b_i$ are affine.

可以注意到凸优化问题的可行集为凸

• Any local optimal point is globally optimal

• Optimality criterion for differentiable $f_0$

  $x$ is optimal iff it’s feasible $(x\in X)$ and $\triangledown f_0(x)^T(y-x)\geq 0$

$-\triangledown f(x)$ 定义了一个支撑超平面切于 最优点

• Equivalent convex problem

包括消除、引入等式约束；加入松弛变量；极小化部分变量；化为上境图问题

2. Quasiconvex optimization

• Different point:

  $x$ is optimal if it’s feasible and $\triangledown f_0(x)^T(y-x)>0$

拟凸问题可以通过构造凸可行性问题来求解

3. Linear program

• minimize $c^Tx+d$

  subject to $Gx\preceq h, Ax=b$

线性目标函数对凸优化是普适的。

与线性分式问题等价

$\min |x|_1$ s.t. $Ax=b$ 是线性规划问题：
$\min t$ s.t. $|x|_1\leq t, Ax=b$ 1范数可以分解成各分量的线性不等式

4. Quadradic program

• minimize $(1/2)x^TPx+q^Tx+r$

  subject to $Gx\preceq h, Ax=b, P\in \textbf{S}^n_+$

• least-squares: minimize $|Ax-b|^2_2$

  analytical solution $x^\star = A^\dagger b$

$A^\dagger$ 是伪逆矩阵的意思， $A=U\Sigma V^T, A^\dagger=V\Sigma^+U^T$

5. Second-order cone programming

• minimize $f^Tx$

  subject to $|A_ix+b_i|_2\leq c^T_ix, i=1,\cdots,m, Fx=g$