在数学中的最优化问题中，拉格朗日乘数法是一种寻找多元函数在其变量受到一个或多个条件的约束时的极值的方法，这里的条件约束是等式约束，不等式约束使用KKT解决。这种方法可以将一个有 n n n n + k n+k n + k
比如，要求f ( x , y ) f(x,y) f ( x , y ) g ( x , y ) = c g(x,y)=c g ( x , y ) = c λ \lambda λ
L ( x , y , λ ) = f ( x , y ) + λ ⋅ ( g ( x , y ) − c ) \mathcal{L}(x,y,\lambda) = f(x,y)+\lambda\cdot(g(x,y)-c) L ( x , y , λ ) = f ( x , y ) + λ ⋅ ( g ( x , y ) − c )
更一般地，对含 n n n k k k
L ( x 1 , … , x n , λ 1 , … , λ k ) = f ( x 1 , … , x n ) − ∑ i = 1 k λ i g i ( x 1 , … , x n ) \mathcal{L}(x_1,\dots,x_n,\lambda_1,\dots,\lambda_k) = f(x_1,\dots,x_n)-\sum\limits_{i=1}^k\lambda_ig_i(x_1,\dots,x_n) L ( x 1 , … , x n , λ 1 , … , λ k ) = f ( x 1 , … , x n ) − i = 1 ∑ k λ i g i ( x 1 , … , x n )
假设有函数 f ( x , y ) f(x,y) f ( x , y ) g ( x , y ) = c g(x,y)=c g ( x , y ) = c c c c d n d_n d n f ( x , y ) = d n f(x,y)=d_n f ( x , y ) = d n g g g g ( x , y ) = c g(x,y) = c g ( x , y ) = c g = c g = c g = c f f f g g g g = c g = c g = c f f f f ( x , y ) = d n f(x,y)=d_n f ( x , y ) = d n d n d_n d n g = c g = c g = c f ( x , y ) = d n f(x,y)=d_n f ( x , y ) = d n g = c g = c g = c f ( x , y ) = d n f(x,y) = d_n f ( x , y ) = d n
用向量的形式来表达的话，我们说相切的性质在此意味着 f f f g g g λ \lambda λ
∇ [ f ( x , y ) + λ ( g ( x , y ) − c ) ] = 0 \nabla[f(x,y)+\lambda(g(x,y)-c)] = 0 ∇ [ f ( x , y ) + λ ( g ( x , y ) − c )] = 0
一旦求出 λ \lambda λ
F ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c ) F(x,y,\lambda) = f(x,y)+\lambda(g(x,y)-c) F ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c )
新方程 F ( x , y , λ ) F(x,y,\lambda) F ( x , y , λ ) f ( x , y ) f(x,y) f ( x , y ) F ( x , y , λ ) F(x,y,\lambda) F ( x , y , λ ) g ( x , y ) − c g(x,y)-c g ( x , y ) − c
求 f ( x , y ) = x 2 y f(x,y)=x^2y f ( x , y ) = x 2 y x 2 + y 2 = 1 x^2+y^2 = 1 x 2 + y 2 = 1
因为只有一个限制条件，我们只需要用一个乘数 λ \lambda λ
Φ ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c ) = x 2 y + λ ( ( x 2 + y 2 ) − 1 ) \Phi(x,y,\lambda) = f(x,y)+\lambda(g(x,y)-c) = x^2y+\lambda((x^2+y^2)-1) Φ ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c ) = x 2 y + λ (( x 2 + y 2 ) − 1 )
将所有 Φ \Phi Φ
2 x y + 2 λ x = 0 2xy+2\lambda x = 0 2 x y + 2 λ x = 0
x 2 + 2 λ y = 0 x^2+2\lambda y =0 x 2 + 2 λ y = 0
x 2 + y 2 − 1 = 0 x^2+y^2-1 = 0 x 2 + y 2 − 1 = 0
现在考虑不等式 g ( x ) ≤ 0 g(x)\leq 0 g ( x ) ≤ 0 g ( x ) < 0 g(x)<0 g ( x ) < 0 g ( x ) = 0 g(x) = 0 g ( x ) = 0
1、对于 g ( x ) < 0 g(x)<0 g ( x ) < 0 g ( x ) ≤ 0 g(x)\leq0 g ( x ) ≤ 0 ∇ f ( x ) = 0 \nabla f(x) = 0 ∇ f ( x ) = 0 λ \lambda λ ∇ x L ( x , λ ) \nabla_x\mathcal{L}(x,\lambda) ∇ x L ( x , λ )
2、 g ( x ) = 0 g(x) =0 g ( x ) = 0 ∇ f ( x ∗ ) \nabla f(x^*) ∇ f ( x ∗ ) ∇ g ( x ∗ ) \nabla g(x^*) ∇ g ( x ∗ ) λ > 0 \lambda>0 λ > 0 λ < 0 \lambda<0 λ < 0 g ( x ) > 0 g(x)>0 g ( x ) > 0 ∇ f ( x ∗ ) + λ ∇ g ( x ∗ ) = 0 \nabla f(x^*) +\lambda\nabla g(x^*) =0 ∇ f ( x ∗ ) + λ ∇ g ( x ∗ ) = 0 λ g ( x ) = 0 \lambda g(x)=0 λ g ( x ) = 0
因此，在约束 g ( x ) ≤ 0 g(x)\leq 0 g ( x ) ≤ 0 f ( x ) f(x) f ( x ) L ( x , λ ) = f ( x ) + λ g ( x ) \mathcal{L}(x,\lambda)=f(x)+\lambda g(x) L ( x , λ ) = f ( x ) + λ g ( x )
{ h ( x ) = 0 g ( x ) ≤ 0 λ ≥ 0 λ g ( x ) = 0 \begin{cases}h(x)=0\\g(x)\leq0\\ \lambda\geq 0 \\ \lambda g(x) = 0\end{cases} ⎩ ⎨ ⎧ h ( x ) = 0 g ( x ) ≤ 0 λ ≥ 0 λ g ( x ) = 0
max x f ( x ) s . t . h j ( x ) = 0 , j = 1 , … , q ; g i ( x ) ≤ 0 , i = 1 , … , p \max_xf(x)\ \ \ s.t.\ \ \ h_j(x)=0,j=1,\dots,q\ ;\ \ g_i(x)\leq0,i=1,\dots,p max x f ( x ) s . t . h j ( x ) = 0 , j = 1 , … , q ; g i ( x ) ≤ 0 , i = 1 , … , p
也就是说，自变量 x x x n n n f f f x ∗ x^* x ∗
∇ f ( x ∗ ) = ∑ j λ j ∇ h j ( x ∗ ) + ∑ i μ i ∇ g j ( x ∗ ) μ i ≥ 0 , μ i g i ( x ∗ ) = 0 \nabla f(x^*)=\sum\limits_j\lambda_j\nabla h_j(x^*)+\sum\limits_i\mu_i\nabla g_j(x^*)\ \ \ \ \mu_i\geq0,\ \mu_ig_i(x^*) = 0 ∇ f ( x ∗ ) = j ∑ λ j ∇ h j ( x ∗ ) + i ∑ μ i ∇ g j ( x ∗ ) μ i ≥ 0 , μ i g i ( x ∗ ) = 0
简单说，就是在极值处， f f f h j h_j h j g i g_i g i λ j \lambda_j λ j μ i \mu_i μ i g i ( x ∗ ) g_i(x^*) g i ( x ∗ ) 0 0 0 μ i \mu_i μ i 0 0 0 x ∗ x^* x ∗ g i = 0 g_i=0 g i = 0 g i g_i g i
给定一个优化问题，我们把满足所有约束条件的n维空间区域称为可行域。从可行域中的每一个点 x x x v v v v v v F ( x ) F(x) F ( x ) x x x x ∗ x^* x ∗ F ( x ∗ ) F(x^*) F ( x ∗ ) x ∗ x^* x ∗ F ( x ∗ ) F(x^*) F ( x ∗ ) x ∗ x^* x ∗ f ( x ) f(x) f ( x ) x ∗ x^* x ∗ F ( x ∗ ) F(x^*) F ( x ∗ )
求解 min ( x 1 2 + x 2 2 ) s . t . x 1 + x 2 = 1 , x 2 ≤ α \mathop{\min} (x_1^2+x_2^2) \ \ \ s.t.\ x_1+x_2=1, x_2\leq \alpha min ( x 1 2 + x 2 2 ) s . t . x 1 + x 2 = 1 , x 2 ≤ α
L ( x 1 , x 2 , λ , μ ) = x 1 2 + x 2 2 + λ ( 1 − x 1 − x 2 ) + μ ( x 2 − α ) \mathcal{L}(x_1,x_2,\lambda,\mu) = x_1^2+x_2^2+\lambda(1-x_1-x_2)+\mu(x_2-\alpha) L ( x 1 , x 2 , λ , μ ) = x 1 2 + x 2 2 + λ ( 1 − x 1 − x 2 ) + μ ( x 2 − α )
{ ∂ L ∂ x i = 0 → ∂ L ∂ x 1 = 2 x 1 − λ = 0 , ∂ L ∂ x 2 = 2 x 2 − λ + μ = 0 x 1 + x 2 − 1 = 0 x 2 − α ≤ 0 μ ≥ 0 μ ( x 2 − α ) = 0 \begin{cases}\frac{\partial L}{\partial x_i} = 0 \to \frac{\partial L}{\partial x_1} = 2x_1-\lambda = 0, \ \ \frac{\partial L}{\partial x_2} = 2x_2-\lambda+\mu = 0\\ x_1+x_2 - 1=0\\ x_2-\alpha\leq0\\ \mu\geq0\\\mu(x_2-\alpha) = 0 \end{cases} ⎩ ⎨ ⎧ ∂ x i ∂ L = 0 → ∂ x 1 ∂ L = 2 x 1 − λ = 0 , ∂ x 2 ∂ L = 2 x 2 − λ + μ = 0 x 1 + x 2 − 1 = 0 x 2 − α ≤ 0 μ ≥ 0 μ ( x 2 − α ) = 0
假设 f ( x ) , c i ( x ) , h j ( x ) f(x),\ c_i(x),\ h_j(x) f ( x ) , c i ( x ) , h j ( x ) R n R^n R n
min x ∈ R n f ( x ) s . t . c i ( x ) ≤ 0 , i = 1 , 2 , … , k h j ( x ) = 0 , j = 1 , 2 , … , l \mathop{\min}\limits_{x\in R^n}f(x)\ \ \ s.t.\ \ c_i(x)\leq 0,\ i=1,2,\dots,k\ \ \ \ h_j(x)=0,\ j=1,2,\dots,l x ∈ R n min f ( x ) s . t . c i ( x ) ≤ 0 , i = 1 , 2 , … , k h j ( x ) = 0 , j = 1 , 2 , … , l
L ( x , α , β ) = f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ j = 1 l β j h j ( x ) \mathcal{L}(x,\alpha,\beta) = f(x)+\sum\limits_{i=1}^k\alpha_ic_i(x)+\sum\limits_{j=1}^l\beta_jh_j(x) L ( x , α , β ) = f ( x ) + i = 1 ∑ k α i c i ( x ) + j = 1 ∑ l β j h j ( x )
这里， x = ( x ( 1 ) , x ( 2 ) , ⋯ , x ( n ) ) T ∈ R n , α i , β j x = (x^{(1)},x^{(2)},\cdots,x^{(n)})^T\in R^n,\ \alpha_i,\ \beta_j x = ( x ( 1 ) , x ( 2 ) , ⋯ , x ( n ) ) T ∈ R n , α i , β j α ≥ 0 \alpha\geq0 α ≥ 0 x x x
θ P ( x ) = max α , β : α i ≥ 0 L ( x , α , β ) \theta_P(x)=\mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathcal{L}(x,\alpha,\beta) θ P ( x ) = α , β : α i ≥ 0 max L ( x , α , β )
这里，下标 P P P x x x x x x i i i c i ( w ) > 0 c_i(w)>0 c i ( w ) > 0 j j j h j ( w ) ≠ 0 h_j(w)\neq0 h j ( w ) = 0
θ P ( x ) = max α , β : α ≥ 0 [ f ( x ) + ∑ i = 1 k α i c i ( x ) + ∑ j = 1 l β j h j ( x ) ] = + ∞ \theta_P(x)=\mathop{\max}\limits_{\alpha,\beta:\alpha\geq0}[f(x)+\sum\limits_{i=1}^k\alpha_ic_i(x)+\sum\limits_{j=1}^l\beta_jh_j(x)]=+\infty θ P ( x ) = α , β : α ≥ 0 max [ f ( x ) + i = 1 ∑ k α i c i ( x ) + j = 1 ∑ l β j h j ( x )] = + ∞
因为若某个 i i i c i ( x ) > 0 c_i(x)>0 c i ( x ) > 0 α i → + ∞ \alpha_i\to+\infty α i → + ∞ j j j h j ( x ) ≠ 0 h_j(x)\neq0 h j ( x ) = 0 β j h j ( x ) → + ∞ \beta_jh_j(x)\to+\infty β j h j ( x ) → + ∞ α i , β j \alpha_i,\ \beta_j α i , β j 0 0 0
相反地，若 x x x θ P ( x ) = f ( x ) \theta_P(x)=f(x) θ P ( x ) = f ( x )
θ P ( x ) = { f ( x ) , x 满足原始约束 + ∞ , 其他 \theta_P(x)=\begin{cases}f(x),\ x满足原始约束\\+\infty,\ 其他\end{cases} θ P ( x ) = { f ( x ) , x 满足原始约束 + ∞ , 其他
min x θ P ( x ) = min x max α , β : α ≥ 0 L ( x , α , β ) \mathop{\min}\limits_x\theta_P(x)=\mathop{\min}\limits_x\mathop{\max}\limits_{\alpha,\beta:\alpha\geq0}\mathcal{L}(x,\alpha,\beta) x min θ P ( x ) = x min α , β : α ≥ 0 max L ( x , α , β )
它是与原始最优化问题等价的，即他们有相同解。问题 m i n x m a x α , β : α ≥ 0 L ( x , α , β ) \mathop{min}\limits_x\mathop{max}\limits_{\alpha,\beta:\alpha\geq0}\mathcal{L}(x,\alpha,\beta) x min α , β : α ≥ 0 ma x L ( x , α , β )
p ∗ = min x θ P ( x ) p^* = \mathop{\min}\limits_x\theta_P(x) p ∗ = x min θ P ( x )
定义 θ D ( α , β ) = min x L ( x , α , β ) \theta_D(\alpha,\beta)=\mathop{\min}\limits_x\mathcal{L}(x,\alpha,\beta) θ D ( α , β ) = x min L ( x , α , β )
max α , β : α i ≥ 0 θ D ( α , β ) = max α , β : α i ≥ 0 min x L ( x , α , β ) \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta) = \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathop{\min}\limits_x\mathcal{L}(x,\alpha,\beta) α , β : α i ≥ 0 max θ D ( α , β ) = α , β : α i ≥ 0 max x min L ( x , α , β )
max α , β : α i ≥ 0 θ D ( α , β ) = max α , β : α i ≥ 0 min x L ( x , α , β ) s . t . α i ≥ 0 , i = 1 , 2 , … , k \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta) = \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathop{\min}\limits_x\mathcal{L}(x,\alpha,\beta)\ \ \ \ s.t.\ \alpha_i\geq0,\ i=1,2,\dots,k α , β : α i ≥ 0 max θ D ( α , β ) = α , β : α i ≥ 0 max x min L ( x , α , β ) s . t . α i ≥ 0 , i = 1 , 2 , … , k
d ∗ = max α , β : α i ≥ 0 θ D ( α , β ) d^* = \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta) d ∗ = α , β : α i ≥ 0 max θ D ( α , β )
d ∗ = max α , β : α i ≥ 0 min x L ( x , α , β ) ≤ min x max α , β : α i ≥ 0 L ( x , α , β ) = p ∗ d^* = \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathop{\min}\limits_x\mathcal{L}(x,\alpha,\beta)\leq \mathop{\min}\limits_x\mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathcal{L}(x,\alpha,\beta)=p^* d ∗ = α , β : α i ≥ 0 max x min L ( x , α , β ) ≤ x min α , β : α i ≥ 0 max L ( x , α , β ) = p ∗
由 max α , β : α i ≥ 0 θ D ( α , β ) = max α , β : α i ≥ 0 min x L ( x , α , β ) \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta) = \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathop{\min}\limits_x\mathcal{L}(x,\alpha,\beta) α , β : α i ≥ 0 max θ D ( α , β ) = α , β : α i ≥ 0 max x min L ( x , α , β ) θ P ( x ) = max α , β : α i ≥ 0 L ( x , α , β ) \theta_P(x)=\mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathcal{L}(x,\alpha,\beta) θ P ( x ) = α , β : α i ≥ 0 max L ( x , α , β ) α , β , x \alpha,\beta,x α , β , x
θ D ( α , β ) = min x L ( x , α , β ) ≤ L ( x , α , β ) ≤ max α , β : α i ≥ 0 L ( x , α , β ) = θ P ( x ) \theta_D(\alpha,\beta)=\mathop{\min}\limits_x\mathcal{L}(x,\alpha,\beta)\leq\mathcal{L}(x,\alpha,\beta)\leq\mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathcal{L}(x,\alpha,\beta)=\theta_P(x) θ D ( α , β ) = x min L ( x , α , β ) ≤ L ( x , α , β ) ≤ α , β : α i ≥ 0 max L ( x , α , β ) = θ P ( x )
即 θ D ( α , β ) ≤ θ P ( x ) \theta_D(\alpha,\beta)\leq\theta_P(x) θ D ( α , β ) ≤ θ P ( x )
max α , β : α i ≥ 0 θ D ( α , β ) ≤ min x θ P ( x ) \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\theta_D(\alpha,\beta)\leq\mathop{\min}\limits_x\theta_P(x) α , β : α i ≥ 0 max θ D ( α , β ) ≤ x min θ P ( x )
d ∗ = max α , β : α i ≥ 0 min x L ( x , α , β ) ≤ min x max α , β : α i ≥ 0 L ( x , α , β ) = p ∗ d^* = \mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathop{\min}\limits_x\mathcal{L}(x,\alpha,\beta)\leq \mathop{\min}\limits_x\mathop{\max}\limits_{\alpha,\beta:\alpha_i\geq0}\mathcal{L}(x,\alpha,\beta)=p^* d ∗ = α , β : α i ≥ 0 max x min L ( x , α , β ) ≤ x min α , β : α i ≥ 0 max L ( x , α , β ) = p ∗
推论：设 x ∗ , α ∗ , β ∗ x^*,\ \alpha^*,\ \beta^* x ∗ , α ∗ , β ∗ d ∗ = p ∗ d^*=p^* d ∗ = p ∗ x ∗ , α ∗ , β ∗ x^*,\ \alpha^*,\ \beta^* x ∗ , α ∗ , β ∗
1、一个需要极大化的线性函数，例如 c 1 x 1 + c 2 x 2 c_1x_1+c_2x_2 c 1 x 1 + c 2 x 2
2、以下形式的问题约束，例如 a 11 x 1 + a 12 x 2 ≤ b 1 a 21 x 1 + a 22 x 2 ≤ b 2 a_{11}x_1+a_{12}x_2\leq b_1\ \ \ a_{21}x_1+a_{22}x_2\leq b_2 a 11 x 1 + a 12 x 2 ≤ b 1 a 21 x 1 + a 22 x 2 ≤ b 2
3、和非负变量，例如 x 1 ≥ 0 , x 2 ≥ 0 x_1\geq 0 , x_2\geq 0 x 1 ≥ 0 , x 2 ≥ 0
max c T x s . t . A x ≤ b , x ≥ 0 \mathop{\max}c^Tx\ \ \ \ \ s.t.Ax\leq b, x\geq0 max c T x s . t . A x ≤ b , x ≥ 0
二次规划包括凸二次优化和非凸二次优化。在此类问题中，目标函数是变量的二次函数，约束条件是变量的线性不等式。假定变量个数为 d d d m m m
min x 1 2 x T Q x + c T x s . t . A x ≤ b \mathop{\min}\limits_x\frac{1}{2}x^TQx+c^Tx\ \ s.t.\ Ax\leq b x min 2 1 x T Q x + c T x s . t . A x ≤ b
其中 x x x d d d Q ∈ R d × d Q\in \mathbb{R}^{d\times d} Q ∈ R d × d 实对称矩阵 ， A ∈ R m × d A\in \mathbb{R}^{m\times d} A ∈ R m × d 实矩阵 ， b ∈ R m b\in \mathbb{R}^m b ∈ R m c ∈ R d c\in \mathbb{R}^d c ∈ R d A x ≤ b Ax\leq b A x ≤ b
1、若 Q Q Q 半正定矩阵 ，则上式是凸函数，相应的二次规划是凸二次优化问题；此时若约束条件 A x ≤ b Ax\leq b A x ≤ b
2、若 Q Q Q 正定矩阵 ，则该问题有唯一的全局最小解
3、若 Q Q Q
半正定规划(SDP)是一类凸优化问题，其中的变量可组织成半正定对称矩阵形式，且优化问题的目标函数和约束都是这些变量的线性函数。给定 d × d d\times d d × d X 、 C X、C X 、 C
C ⋅ X = ∑ i = 1 d ∑ j = 1 d C i j X i j C\cdot X = \sum\limits_{i=1}^{d}\sum\limits_{j=1}^{d}C_{ij}X_{ij} C ⋅ X = i = 1 ∑ d j = 1 ∑ d C ij X ij
若 A i ( i = 1 , 2 , … , m ) A_i(i=1,2,\dots,m) A i ( i = 1 , 2 , … , m ) d × d d\times d d × d b i ( i = 1 , 2 , … , m ) b_i(i=1,2,\dots,m) b i ( i = 1 , 2 , … , m ) m m m
min X C ⋅ X s . t . A i ⋅ X = b i , i = 1 , 2 , … , m X ⪰ 0 \mathop{\min}\limits_{X} C\cdot X \ \ \ s.t.\ A_i\cdot X=b_i,\ i=1,2,\dots,m\ \ X\succeq 0 X min C ⋅ X s . t . A i ⋅ X = b i , i = 1 , 2 , … , m X ⪰ 0
半正定规划与线性规划都拥有线性的目标函数和约束，但半正定规划中的约束 X ⪰ 0 X\succeq 0 X ⪰ 0
