3.4. 拉格朗日乘子法

3.4.1. 概念与内涵

在优化理论中, 拉格朗日乘子 (Lagrange Multiplier) 法是用于求解等式约束优化问题的局部极小极大问题. 其基本思想是将约束优化问题转化为无约束优化问题. 函数的不动点/稳定点(stationary point)也满足等式约束, 即函数在该不动点的梯度可以表示成约束在该点的梯度的线性组合, 从而原始问题可转化为拉格朗日函数形式 (Lagrangian Function).

Definition 3.1

设有等式约束优化问题:

(3.4)P0:minx f(x)  s.t.  gi(x)=0,{P}_0: {\rm min}_{\bm x}\ f({\bm x})\ \ {\rm s.t.}\ \ g_i({\bm x}) = 0,

其中, gi,i=1,2,,Mg_i, i=1,2,\cdots,MMM 个等式约束. 化为无约束优化的拉格朗日函数形式为

(3.5)P1:minx L(x,λ)=f(x)i=1Mλigi(x),{P}_1: {\rm min}_{\bm x}\ L({\bm x}, {\bm \lambda}) = f({\bm x}) - \sum_{i=1}^M \lambda_i g_i({\bm x}),

其中, λi,i=1,2,,M\lambda_i, i=1,2,\cdots,M拉格朗日乘子 (Lagrange Multiplier), 等号右边两项可以为加也可以为减. 其矩阵形式为

(3.6)P1:minx L(x,λ)=f(x)λTg,{P}_1: {\rm min}_{\bm x}\ L({\bm x}, {\bm \lambda}) = f({\bm x}) - {\bm \lambda}^T {\bm g},

其中, λ=[λ1,λ2,,λM]T{\bm \lambda} = [\lambda_1, \lambda_2, \cdots, \lambda_M]^TMM 个拉格朗日乘子构成的向量, x=[x1,x2,,xN]T{\bm x} = [x_1, x_2, \cdots, x_N]^TNN 个变量构成的向量, g=[g1(x),g2(x),,gM(x)]T{\bm g} = [g_1({\bm x}), g_2({\bm x}),\cdots, g_M(\bm x)]^TMM 个约束构成的向量.

易知 式.3.6λ{\bm \lambda} 求导为

λL(x,λ)=g\nabla_{\bm \lambda} L({\bm x}, {\bm \lambda}) = {\bm g}

式.3.6x{\bm x} 求导为

xL(x,λ)=xf(x)i=1Mλixgi(x)=xf(x)λTxg\nabla_{\bm x} L({\bm x}, \lambda) = {\nabla}_{\bm x}f({\bm x}) - \sum_{i=1}^M \lambda_i{\nabla}_{\bm x}g_i(\bm x) = {\nabla}_{\bm x}f({\bm x}) - {\bm \lambda}^T{\nabla}_{\bm x}{\bm g}

从而有

(3.7)x,λL(x,λ)=0{f(x)=λTxg=i=1Mλixgi(x)g1(x)==gM(x)=0{\nabla}_{{\bm x},{\bm \lambda}}L({\bm x}, {\bm \lambda}) = 0 \Longleftrightarrow \left\{\begin{array}{l}{\nabla f({\bm x}) = {\bm \lambda}^T {\nabla}_{\bm x}{\bm g} = \sum_{i=1}^M\lambda_i {\nabla}_{\bm x}g_i({\bm x})} \\ {g_{1}({\bm x})=\cdots=g_M({\bm x})=0}\end{array}\right.

3.4.2. 拉格朗日函数的对偶问题

3.4.3. 约束优化与流形学习

寻找满足等式/不等式约束的极小极大问题, 可推广为寻找不同流形 M{\mathcal M} 上的最小值与最大值. M{\mathcal M} 不一定是欧式空间, 也可以是黎曼空间.

Modern formulation via differentiable manifolds

3.4.4. 实验与分析