Optimization: Dual Problem and Karush-Kuhn-Tucker Conditions

主要介绍一下 Dual Problem 和 KKT Conditions。Dual Problem 参考该课件，KKT Conditions 参考该课件。

---

Lagrangian Function

我们考虑如下最优化问题：

$$\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{min}& f(x)\\ \text{s.t.}& h_i(x)\le 0& \mathrm{\forall }i\in [m]\\ & l_i(x)=0& \mathrm{\forall }i\in [r]\end{array}$$
记该问题的最优值为 $f^{\ast }$。

本文中会称上述问题为 Primal Problem。首先求得它的 Lagrangian Function:
$$\mathcal{L}(x,\mu ,\nu )=f(x)+{\mu }^{\mathrm{\top }}h(x)+{\nu }^{\mathrm{\top }}l(x)=L(x,\lambda )=f(x)+{\lambda }^{\mathrm{\top }}\left(\begin{array}{c}h(x)\\ l(x)\end{array}\right)$$
其中，$h(x)=(h_1(x),h_2(x),\dots ,h_m(x){)}^{\mathrm{\top }}$，$l(x)=(l_1(x),l_2(x),\dots ,l_r(x){)}^{\mathrm{\top }}$

Remark 1: 对任意 feasible $x$，$f(x)=\underset{\mu \ge 0,v}{sup}\mathcal{L}(x,\mu ,\nu )$，并且 supremum 当且仅当 ${\mu }^{\mathrm{\top }}h(x)=0$。

Remark 2: 对任意 non-feasible $x$，$\underset{\mu \ge 0,v}{sup}\mathcal{L}(x,\mu ,\nu )=+\mathrm{\infty }$。（考虑 non-feasible 的两种情况即可）

Remark 3: $f^{\ast }=\underset{x\in {\mathbb{R}}^n}{inf}\underset{\mu \ge 0,\nu }{sup}\mathcal{L}(x,\mu ,\nu )$。

---

Lagrange Dual Problem

定义 Lagrange Dual Function: $g(\mu ,\nu )=\underset{x}{inf}\mathcal{L}(x,\mu ,\nu )$
注意到这里取的 $x\in {\mathbb{R}}^n$ 并不要求满足 $g(x)\le 0$ 和 $h(x)=0$。

定义 Lagrange Dual Problem 为

$$\begin{array}{rl}\underset{\mu \in {\mathbb{R}}^m,\nu \in {\mathbb{R}}^r}{max}& g(\mu ,\nu )\\ \text{s.t.}& \mu \ge 0\end{array}$$
记该问题的最优值为 $g^{\ast }$。

Remark 4：$g^{\ast }=\underset{\mu \ge 0,\nu }{sup}\underset{x}{inf}\mathcal{L}(x,\mu ,\nu )$。

Remark 5：无论 Primal Problem 是否为 Convex Problem，Dual Problem 都是 Convex Problem。（考虑 $g$ 的 concavity (最大化问题)，需要补充证明）

---

Weak and Strong Duality

Weak Duality: $g^{\ast }\le f^{\ast }$ (Always hold)
Strong Duality: $g^{\ast }=f^{\ast }$

Lemma 6. Weak Duality always hold, i.e.
$$g^{\ast }=\underset{\mu \ge 0,\nu }{sup}\underset{x}{inf}\mathcal{L}(x,\mu ,\nu )\le \underset{x}{inf}\underset{\mu \ge 0,\nu }{sup}\mathcal{L}(x,\mu ,\nu )=f^{\ast }$$

这个也叫 Max-min Inequality ，证明可见 Wikipedia。
一个比较形象的证明：假设 Alice 和 Bob 在玩游戏，Alice 决定 $x$ 的取值，Bob 决定 $(\mu ,\nu )$ 的取值，在两个人选定取值后，要求 Alice 给予 Bob $\mathcal{L}(x,\mu ,\nu )$ 的金币。假设两个人都 act optimal ，现在考虑先后手：假设 Alice 先手，那么显然Alice 需要付出 $g^{\ast }$ 的金币；而假若 Bob 先手，那么 Bob 会得到 $f^{\ast }$ 的金币，然后我们同时也容易想到这个游戏先手优势很大，同时该游戏对 Alice 不公平，那么就可以得到 $g^{\ast }\le f^{\ast }$。

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.
$$\mathrm{\exists }{x}_0:h_i(x)<0,l_j(x)=0,l_j\text{ is linear operator},\mathrm{\forall }i\in [m],j\in [r]$$
那么有 Strong Duality 成立。

（需要补充证明）

---

Karush-Kuhn-Tucker Conditions

KKT Conditions:
$$\begin{array}{rl}\text{Primal Feasibility: }& h(x)\le 0,l(x)=0\\ \text{Dual Feasibility: }& \mu \ge 0\\ \text{Complementary Slackness: }& {\mu }^{\mathrm{\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{array}$$

为什么总要考虑 $(x,\mu ,\nu )$ 是否满足 KKT Conditions？
1. KKT Conditions 总是 optimal 的充分条件
2. 如果 strong duality holds，那么 KKT Conditions 也是 optimal 的必要条件

（需要补充证明）