【约束优化】一次搞定拉格朗日，对偶问题，弱对偶定理，Slater条件和KKT条件

1. 原问题的拉格朗日等价形式

对一个约束优化问题：
$$\begin{gathered} \underset{\mathbf{x}}{\min }f(\mathbf{x}) \\ \text{s.t. }{g}_i(\mathbf{x})\le 0,i=1,\cdots ,m \\ {h}_i(\mathbf{x})=0,i=1,\cdots ,p \end{gathered}$$

• 不等式约束：$g_i:{\mathbb{R}}^n\mapsto \mathbb{R},i=1,\cdots ,m$

• 等式约束：$h_i:{\mathbb{R}}^n\mapsto \mathbb{R},i=1,\cdots ,p$

• 可行域： Ω = { x ∈ R n : g i ( x ) ≤ 0 , h j ( x ) = 0 , i = 1 , ⋯ , m , j = 1 , ⋯ , p } \Omega=\{\mathbf{x}\in\R^n:g_i(\mathbf{x})\leq0,h_j(\mathbf{x})=0,i=1,\cdots,m,j=1,\cdots,p\} Ω={x∈Rn:gi​(x)≤0,hj​(x)=0,i=1,⋯,m,j=1,⋯,p}

• 拉格朗日函数：$L(\mathbf{x},\lambda ,\mu )=f(\mathbf{x})+{\sum }_{i=1}^m{\lambda }_i{g}_i(\mathbf{x})+{\sum }_{j=1}^p{\mu }_j{h}_j(\mathbf{x}),{\lambda }_i\ge 0$

可以看到：

• case 1：当 $\mathbf{x}\in \Omega$ 时，$L(\mathbf{x},\lambda ,\mu )=f(\mathbf{x})+\underset{\le 0}{\underbrace{\sum {\lambda }_i{g}_i}}+\underset{=0}{\underbrace{\sum {\mu }_j{h}_j}}\le f(\mathbf{x})$，因此 $\underset{\lambda \ge 0,\mu }{\max }L(\mathbf{x},\lambda ,\mu )=f(\mathbf{x})$
• case 2：当 $\mathbf{x}\notin \Omega$ 时，$L(\mathbf{x},\lambda ,\mu )=f(\mathbf{x})+\underset{+\infty }{\underbrace{\sum {\lambda }_i{g}_i}}+\underset{+\infty }{\underbrace{\sum {\mu }_j{h}_j}}=\infty$
• 综合上述情况：

$$f(\mathbf{x})=\{\begin{array}{l}\underset{\lambda \ge 0,\mu }{\max }L(\mathbf{x},\lambda ,\mu ),\mathbf{x}\in \Omega \\ +\infty ,\text{otherwise}\end{array}$$

因此原问题（Primal）：$\underset{\mathbf{x}\in \Omega }{\min }f(\mathbf{x})\iff \underset{\mathbf{x}\in {\mathbb{R}}^{\mathbf{n}}}{\min }\underset{\lambda \ge 0,\mu }{\max }L(\mathbf{x},\lambda ,\mu )$

2. 对偶函数和对偶问题

【思考】：现在我们知道了原问题等价于求拉格朗日函数的最大值再求最小值，那么倘若交换 $\min$ 和 $\max$ 运算，即 $\underset{\lambda \ge 0,\mu }{\max }\underset{\mathbf{x}\in {\mathbb{R}}^{\mathbf{n}}}{\min }L(\mathbf{x},\lambda ,\mu )$ 是否依旧和原问题等价呢？

于是我们定义：

• 对偶函数（Dual Function）：$q(\lambda ,\mu ):=\underset{\mathbf{x}}{\min }L(\mathbf{x},\lambda ,\mu )$
• 对偶问题（Dual Problem）：$\underset{\lambda \ge 0,\mu }{\max }q(\lambda ,\mu )$

【思考】：我们对原问题和对偶问题是否等价很感兴趣。如果他们不等价，那么原问题和对偶问题有怎样的关系？在某些特殊情况下，原问题和对偶问题等价？

3. 弱对偶定理

【定理】：对任意 $\mathbf{x}\in \Omega$（原问题可行） 和任意 $\lambda \ge 0,\mu$（对偶问题可行），$q(\lambda ,\mu )\le f(\mathbf{x})$ 恒成立。

【证明】：设 ${\mathbf{x}}^{\ast }$ 是原问题的最优解，则对任意 $\lambda \ge 0,\mu ,\mathbf{x}\in \Omega$ 有如下不等式：
$$\begin{gathered} q(\lambda ,\mu )=\underset{\mathbf{x}}{\min }L(\mathbf{x},\lambda ,\mu )\le L({\mathbf{x}}^{\ast },\lambda ,\mu ) \\ \le \underset{\lambda \ge 0,\mu }{\max }L({\mathbf{x}}^{\ast },\lambda ,\mu )=f({\mathbf{x}}^{\ast })\le f(\mathbf{x}) \end{gathered}$$

因为在对偶函数中，$\mathbf{x}\in {\mathbb{R}}^n$，而${\mathbf{x}}^{\ast }\in \Omega ,\Omega \subset {\mathbb{R}}^n$，所以 $\underset{\mathbf{X}}{\min }L(\mathbf{x},\lambda ,\mu )\le L({\mathbf{x}}^{\ast },\lambda ,\mu )$

【推论】：设 ${\lambda }^{\ast },{\mu }^{\ast }=\arg \underset{\lambda \ge 0,\mu }{\max }q(\lambda ,\mu )$，并且 ${\mathbf{x}}^{\ast }=\arg \underset{\mathbf{x}\in \Omega }{\max }f(\mathbf{x})$，则由弱对偶定理，我们可以得到：
$$q({\lambda }^{\ast },{\mu }^{\ast })\le f({\mathbf{x}}^{\ast })\iff \underset{\lambda \ge 0,\mu }{\max }\underset{\mathbf{x}}{\min }L\le \underset{\mathbf{x}\in \Omega }{\min }\underset{\lambda \ge 0,\mu }{\max }L$$

4. 强对偶定理

在约束优化问题中，强对偶定理是指原问题的最优值与其对偶问题的最优值相等的情况。然而，强对偶定理成立的条件依赖于问题的具体结构和性质。以下是针对不同类型的优化问题，强对偶定理成立的常见条件：

• 线性规划问题（LP）：只要原问题有一个可行解并且最优解存在，那么强对偶定理总是成立。在这种情况下，强对偶性条件非常宽松。
• 凸（Convex）优化问题：对于凸优化问题，强对偶定理的成立通常需要满足Slater 条件。该条件是针对凸优化问题中强对偶性成立的充分条件，Slater 条件要求：
  • 凸性：目标函数 $f(\mathbf{x})$ 和不等式约束函数 $g_i(\mathbf{x})$ 必须是凸函数，等式约束函数 $h_j(\mathbf{x})$ 必须是仿射函数（即线性函数）。
  • 严格可行性：$\exists {\mathbf{x}}_0\text{s.t.}\forall i{g}_i({\mathbf{x}}_0)<0,h(\mathbf{x})=0$

由弱对偶定理我们有：$q({\lambda }^{\ast },{\mu }^{\ast })\le L({\mathbf{x}}^{\ast },{\lambda }^{\ast },{\mu }^{\ast })\le f({\mathbf{x}}^{\ast })$，所以当 $q({\lambda }^{\ast },{\mu }^{\ast })=f({\mathbf{x}}^{\ast })$ 时，
$$\begin{array}{rl}& L({\mathbf{x}}^{\ast },{\lambda }^{\ast },{\mu }^{\ast })=f({\mathbf{x}}^{\ast })\\ & \Rightarrow \sum _{i=1}^m{\lambda }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })+\underset{=0}{\underbrace{\sum _{j=1}^p{\mu }_i^{\ast }{h}_i({\mathbf{x}}^{\ast })}}=0\\ & \Rightarrow \sum _{i=1}^m{\lambda }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })=0\\ & \Rightarrow {\lambda }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })=0\Rightarrow \text{KKT: 互补松弛条件}\end{array}$$

5. KKT条件

KKT（Karush-Kuhn-Tucker）条件是用于解决非线性优化问题的一个重要工具，特别是带有约束的优化问题。它为寻找局部最优解提供了必要条件和充分条件（在某些情况下）。

• 在凸优化问题中，如果目标函数和不等式约束函数都是凸的，KKT条件不仅是局部最优解的必要条件，还是全局最优解的充分条件。这种情况下，满足KKT条件的解就是最优解。
• 在非凸优化问题中，KKT条件仍然是局部最优解的必要条件，但不再是充分条件。也就是说，即使一个解满足KKT条件，它也不一定是全局最优解。只有在特定问题结构下（如凸性条件），KKT条件才是充分条件。

【KKT条件】：设 ${\mathbf{x}}^{\ast },{\lambda }^{\ast },{\mu }^{\ast }$ 分别是原问题和对偶问题的最优解，则满足如下条件：

• 原问题可行：$g_i({\mathbf{x}}^{\ast })\le 0,\forall i=1,\cdots ,m$，$h_j({\mathbf{x}}^{\ast })=0,\forall j=1,\cdots ,p$
• 对偶问题可行：${\lambda }_i^{\ast }\ge 0,\forall i=1,\cdots ,m$
• 互补松弛条件：${\lambda }_i^{\ast }{g}_i(\mathbf{x})=0,\forall i=1,\cdots ,m$
• 稳定点：${\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\lambda }^{\ast },{\mu }^{\ast })=0$

下一节将介绍支持向量机SVM的数学原理