优化

1. 优化问题

对于函数 $f(x)$，我们希望找到 $x \in \chi$，使得 $f(x)$ 最小或最大。

2. 线性规划 (LP)

已知 $c=(c_1,c_2,\cdots,c_n)^T, x=(x_1,x_2,\cdots,x_n)^T$， $A$ 为 $m \times n$ 矩阵，$b$ 为 $m$ 维向量。

已知 $x\succeq 0$ ，$Ax\preceq b$，求 $c^Tx$ 的最大值。

含有绝对值的情况： 令 $x_1 = \max\{x,0\},x_2=\max\{-x,0\}$, 则 $\lvert x\rvert = x_1+x_2,~~ x=x_1-x_2$

3. 二次规划 (QP)

已知 $Ax\preceq b$，最小化 $x^TPx+c^Tx+d$

4. 二次约束二次规划 (QCQP)

已知 $\frac{1}{2}x^TP_ix+q_i^Tx+r_i\leq 0, i=1,\cdots,m$，且 $Ax=b$

最小化 $\frac{1}{2}x^TP_0x+q_0^Tx+r_0$

5. 几何规划 (GP)

已知：对于 $i\in C_1$，$f_i(x)=b_i$，对于 $i\in C_2$，$f_i(x)<b_i$，且 $x\succeq0$

最小化 $f_0(x)$