在学习与工程之中，我们时常会遇到一些优化的问题，也就是要对某个目标函数求取极值，最简单的形式如下。
min x ∈ R n f ( x )
\large \min_{x \in \mathbb{R^n}}{f(x)}
x ∈ R n min f ( x )
这个式子表达的含义是以 x x x f ( x ) f(x) f ( x ) f f f max x f ( x ) \max_{x}{f(x)} max x f ( x ) min x − f ( x ) \min_{x}{-f(x)} min x − f ( x ) x x x
这样的例子有很多，最常见的就比如我们在机器学习中经常碰到的最小化代价函数。对于这样的问题，我们求解的方法很简单，只要能够求出一个点 x ′ x^\prime x ′ ∇ f ( x ′ ) = 0 \nabla f(x^\prime) = 0 ∇ f ( x ′ ) = 0
当然我们也知道，只有当 f f f f f f
我们在上一节的基础上进一步，如果 f f f
min x ∈ R n f ( x ) s . t h i ( x ) = 0 , i ∈ [ 1 , l ]
\large
\begin{aligned}
&\min_{x \in \mathbb{R^n}}{f(x)}\\
&s.t \quad h_i(x) = 0, i \in [1, l]
\end{aligned}
x ∈ R n min f ( x ) s . t h i ( x ) = 0 , i ∈ [ 1 , l ]
在这个问题中，我们对在定义域上的 x x x l l l h i h_i h i
这时就需要用到拉格朗日乘数法了，具体而言，我们首先来构建这么一个拉格朗日函数:
L ( x , λ ) = f ( x ) + ∑ i = 1 l λ i h i ( x ) x ∈ R n , λ ∈ R l
\begin{aligned}
&L(x, \lambda) = f(x) + \sum_{i=1}^{l}\lambda_ih_i(x)\\
&x \in \mathbb{R^n}, \lambda \in \mathbb{R^l}
\end{aligned}
L ( x , λ ) = f ( x ) + i = 1 ∑ l λ i h i ( x ) x ∈ R n , λ ∈ R l λ \lambda λ l l l
接着我们需要求解方程:
{ ∂ L ∂ x = 0 h i ( x ) = 0
\left\{
\begin{aligned}
&\frac{\partial L}{\partial x} = 0\\
&h_i(x) = 0
\end{aligned}
\right.
⎩ ⎨ ⎧ ∂ x ∂ L = 0 h i ( x ) = 0
求解出来的结果 x ′ x^\prime x ′
那么为什么会这样呢？这里我们稍加解释，如下图所示，f ( x , y ) f(x, y) f ( x , y ) f ( x ) f(x) f ( x ) g ( x , y ) g(x, y) g ( x , y ) h ( x ) h(x) h ( x )
显然我们的目标就是求出在 f f f g g g 这样的点一定是两个 g g g f f f 。原因很简单：假定我们的目标 x ∗ x^* x ∗
所以我们就有结论:
若 x ∗ x^* x ∗ h h h min f \min f min f f f f h h h x ∗ x^* x ∗
既然 f f f h h h x ∗ x^* x ∗ 在这一点的梯度的方向相同 ，即:∇ f = λ ∇ h , λ ̸ = 0
\nabla f = \lambda \nabla h,\quad \lambda \not = 0
∇ f = λ ∇ h , λ ̸ = 0
稍加整理，我们就可以得出结论，只要 x x x { d f d x + λ d h d x = 0 h ( x ) = 0
\left\{
\begin{aligned}
&\frac{\mathbb{d}f}{\mathbb{d}x} + \lambda\frac{\mathbb{d}h}{\mathbb{d}x} = 0\\
&h(x) = 0
\end{aligned}
\right.
⎩ ⎨ ⎧ d x d f + λ d x d h = 0 h ( x ) = 0 x x x
更详细的解释见这里 。
然而实际生活中我们可能碰到的问题比上面的还要复杂，不仅仅是有等式约束，还可能会有不等式约束。
现在假定 f ( x ) , c i ( x ) , h i ( x ) f(x),\ c_i(x),\ h_i(x) f ( x ) , c i ( x ) , h i ( x ) R n \mathbb{R^n} R n (1) min x ∈ R n f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ]
\large
\begin{aligned}
&\min_{x \in \mathbb{R^n}}{f(x)}\\
&s.t \quad c_i(x) \leqslant 0, i \in [1, k]\\
&\qquad h_j(x) = 0, j \in [1, l]\\
\end{aligned} \tag{1}
x ∈ R n min f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ] ( 1 )
式(1)就是我们实际会遇到的优化问题的基本形式。如何求解这个优化问题也就是这篇文章主要要探讨的。
关于具体如何求解，我们从第三节 再开始讲其。第二节中，我们主要先把一些需要用到的数学概念理清了。
min \min min max \max max
在接下来你会看到一大堆这样:(a) min x f ( x )
\min_{x} f(x) \tag{a}
x min f ( x ) ( a ) (b) max x ∈ D f ( x , λ )
\max_{x \in D}f(x, \lambda) \tag{b}
x ∈ D max f ( x , λ ) ( b ) (c) max λ min x f ( x , λ )
\max_{\lambda}\min_{x}f(x, \lambda) \tag{c}
λ max x min f ( x , λ ) ( c ) min x \min_x min x max x \max_x max x
简而言之，式子(a)的意思是对于函数 f ( x ) f(x) f ( x ) x x x x x x min \min min x ∈ D x \in D x ∈ D x x x
这个符号的含义在函数只有一个自变量 x x x (b) max x ∈ D f ( x , λ )
\max_{x \in D}f(x, \lambda) \tag{b}
x ∈ D max f ( x , λ ) ( b ) f f f x , λ x, \lambda x , λ 固定 λ \lambda λ x x x f f f 。有时候可能会看到这样的格式:g ( λ ) = max x ∈ D f ( x , λ )
g(\lambda) = \max_{x \in D}f(x, \lambda)
g ( λ ) = x ∈ D max f ( x , λ )
g ( λ ) g(\lambda) g ( λ ) λ \lambda λ
当 λ = y \lambda = y λ = y g ( λ ) g(\lambda) g ( λ ) f ( x , λ ) f(x, \lambda) f ( x , λ ) λ = y \lambda = y λ = y x x x f f f
比如:f ( x , y ) = x 2 + y 2 g ( y ) = min x ∈ D f ( x , y ) g ( 4 ) = min x ∈ D f ( x , 4 ) = min x ∈ D ( x 2 + 16 ) = 0 + 16 = 16
\begin{aligned}
&&f(x, y) &= x^2 + y^2\\
&&g(y) &= \min_{x \in D}f(x, y)\\
&&g(4) &= \min_{x \in D}f(x, 4)\\
&& &= \min_{x \in D}(x^2 + 16)\\
&& &= 0 + 16 = 16
\end{aligned}
f ( x , y ) g ( y ) g ( 4 ) = x 2 + y 2 = x ∈ D min f ( x , y ) = x ∈ D min f ( x , 4 ) = x ∈ D min ( x 2 + 1 6 ) = 0 + 1 6 = 1 6
在进一步，有时候 min \min min max \max max v = max λ min x f ( x , λ )
v = \max_{\lambda}\min_{x}f(x, \lambda)
v = λ max x min f ( x , λ ) min x f ( x , λ ) \min_{x}f(x, \lambda) min x f ( x , λ ) λ \lambda λ g ( λ ) g(\lambda) g ( λ ) g g g g ( λ ) = min x f ( x , λ ) v = max λ g ( λ )
\begin{aligned}
&g(\lambda) = \min_{x}f(x, \lambda)\\
&v = \max_\lambda{g(\lambda)}
\end{aligned}
g ( λ ) = x min f ( x , λ ) v = λ max g ( λ )
inf \inf inf sup \sup sup
inf \inf inf sup \sup sup
有函数 f ( x ) = s i n ( x ) x \large f(x) = \frac{sin(x)}{x} f ( x ) = x s i n ( x )
显然 f f f
max f \max{f} max f
sup f \sup{f} sup f
d o m f dom\ f d o m f f f f
⋂ S i \bigcap S_i ⋂ S i S i S_i S i
关于这两个，我有一言请诸位静听:
没错，其实是上凹下凸，这是国际惯例，我们国内的定义(也就是中学教的)是反过来的，我们在此后一律使用国际标准 。
另外关于凸函数和凹函数有性质如下:
若函数 f : R n → R f: \mathbb{R^n} \to \mathbb{R} f : R n → R
∀ x , y ∈ d o m f , ∀ θ ∈ [ 0 , 1 ] f ( θ x + ( 1 − θ ) y ) ⩽ θ f ( x ) + ( 1 − θ ) f ( y )
\begin{aligned}
&\forall x,\ y \in dom\ f,\ \forall \theta \in [0, 1]\\
&f(\theta x + (1 - \theta)y) \leqslant \theta f(x) + (1 - \theta) f(y)
\end{aligned}
∀ x , y ∈ d o m f , ∀ θ ∈ [ 0 , 1 ] f ( θ x + ( 1 − θ ) y ) ⩽ θ f ( x ) + ( 1 − θ ) f ( y )
若函数 f : R n → R f: \mathbb{R^n} \to \mathbb{R} f : R n → R
∀ x , y ∈ d o m f , ∀ θ ∈ [ 0 , 1 ] f ( θ x + ( 1 − θ ) y ) ⩾ θ f ( x ) + ( 1 − θ ) f ( y )
\begin{aligned}
&\forall x,\ y \in dom\ f,\ \forall \theta \in [0, 1]\\
&f(\theta x + (1 - \theta)y) \geqslant \theta f(x) + (1 - \theta) f(y)
\end{aligned}
∀ x , y ∈ d o m f , ∀ θ ∈ [ 0 , 1 ] f ( θ x + ( 1 − θ ) y ) ⩾ θ f ( x ) + ( 1 − θ ) f ( y )
假如有 x ⃗ ∈ R n \vec{x} \in \mathbb{R^n} x ∈ R n b ⃗ ∈ R m \vec{b} \in \mathbb{R^m} b ∈ R m A m × n A_{m\times n} A m × n
x ⃗ → A x ⃗ + b ⃗
\vec x \rightarrow A\vec x + \vec b
x → A x + b
被称为 R n → R m \mathbb{R^n} \rightarrow \mathbb{R^m} R n → R m f ( x ) = A x + b , x ∈ R n
f(x) = Ax + b,\ x\in \mathbb{R^n}
f ( x ) = A x + b , x ∈ R n
比如最简单的:a 1 x 1 + a 2 x 2 + ⋯ + a n x n + b
a_1x_1 + a_2x_2 + \cdots + a_nx_n + b
a 1 x 1 + a 2 x 2 + ⋯ + a n x n + b
仿射函数有一个非常重要的性质，那就是它既凹又凸 ，准确来讲在凹凸函数的那个不等式中，仿射函数是可以取等号的:f ( θ x + ( 1 − θ ) y ) = θ f ( x ) + ( 1 − θ ) f ( y )
f(\theta x + (1 - \theta)y) = \theta f(x) + (1 - \theta) f(y)
f ( θ x + ( 1 − θ ) y ) = θ f ( x ) + ( 1 − θ ) f ( y )
我们在 1.3 节中的式 (1) 给出的式子其实是优化问题的基本形式:min x ∈ R n f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ]
\large
\begin{aligned}
&\min_{x \in \mathbb{R^n}}{f(x)}\\
&s.t \quad c_i(x) \leqslant 0, i \in [1, k]\\
&\qquad h_j(x) = 0, j \in [1, l]\\
\end{aligned}
x ∈ R n min f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ]
而所谓的凸优化，是满足一些特定条件的优化问题，它要求:
f ( x ) f(x) f ( x )
c i ( x ) c_i(x) c i ( x )
h j ( x ) h_j(x) h j ( x )
也就是min x ∈ R n f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] a j x = b j , j ∈ [ 1 , l ]
\large
\begin{aligned}
&\min_{x \in \mathbb{R^n}}{f(x)}\\
&s.t \quad c_i(x) \leqslant 0, i \in [1, k]\\
&\qquad a_jx = b_j, j \in [1, l]\\
\end{aligned}
x ∈ R n min f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] a j x = b j , j ∈ [ 1 , l ]
凸优化有一个重要的性质：任意位置的局部最优解同时也是全局最优解 。
OK，做了一大堆铺垫，我们终于要开始正式将拉格朗日对偶了。
首先来回忆一下我们的原问题 (Primal Problem):(1) min x ∈ R n f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ]
\large
\begin{aligned}
&\min_{x \in \mathbb{R^n}}{f(x)}\\
&s.t \quad c_i(x) \leqslant 0, i \in [1, k]\\
&\qquad h_j(x) = 0, j \in [1, l]\\
\end{aligned} \tag{1}
x ∈ R n min f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ] ( 1 )
首先我们做两个约定:
我们不假定原函数 f f f ，也就是 f f f
记问题的定义域 D = ( d o m f ) ∩ ( ⋂ i = 1 k c i ) ∩ ( ⋂ i = 1 l h i ) D = (dom\ f)\cap(\bigcap_{i=1}^k{c_i})\cap (\bigcap_{i=1}^l{h_i}) D = ( d o m f ) ∩ ( ⋂ i = 1 k c i ) ∩ ( ⋂ i = 1 l h i )
D ≠ ∅ D \neq \empty D ̸ = ∅ 我们约定最终求出来的最优结果用 p ∗ p^* p ∗
对于原问题(1)我们通常用拉格朗日对偶的方式来求解。啥是对偶？对偶说白了就是实质相同但从不同角度提出不同提法的一对问题 。有时候原问题 (Primal Problem) 不太好解，但是对偶问题 (Dual Problem) 却很好解，我们就可以通过求解对偶问题来迂回地解答原问题。
在这里我们用的是拉格朗日对偶的方法来解决，既然我们说用对偶的方法的原因在于原问题不好解，那么这里也是如此吗？
当然了。
首先我们来看看原问题有什么难的地方:
约束条件太多k + l k + l k + l
原问题凹凸性不明确f f f
那么它的拉格朗日对偶问题有什么优点呢？
只有一个约束
拉格朗日对偶问题一定是凹的
这里先做一个感性的认识，细节方面接下来慢慢说。
早前我们说过，对于等式约束问题可以用构建拉格朗日函数的方法来求解。这里也一样，我们可以为原问题构建一个广义拉格朗日函数 L \mathcal{L} L
(2) L : R n × R k × R l → R L ( x , λ , μ ) = f ( x ) + ∑ i = 1 k λ i c i ( x ) + ∑ j = 1 l μ j h j ( x ) x ⃗ ∈ R n , λ ⃗ ∈ R k , μ ⃗ ∈ R l
\begin{aligned}
&\mathcal{L}: \mathbb{R^n}\times \mathbb{R^k}\times \mathbb{R^l} \rightarrow R\\
&\mathcal{L}(x, \lambda, \mu) = f(x) + \sum_{i = 1}^{k}{\lambda_ic_i(x)} + \sum_{j = 1}^{l}{\mu_jh_j(x)}\\
&\vec x \in \mathbb{R^n},\ \vec \lambda \in \mathbb{R^k},\ \vec \mu \in \mathbb{R^l}
\end{aligned} \tag{2}
L : R n × R k × R l → R L ( x , λ , μ ) = f ( x ) + i = 1 ∑ k λ i c i ( x ) + j = 1 ∑ l μ j h j ( x ) x ∈ R n , λ ∈ R k , μ ∈ R l ( 2 ) λ ⃗ \vec \lambda λ μ ⃗ \vec \mu μ
有了这个广义拉格朗日函数，现在我们分别可以定义另外对偶函数 g g g
g g g
我们可以根据 L \mathcal{L} L g ( λ , μ ) g(\lambda, \mu) g ( λ , μ )
(3) g ( λ , μ ) = inf x ∈ D L ( x , λ , μ ) = inf x ∈ D ( f ( x ) + ∑ i = 1 k λ i c i ( x ) + ∑ j = 1 l μ j h j ( x ) ) λ ⩾ 0
\begin{aligned}
&&g(\lambda, \mu) &= \inf_{x\in D}{\mathcal{L}(x, \lambda, \mu)}\\
&&\ &=\inf_{x\in D}{\big (f(x) + \sum_{i = 1}^{k}{\lambda_ic_i(x)} + \sum_{j = 1}^{l}{\mu_jh_j(x)}\big )}\\
&&\lambda \geqslant 0
\end{aligned} \tag{3}
g ( λ , μ ) λ ⩾ 0 = x ∈ D inf L ( x , λ , μ ) = x ∈ D inf ( f ( x ) + i = 1 ∑ k λ i c i ( x ) + j = 1 ∑ l μ j h j ( x ) ) ( 3 )
注意到 λ ⩾ 0 \lambda \geqslant 0 λ ⩾ 0
这个对偶函数 g g g 它一定是一个凹函数 ，我们可以证明一下。
首先我们明确一个凹函数具有性质:f ( θ x + ( 1 − θ ) y ) ⩾ θ f ( x ) + ( 1 − θ ) f ( y )
f(\theta x + (1 - \theta)y) \geqslant \theta f(x) + (1 - \theta) f(y)
f ( θ x + ( 1 − θ ) y ) ⩾ θ f ( x ) + ( 1 − θ ) f ( y ) g g g
我们首先记:g ( λ , μ ) = inf x ∈ D { L ( x 1 , λ , μ ) , L ( x 2 , λ , μ ) , ⋯  , L ( x n , λ , μ ) } , x → + ∞
g(\lambda, \mu) = \inf_{x\in D}\{\mathcal{L}(x_1, \lambda, \mu), \mathcal{L}(x_2, \lambda, \mu), \cdots, \mathcal{L}(x_n, \lambda, \mu)\}, x\to +\infty
g ( λ , μ ) = x ∈ D inf { L ( x 1 , λ , μ ) , L ( x 2 , λ , μ ) , ⋯ , L ( x n , λ , μ ) } , x → + ∞
这个好理解，我是就是把 g g g
简记:γ = ( λ , μ ) , g ( γ ) = g ( λ , μ )
\gamma = (\lambda, \mu),\ g(\gamma) = g(\lambda, \mu)
γ = ( λ , μ ) , g ( γ ) = g ( λ , μ )
证明过程如下:g ( θ γ 1 + ( 1 − θ ) γ 2 ) = inf { L ( x 1 , θ γ 1 + ( 1 − θ ) γ 2 ) , L ( x 2 , θ γ 1 + ( 1 − θ ) γ 2 ) , ⋯  , L ( x n , θ γ 1 + ( 1 − θ ) γ 2 ) } ⩾ inf { θ L ( x 1 , γ 1 ) + ( 1 − θ ) L ( x 1 , γ 2 ) , ⋯  , θ L ( x n , γ 1 ) + ( 1 − θ ) L ( x n , γ 2 ) } ⩾ θ inf { L ( x 1 , γ 1 ) , L ( x 2 , γ 1 ) , ⋯  , L ( x n , γ 1 ) } + ( 1 − θ ) inf { L ( x 1 , γ 2 ) , L ( x 2 , γ 2 ) , ⋯  , L ( x n , γ 2 ) } = θ g ( γ 1 ) + ( 1 − θ ) g ( γ 2 )
\begin{aligned}
&g(\theta\gamma_1 + (1 - \theta)\gamma_2)\\
&= \inf\{\mathcal{L}(x_1, \theta\gamma_1 + (1 - \theta)\gamma_2),\ \mathcal{L}(x_2, \theta\gamma_1 + (1 - \theta)\gamma_2),\ \cdots,\ \mathcal{L}(x_n, \theta\gamma_1 + (1 - \theta)\gamma_2)\}\\
&\geqslant \inf\{\theta\mathcal{L}(x_1, \gamma_1) + (1-\theta)\mathcal{L}(x_1, \gamma_2),\ \cdots,\ \theta\mathcal{L}(x_n, \gamma_1) + (1-\theta)\mathcal{L}(x_n, \gamma_2)\}\\
&\geqslant\theta\inf\{\mathcal{L}(x_1, \gamma_1),\ \mathcal{L}(x_2, \gamma_1), \cdots,\ \mathcal{L}(x_n, \gamma_1)\} + (1 - \theta)\inf\{\mathcal{L}(x_1, \gamma_2),\ \mathcal{L}(x_2, \gamma_2), \cdots,\ \mathcal{L}(x_n, \gamma_2)\}\\
&=\theta g(\gamma_1) + (1 - \theta)g(\gamma_2)
\end{aligned}
g ( θ γ 1 + ( 1 − θ ) γ 2 ) = inf { L ( x 1 , θ γ 1 + ( 1 − θ ) γ 2 ) , L ( x 2 , θ γ 1 + ( 1 − θ ) γ 2 ) , ⋯ , L ( x n , θ γ 1 + ( 1 − θ ) γ 2 ) } ⩾ inf { θ L ( x 1 , γ 1 ) + ( 1 − θ ) L ( x 1 , γ 2 ) , ⋯ , θ L ( x n , γ 1 ) + ( 1 − θ ) L ( x n , γ 2 ) } ⩾ θ inf { L ( x 1 , γ 1 ) , L ( x 2 , γ 1 ) , ⋯ , L ( x n , γ 1 ) } + ( 1 − θ ) inf { L ( x 1 , γ 2 ) , L ( x 2 , γ 2 ) , ⋯ , L ( x n , γ 2 ) } = θ g ( γ 1 ) + ( 1 − θ ) g ( γ 2 )
来逐行解释一下:
第一行：之前讲过了，略
第二行L ( x i , γ ) \mathcal{L}(x_i, \gamma) L ( x i , γ ) x i x_i x i 已经固定了 ，∴ f ( x ) , c i ( x ) , h i ( x ) \therefore f(x),\ c_i(x),\ h_i(x) ∴ f ( x ) , c i ( x ) , h i ( x ) r , p , q r, p, q r , p , q L ( x i , γ ) = ∑ λ i p i + ∑ μ j q j + r
\mathcal{L}(x_i, \gamma) = \sum{\lambda_i p_i} + \sum{\mu_j q_j} + r
L ( x i , γ ) = ∑ λ i p i + ∑ μ j q j + r L \mathcal{L} L L ( x n , θ γ 1 + ( 1 − θ ) γ 2 ) ⩾ θ L ( x n , γ 1 ) + ( 1 − θ ) L ( x n , γ 2 )
\mathcal{L}(x_n, \theta\gamma_1 + (1 - \theta)\gamma_2) \geqslant \theta \mathcal{L}(x_n, \gamma_1) + (1 - \theta) \mathcal{L}(x_n, \gamma_2)
L ( x n , θ γ 1 + ( 1 − θ ) γ 2 ) ⩾ θ L ( x n , γ 1 ) + ( 1 − θ ) L ( x n , γ 2 )
第三行m i n { a i + b i } ⩾ m i n { a } + m i n { b }
min\{a_i + b_i\} \geqslant min\{a\} + min\{b\}
m i n { a i + b i } ⩾ m i n { a } + m i n { b }
总结: 不管原函数 f f f g g g
我们之所以需要这么一个对偶函数是因为 g g g
Give the lower bound on optimal value (p ∗ p^* p ∗
什么意思呢？其实这是 Dual Function 一个很重要的性质:(4) ∀ λ ⩾ 0 ⇒ g ( λ , μ ) ⩽ p ∗
\forall \lambda \geqslant 0 \Rightarrow g(\lambda, \mu) \leqslant p^* \tag{4}
∀ λ ⩾ 0 ⇒ g ( λ , μ ) ⩽ p ∗ ( 4 ) λ \lambda λ g g g p ∗ p^* p ∗
要证明这个定理并不难，我们首先假设 x ^ ∈ D \hat x \in D x ^ ∈ D
∵ c i ( x ^ ) ⩽ 0 , h i ( x ^ ) = 0 ∴ λ i c i ⩽ 0 , μ i h i = 0 ∴ L ( x ^ , λ , μ ) = f ( x ) + ∑ i = 1 k λ i c i ( x ^ ) + ∑ j = 1 l μ j h j ( x ^ ) ⩽ f ( x ) Meanwhile g ( λ , μ ) = inf L , p ∗ = min f ∴ g ( λ , μ ) ⩽ L ⩽ p ∗
\begin{aligned}
& \because c_i(\hat x) \leqslant 0,\ h_i(\hat x) = 0\\
& \therefore \lambda_ic_i \leqslant 0, \mu_ih_i = 0\\
& \therefore \mathcal{L}(\hat x, \lambda, \mu) = f(x) + \sum_{i = 1}^{k}{\lambda_ic_i(\hat x)} + \sum_{j = 1}^{l}{\mu_jh_j(\hat x)} \leqslant f(x)\\
& \text{Meanwhile}\quad g(\lambda, \mu) = \inf{\mathcal{L}},\quad p^* = \min f\\
& \therefore g(\lambda, \mu) \leqslant \mathcal{L} \leqslant p^*
\end{aligned}
∵ c i ( x ^ ) ⩽ 0 , h i ( x ^ ) = 0 ∴ λ i c i ⩽ 0 , μ i h i = 0 ∴ L ( x ^ , λ , μ ) = f ( x ) + i = 1 ∑ k λ i c i ( x ^ ) + j = 1 ∑ l μ j h j ( x ^ ) ⩽ f ( x ) Meanwhile g ( λ , μ ) = inf L , p ∗ = min f ∴ g ( λ , μ ) ⩽ L ⩽ p ∗
这给了我们一个重要的启示，无论如何，p ∗ p^* p ∗ max g ( λ , μ ) \max{g(\lambda, \mu)} max g ( λ , μ )
在此之前，我们讲了原问题，讲了广义拉格朗日函数和拉格朗日对偶函数，又讲了这两个之间的关系。那么这有什么用呢？
用处当然很大啦！现在我们不妨这么一想，既然 Lagrange 对偶函数给出了最优解 p ∗ p^* p ∗
What is the best lower bound that can be obtained from lagrange dual function?
啥意思？我们来捋一捋:
首先我们明确一件事，我们的目的是找到最优解 p ∗ p^* p ∗
有时候 p ∗ p^* p ∗ 给出一个尽可能地逼近 p ∗ p^* p ∗
既然我们已经知道了 g g g
答案是: max g ( λ , μ ) \max g(\lambda, \mu) max g ( λ , μ ) s . t λ ⩾ 0 s.t\ \lambda \geqslant 0 s . t λ ⩾ 0
明白了这一点，我们终于可以介绍拉格朗日对偶问题了。
首先再次回顾一下原问题。(1) Primal Problem min x ∈ R n f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ]
\large
\text{Primal Problem}\\
\begin{aligned}
\\
&\min_{x \in \mathbb{R^n}}{f(x)}\\
&s.t \quad c_i(x) \leqslant 0, i \in [1, k]\\
&\qquad h_j(x) = 0, j \in [1, l]\\
\end{aligned} \tag{1}
Primal Problem x ∈ R n min f ( x ) s . t c i ( x ) ⩽ 0 , i ∈ [ 1 , k ] h j ( x ) = 0 , j ∈ [ 1 , l ] ( 1 ) (5) Lagrange Dual Problem max λ , μ g ( λ , μ ) = max λ , μ inf x ∈ D L ( x , λ , μ ) s . t λ i ⩾ 0 , i = 1 , 2 , … , k
\large
\text{Lagrange Dual Problem}\\
\begin{aligned}
\\
&\max_{\lambda, \mu}g(\lambda, \mu) = \max_{\lambda, \mu}\inf_{x\in D}{\mathcal{L}(x, \lambda, \mu)}\\
&s.t \quad \lambda_i \geqslant 0,\ i = 1, 2,\dots, k\\
\end{aligned} \tag{5}
Lagrange Dual Problem λ , μ max g ( λ , μ ) = λ , μ max x ∈ D inf L ( x , λ , μ ) s . t λ i ⩾ 0 , i = 1 , 2 , … , k ( 5 )
参考上面那幅图，其实这个所谓的对偶问题在干什么已经很清楚了。我们把问题 (1) 的结果令为 p ∗ p^* p ∗ d ∗ d^* d ∗
现在回顾一下之前说的求解对偶问题的好处 ，我们再来看看为什么需要拉格朗日对偶。
首先是问题 (1) 有哪些 annoying 的地方:
原问题的约束太多了，又是等式又是不等式
问题 (1) 不一定是一个凸优化问题，所以即便找到了貌似是 p ∗ p^* p ∗
那 Lagrange 对偶问题 (5) 就好一些吗？还真是，我们来康康:
约束少了，这是很明显的，少了 l l l k k k
最最重要的，问题 (5) 一定是一个凸优化问题 ，所以很多凸优化的手段全可以用上了
总结一下就是:
我们希望求 p ∗ p^* p ∗ p ∗ p^* p ∗ d ∗ d^* d ∗ d ∗ ⩽ p ∗ d^* \leqslant p^* d ∗ ⩽ p ∗ d ∗ d^* d ∗ p ∗ p^* p ∗ p ∗ p^* p ∗ d ∗ = p ∗ d^* = p^* d ∗ = p ∗
d ∗ = p ∗ d^* = p^* d ∗ = p ∗
所谓强弱对偶，指的是 Lagrange 对偶问题的一种性质，关于弱对偶我们其实在前面已经谈到了。
(6) d ∗ ⩽ p ∗
d^* \leqslant p^* \tag{6}
d ∗ ⩽ p ∗ ( 6 )
即便原文题不是凸问题，上述的不等式也成立，这就是所谓的弱对偶性 (Weak Dulity)。这样的性质即便是 d ∗ d^* d ∗ p ∗ p^* p ∗
如果 p ∗ = − ∞ p^* = -\infty p ∗ = − ∞ d ∗ = − ∞ d^* = -\infty d ∗ = − ∞
如果 d ∗ = + ∞ d^* = +\infty d ∗ = + ∞ p ∗ = + ∞ p^* = +\infty p ∗ = + ∞
我们还把 p ∗ − d ∗ p^* - d^* p ∗ − d ∗ 最优对偶间隙 (Optimal Duality Gap)，这个值必然非负。
对于式子 (6) 还有一种很特殊的情况:
(7) d ∗ = p ∗
d^* = p^* \tag{7}
d ∗ = p ∗ ( 7 )
这种情况，我们称之为强对偶性 (Strong Duality)。
之所以称之为“强”对偶，正是因为这种性质相对于“弱”对偶而言对我们的意义更加重大。很显然，当我们待求解的问题是强对偶的话，那就意味着我们通过对偶问题求的的解就不再仅仅是原问题解的一个下界了，而是 p ∗ p^* p ∗
如果满足强对偶，那只要我们求出了 d ∗ d^* d ∗ p ∗ p^* p ∗
显然，强对偶并不是什么时候都成立的，必须要满足一定的条件才会有强对偶这种东西。
下一节，我们着重讲解这些条件是什么 (充分条件、必要条件)。
首先要明确一件事情：使满足强对偶的条件有很多种 ，我们这里只介绍最基本的。
如果:
原问题是凸优化
满足 Slater 条件
则一定满足强对偶充分条件
下面具体解释一下含义。
首先是第 1 点，在 2.4 节中我们讲到过，这意味着:
f ( x ) f(x) f ( x )
c i ( x ) c_i(x) c i ( x )
h j ( x ) h_j(x) h j ( x )
再来看看第 2 点，所谓的 Slater 条件。严格的 Slater 条件表述如下:(8) ∃ x ∈ D c i ( x ) < 0 , i ∈ [ 1 , k ] A x = b
\begin{aligned}
&\exists x \in D\\
&c_i(x) < 0, i \in [1,k]\\
&Ax = b
\end{aligned} \tag{8}
∃ x ∈ D c i ( x ) < 0 , i ∈ [ 1 , k ] A x = b ( 8 ) A x = b Ax = b A x = b a j x = b j a_jx=b_j a j x = b j c i c_i c i 严格可行 的，因为不等式约束要求严格成立。
之所以称上述的 Slater 条件是严格的，是因为 Slater 还有一个弱化的版本。
(9) 若 c i ( x ) 是仿射函数 , i = [ 1 , p ] & p ⩽ k 则弱化的 Slater 条件为: ∃ x ∈ D c i ( x ) ⩽ 0 , i ∈ [ 1 , p ] c i ( x ) < 0 , i ∈ [ p + 1 , k ] A x = b
\begin{aligned}
&\text{若}c_i(x)\text{是仿射函数},\ i = [1, p] \And p \leqslant k\\
&\text{则弱化的 Slater 条件为:}\\
&\exists x \in D\\
&c_i(x) \leqslant 0, i \in [1,p]\\
&c_i(x) < 0, i \in [p+1, k]\\
&Ax = b
\end{aligned} \tag{9}
若 c i ( x ) 是仿射函数 , i = [ 1 , p ] & p ⩽ k 则弱化的 Slater 条件为 : ∃ x ∈ D c i ( x ) ⩽ 0 , i ∈ [ 1 , p ] c i ( x ) < 0 , i ∈ [ p + 1 , k ] A x = b ( 9 )
任意满足:
凸优化
强或弱 Slater 条件
的优化问题同样满足强对偶性 (充分条件)。
有必要明确一些很重要的点。
首先是 KKT 条件实际上应该分为两种情况讨论:
Case 1: 原问题为非凸问题情况下的 KKT
Case 2: 原问题为凸问题情况下的 KKT
为什么要分两点来讨论？因为在两种情况下，KKT 条件作为一个“条件”的充分性和必要性是不同的，自然用法也不同。
再有一个问题是，无论哪种情况，KKT 都是着眼于“最优解”这个议题进行讨论的。
下面分两种情况讨论。
当原问题并非凸优化(或者不清楚、不关心是不是凸优化)时，KKT 条件是一种用来描述强对偶情况下最优解性质 的条件点 一定满足 KKT 条件；KKT 条件是强对偶一个必要条件 ，但无法作为充分条件来使用
我们首先给出 KKT 条件的具体数学描述，然后逐行解释。
假设:
原问题中的函数均可微
强对偶成立
x ∗ x^* x ∗ ( λ ∗ , μ ∗ ) (\lambda^*, \mu^*) ( λ ∗ , μ ∗ )
则:c i ( x ∗ ) ⩽ 0 i = 1 , … , k h i ( x ∗ ) = 0 i = 1 , … , l λ i ∗ ⩾ 0 i = 1 , … , k λ i ∗ c i ( x ∗ ) = 0 i = 1 , … , k ∇ f ( x ∗ ) + ∑ i = 1 k λ i ∗ ∇ c i ( x ∗ ) + ∑ i = 1 l μ i ∗ ∇ h i ( x ∗ ) = 0
\begin{aligned}
&c_i(x^*) \leqslant 0 &i = 1, \dots, k\\
&h_i(x^*) = 0 &i = 1, \dots, l\\
&\lambda_i^* \geqslant 0 &i = 1, \dots, k\\
&\lambda_i^*c_i(x^*) = 0 &i = 1, \dots, k\\
&\nabla f(x^*) + \sum_{i=1}^{k}\lambda_i^*\nabla c_i(x^*) + \sum_{i=1}^{l}\mu_i^*\nabla h_i(x^*) = 0
\end{aligned}
c i ( x ∗ ) ⩽ 0 h i ( x ∗ ) = 0 λ i ∗ ⩾ 0 λ i ∗ c i ( x ∗ ) = 0 ∇ f ( x ∗ ) + i = 1 ∑ k λ i ∗ ∇ c i ( x ∗ ) + i = 1 ∑ l μ i ∗ ∇ h i ( x ∗ ) = 0 i = 1 , … , k i = 1 , … , l i = 1 , … , k i = 1 , … , k
这就是 KKT 条件了，第一行和第二行是原问题的约束，必须遵守；第三行则是弱对偶的必要条件。最后一行，我们知道，既然 x ∗ x^* x ∗ L \mathcal{L} L x ∗ x^* x ∗
现在难点主要在第四行，其实第四行的不等式是一个被称为“互补松弛条件”的东西。我们做一个简单的证明。
首先我们知道f ( x ∗ ) = g ( λ ∗ , μ ∗ ) = inf x L ( x ∗ , λ ∗ , μ ∗ )
\begin{aligned}
&&f(x^*) &= g(\lambda^*, \mu^*)\\
&& &= \inf_{x}{\mathcal{L}(x^*, \lambda^*, \mu^*)}\\
\end{aligned}
f ( x ∗ ) = g ( λ ∗ , μ ∗ ) = x inf L ( x ∗ , λ ∗ , μ ∗ ) f ( x ∗ ) ⩽ L ( x ∗ , λ ∗ , μ ∗ ) = f ( x ∗ ) + ∑ i = 1 k λ i ∗ c i ( x ∗ ) + ∑ i = 1 l μ i ∗ h i ( x ∗ )
\begin{aligned}
&&f(x^*) &\leqslant \mathcal{L}(x^*, \lambda^*, \mu^*)\\
&& &= f(x^*) + \sum_{i=1}^{k}\lambda_i^*c_i(x^*) + \sum_{i=1}^{l}\mu_i^*h_i(x^*)
\end{aligned}
f ( x ∗ ) ⩽ L ( x ∗ , λ ∗ , μ ∗ ) = f ( x ∗ ) + i = 1 ∑ k λ i ∗ c i ( x ∗ ) + i = 1 ∑ l μ i ∗ h i ( x ∗ ) λ ⩾ 0 \lambda \geqslant 0 λ ⩾ 0 c i ( x ) ⩽ 0 c_i(x) \leqslant 0 c i ( x ) ⩽ 0 h i = 0 h_i = 0 h i = 0 f ( x ∗ ) + ∑ i = 1 k λ i ∗ c i ( x ∗ ) + ∑ i = 1 l μ i ∗ h i ( x ∗ ) ⩽ f ( x ∗ )
f(x^*) + \sum_{i=1}^{k}\lambda_i^*c_i(x^*) + \sum_{i=1}^{l}\mu_i^*h_i(x^*) \leqslant f(x^*)
f ( x ∗ ) + i = 1 ∑ k λ i ∗ c i ( x ∗ ) + i = 1 ∑ l μ i ∗ h i ( x ∗ ) ⩽ f ( x ∗ ) f ( x ∗ ) = g ( λ ∗ , μ ∗ ) = inf x f ( x ∗ ) + ∑ i = 1 k λ i ∗ c i ( x ∗ ) + ∑ i = 1 l μ i ∗ h i ( x ∗ ) = f ( x ∗ ) + ∑ i = 1 k λ i ∗ c i ( x ∗ ) + ∑ i = 1 l μ i ∗ h i ( x ∗ ) = f ( x ∗ )
\begin{aligned}
&&f(x^*) &= g(\lambda^*, \mu^*)\\
&& &= \inf_{x}{f(x^*) + \sum_{i=1}^{k}\lambda_i^*c_i(x^*) + \sum_{i=1}^{l}\mu_i^*h_i(x^*)}\\
&& &= f(x^*) + \sum_{i=1}^{k}\lambda_i^*c_i(x^*) + \sum_{i=1}^{l}\mu_i^*h_i(x^*)\\
&& &= f(x^*)
\end{aligned}
f ( x ∗ ) = g ( λ ∗ , μ ∗ ) = x inf f ( x ∗ ) + i = 1 ∑ k λ i ∗ c i ( x ∗ ) + i = 1 ∑ l μ i ∗ h i ( x ∗ ) = f ( x ∗ ) + i = 1 ∑ k λ i ∗ c i ( x ∗ ) + i = 1 ∑ l μ i ∗ h i ( x ∗ ) = f ( x ∗ ) λ i c i ⩽ 0 \lambda_ic_i \leqslant 0 λ i c i ⩽ 0 λ i c i ( x ) = 0
\lambda_ic_i(x) = 0
λ i c i ( x ) = 0
把这几个条件一股脑叠加在一起，就构成了 KKT 条件。对于目标函数和约束函数可微的优化问题，如果强对偶成立，则任意一对原问题的最优解和对偶问题的最优解满足 KKT 条件。
当原问题为凸优化时，KKT 条件在非凸的基础上有多了找到最优点的功能
也就是说:
若原问题是Convex的
∃ x ^ , λ ^ , μ ^ \exists \hat x, \hat \lambda, \hat \mu ∃ x ^ , λ ^ , μ ^ c i ( x ^ ) ⩽ 0 i = 1 , … , k h i ( x ^ ) = 0 i = 1 , … , l λ ^ i ⩾ 0 i = 1 , … , k λ ^ i c i ( x ^ ) = 0 i = 1 , … , k ∇ f ( x ^ ) + ∑ i = 1 k λ ^ i ∇ c i ( x ^ ) + ∑ i = 1 l μ ^ i ∇ h i ( x ^ ) = 0
\begin{aligned}
&c_i(\hat x) \leqslant 0 &i = 1, \dots, k\\
&h_i(\hat x) = 0 &i = 1, \dots, l\\
&\hat \lambda_i \geqslant 0 &i = 1, \dots, k\\
&\hat \lambda_i c_i(\hat x) = 0 &i = 1, \dots, k\\
&\nabla f(\hat x) + \sum_{i=1}^{k}\hat \lambda_i \nabla c_i(\hat x) + \sum_{i=1}^{l}\hat\mu_i \nabla h_i(\hat x) = 0
\end{aligned}
c i ( x ^ ) ⩽ 0 h i ( x ^ ) = 0 λ ^ i ⩾ 0 λ ^ i c i ( x ^ ) = 0 ∇ f ( x ^ ) + i = 1 ∑ k λ ^ i ∇ c i ( x ^ ) + i = 1 ∑ l μ ^ i ∇ h i ( x ^ ) = 0 i = 1 , … , k i = 1 , … , l i = 1 , … , k i = 1 , … , k
那么 x ^ \hat x x ^ ( λ ^ , μ ^ ) (\hat \lambda, \hat \mu) ( λ ^ , μ ^ )
对于任意问题⇒ \Rightarrow ⇒
对于 Convex + 可微 的问题⇒ \Rightarrow ⇒
Convex + Slater ⇒ \Rightarrow ⇒
本文应该是我写过的最麻烦的一篇文章了，一大堆latex公式敲起来简直酸爽。其实这篇文章的写作动机是我自己太菜了，别人的文章一大堆基础知识看不懂，什么仿射函数什么凸优化，还得自己一个一个去查，所以干脆自己写了一份阅读难度比较低(自以为)的博文。
