主要介绍一下 Dual Problem 和 KKT Conditions。Dual Problem 参考该课件，KKT Conditions 参考该课件。
Lagrangian Function
我们考虑如下最优化问题：
\begin{align}
\min_{x\in \mathbb{R}^n} & \quad f(x) \\
\text{s.t.} \quad & h_i(x) \le 0 &\forall i \in [m] \\
& l_i(x) = 0 &\forall i \in [r]
\end{align}
记该问题的最优值为 $f^*$。
本文中会称上述问题为 Primal Problem。首先求得它的 Lagrangian Function:
\[ \mathcal{L}(x, \mu, \nu) = f(x) + \mu^\top h(x) +\nu^\top l(x) = L(x,\lambda) = f(x) + \lambda^\top \begin{pmatrix}h(x)\\l(x)\end{pmatrix} \]
其中，$h(x) = (h_1(x), h_2(x), \dots, h_m(x))^\top$，$l(x) = (l_1(x), l_2(x), \dots, l_r(x))^\top$
Remark 1: 对任意 feasible $x$，$f(x) = \sup_{\mu \geq 0, v} \mathcal{L}(x, \mu, \nu)$，并且 supremum 当且仅当 $\mu^\top h(x) = 0$。
Remark 2: 对任意 non-feasible $x$，$\sup_{\mu \geq 0, v} \mathcal{L}(x, \mu, \nu) = +\infty$。（考虑 non-feasible 的两种情况即可）
Remark 3: $f^* = \inf_{x\in \mathbb{R}^n} \sup_{\mu\ge 0, \nu} \mathcal{L}(x, \mu, \nu)$。
Lagrange Dual Problem
定义 Lagrange Dual Function: $g(\mu, \nu) = \inf_{x} \mathcal{L}(x, \mu, \nu)$
注意到这里取的 $x\in \mathbb{R}^n$ 并不要求满足 $g(x) \le 0$ 和 $h(x)=0$。
定义 Lagrange Dual Problem 为
\begin{align}
\max_{\mu\in \mathbb{R}^m, \nu \in \mathbb{R}^r} & \quad g(\mu, \nu) \\
\text{s.t.} \quad & \mu \ge 0
\end{align}
记该问题的最优值为 $g^*$。
Remark 4：$g^* = \sup_{\mu \ge 0, \nu} \inf_{x} \mathcal{L}(x, \mu, \nu)$。
Remark 5：无论 Primal Problem 是否为 Convex Problem，Dual Problem 都是 Convex Problem。（考虑 $g$ 的 concavity (最大化问题)，需要补充证明）
Weak and Strong Duality
Weak Duality: $g^* \le f^*$ (Always hold)
Strong Duality: $g^* = f^*$
Lemma 6. Weak Duality always hold, i.e.
\[g^* = \sup_{\mu \ge 0, \nu} \inf_{x} \mathcal{L}(x, \mu, \nu) \le \inf_{x} \sup_{\mu\ge 0, \nu} \mathcal{L}(x, \mu, \nu) = f^*\]
这个也叫 Max-min Inequality ，证明可见 Wikipedia。
一个比较形象的证明：假设 Alice 和 Bob 在玩游戏，Alice 决定 $x$ 的取值，Bob 决定 $(\mu, \nu)$ 的取值，在两个人选定取值后，要求 Alice 给予 Bob $\mathcal{L}(x, \mu, \nu)$ 的金币。假设两个人都 act optimal ，现在考虑先后手：假设 Alice 先手，那么显然Alice 需要付出 $g^*$ 的金币；而假若 Bob 先手，那么 Bob 会得到 $f^*$ 的金币，然后我们同时也容易想到这个游戏先手优势很大，同时该游戏对 Alice 不公平，那么就可以得到 $g^* \le f^*$。
Strong Duality 并不是一直成立，有不少关于 Strong Duality 成立的充分条件，比较有名的就是 Slater’s Conditions：
Theorem 7 (Slater’s Theorem). 若 Primal Problem 是 convex problem，并且在 feasible set 中存在 $x_0$ 满足 Slater’s Condition，i.e.
\[\exists x_0: h_i(x) < 0, l_j(x) = 0, l_j \text{ is linear operator},\forall i \in [m], j \in [r]\]
那么有 Strong Duality 成立。
（需要补充证明）
Karush-Kuhn-Tucker Conditions
KKT Conditions:
\begin{align}
\text{Primal Feasibility: } & h(x) \le 0, l(x) = 0\\
\text{Dual Feasibility: } & \mu \ge 0\\
\text{Complementary Slackness: } & \mu^\top h(x) = 0\\
\text{Stationarity: } & 0\in \partial f(x) + \sum_{i=1}^{m} \mu_i\partial h_i(x) + \sum_{j=1}^{r} \nu_j \partial l_j(x)
\end{align}
为什么总要考虑 $(x, \mu, \nu)$ 是否满足 KKT Conditions？
1. KKT Conditions 总是 optimal 的充分条件
2. 如果 strong duality holds，那么 KKT Conditions 也是 optimal 的必要条件
（需要补充证明）
Leave a Reply