<aside> 👐🏻

Conic Optimization / Conic Programming LP →CP

不等式约束替换为凸锥集（广义不等式）的 LP

$$ \begin{split}\begin{array}{ll} {minimize} & c^Tx \\ {subject to} & Ax=b,\\ & x\in K, \end{array}\end{split} $$

• Linear Optimization $K=\mathbb R_+^n$
• 二次规划 $Q_r^n$
• power cone $P_n^{\alpha,1-\alpha}$
• exponential cone $K_{\exp}$
• geometric programming → exponential cone
• symmetric positive semidefinite → semidefinite programming $S_+^n$→ matrix value CP </aside>

Duality

• feasible set 可行集

  $$ {\cal F}_p=\{x\in \R^n \mid Ax=b\} \cap K $$

• 优化问题的值的下确界infimum

  $$ p^\star = \inf\{c^Tx~:~ x\in{\cal F}_p\}, $$

Dual cone

$$ K^* = \{ y\in \real^n~:~ y^Tx\geq 0\ \forall x\in K\}. $$

如何直观理解凸优化理论中【对偶锥】的概念 https://www.zhihu.com/question/264853229/answer/286677771

• self-dual

  $(\real_+^n)^* = \real_+^n.$ $(Q^n)^=Q^n,(Q_r^n)^,(S_+^n)^*$

Infeasibility certificates

<aside> 👐🏻

Farkas lemma  (see Sec. 2.3 (Infeasibility in linear optimization))

定义$A(K) = \{Ax~:~x\in K\}.$ 可行性↔ $b\in A(K)$ 不可行且$b\not\in\mathrm{cl}(A(K))$，存在过远点的超平面划分b和锥，对偶锥可以找到$y$

$$ b^Ty > 0, \quad (Ax)^Ty \leq 0\ \forall x\in K. $$

1. 可行
2. limit-feasible $\|Ax_n-b\|\to 0$ → ill-posed
3. 不可行，但存在$y$满足刚才的不等式组 → infeasibility certificates </aside>

Lagrangian

$$ L(x, y, s) = c^Tx + y^T(b-Ax) - s^T x. $$

可行点$x^\in{\cal F}_p$ 对偶锥$(y^,s^)\in\real^m\times K^$

满足$x\in K$等价于$\exists s\in S^*,s^Tx\ge 0$

$$ L(x^, y^, s^)=c^Tx^+(y^)^T\cdot 0 - (s^)^Tx^\leq c^T x^. $$

对偶目标函数是拉格朗日函数的极小值

$$ \begin{split}g(y, s) = \min_x L(x,y,s) = \min_x x^T( c - A^T y - s ) + b^T y = \left \{ \begin{array}{ll} b^T y, & c - A^T y - s = 0,\\ -\infty, & \text{otherwise}. \end{array} \right.\end{split} $$

整理之后，原始问题变化为