文章

优化问题

Optimization
本文目录 5

Intro

优化问题是数学/算法中的一个重要的工具

梯度和梯度下降法

设多元函数 f(x1,x2,…,xn)f(x_1, x_2, \dots, x_n) 在点 PP 的某邻域内可微，则称由该函数在点 PP 处的所有一阶偏导数组成的列向量

∇f(P)=(∂f∂x1,∂f∂x2,…,∂f∂xn)⊤\nabla f(P) = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n} \right)^\top

为函数 ff 在点 PP 处的梯度

它指向函数值增加最快的方向，其长度表示沿该方向单位距离上函数值增加的最大速率

那么这个定义是怎么来的呢？这里就要引入一个新的概念，即函数在一个点附近的变化率方向导数，记作 Duf(x0)=lim⁡t→0f(x0+tu)−f(x0)t=ddtf(x0+tu)∣t=0\boxed{D_u f(x_0) = \lim_{t \to 0} \frac{f(x_0 + t u) - f(x_0)}{t} = \left. \frac{d}{dt} f(x_0 + t u) \right|_{t=0}}

这里uu是一个单位向量，这个导数表示的就是我朝一个单位方向走一步的瞬时变化值

由多元函数链式法则（推导见附录）： [ \frac{d}{dt} f(x(t)) = \sum_{i=1}^n \frac{\partial f}{\partial x_i} \cdot \frac{d x_i}{dt} ]

因为 dxidt=ui\frac{d x_i}{dt} = u_i，代入得： [ \frac{d}{dt} f(x_0 + t u) = \sum_{i=1}^n \frac{\partial f}{\partial x_i}(x_0 + t u) \cdot u_i ]

在 t=0t=0 处取极限： [ D_u f(x_0) = \left. \frac{d}{dt} f(x_0 + t u) \right|{t=0} = \sum{i=1}^n \frac{\partial f}{\partial x_i}(x_0) \cdot u_i ]

拉格朗日乘子法

一、解决目标

在给定一个或多个等式约束的条件下，求解多元函数（目标函数）的局部极值（最大值或最小值）。

  • 如果没有约束，我们直接令所有偏导数为 0 即可，然后解方程即可
  • 但有了约束，变量的取值被限制在一条曲线、一个曲面或更高维的“流形”上，不能自由移动。
  • 拉格朗日乘子法的目标就是：把“带约束的极值问题”转化为“无约束的极值问题”来求解。

二、应用条件

条件类别具体要求说明
问题形式目标函数 f(x1,…,xn)f(x_1,\dots,x_n) 在等式约束 gk(x1,…,xn)=0g_k(x_1,\dots,x_n)=0（k=1,…,mk=1,\dots,m）下求极值只适用于等式约束；若是不等式约束，需改用 KKT 条件
可微性ff 和所有 gkg_k 在定义域内连续且一阶偏导数存在因为方法的核心是求梯度，不可导则无法使用
约束正则性（LICQ）在极值点处，所有约束的梯度 ∇gk\nabla g_k 必须线性无关（且均不为零向量）保证拉格朗日乘子 λk\lambda_k 存在且唯一；否则方法可能失效或给出错误点
结果性质求出的只是候选极值点（必要条件），是否为真正极值需额外验证需用二阶条件（在约束切空间上检查海森矩阵的正定/负定性）或直接比较数值

补充：如果问题恰好是凸优化（ff 为凸函数，等式约束为线性仿射函数），则满足上述条件后，求出的点自动是全局最优解，无需二阶验证。

三、应用方法（具体怎么操作？步骤是什么？）

标准步骤（单约束情况，多约束同理推广）：

Step 1：构造拉格朗日函数
引入一个或多个新变量（称为拉格朗日乘子 λ\lambda），构造辅助函数： [ \mathcal{L}(x_1,\dots,x_n,\lambda) = f(x_1,\dots,x_n) + \lambda , g(x_1,\dots,x_n) ] （有些教材用减号，符号不影响本质，只影响 λ\lambda 的正负号）

Step 2：对所有变量及 λ\lambda 求一阶偏导数，并令其等于 0
得到方程组： [ \begin{cases} \dfrac{\partial \mathcal{L}}{\partial x_i} = \dfrac{\partial f}{\partial x_i} + \lambda \dfrac{\partial g}{\partial x_i} = 0, & i=1,\dots,n \[10pt] \dfrac{\partial \mathcal{L}}{\partial \lambda} = g(x_1,\dots,x_n) = 0 \end{cases} ]

Step 3：解这个方程组
得到所有可能的候选点 (x1∗,…,xn∗)(x_1^*,\dots,x_n^*) 及对应的 λ∗\lambda^*。

Step 4：验证是否为真正的极值点

  • 若问题为凸优化，直接确认是全局最优。
  • 否则，使用二阶充分条件（即检查拉格朗日函数在约束切空间上的海森矩阵是否正定/负定），或通过实际数值比较。
多约束的推广

若有 mm 个等式约束 g1=0,…,gm=0g_1=0,\dots,g_m=0，则构造： [ \mathcal{L} = f + \sum_{k=1}^m \lambda_k g_k ] 然后对所有 xix_i 和所有 λk\lambda_k 求偏导为零，得到 n+mn+m 个方程，解出 n+mn+m 个未知数。

四、原理

几何直观解释
  • 在无约束时，极值点处目标函数的梯度 ∇f=0\nabla f = 0（各个方向都不能再下降/上升）。
  • 在有约束时，变量只能在约束曲面（g=0g=0）上移动。在极值点处，沿着约束曲面任何切线方向移动，目标函数 ff 都不能再变化。
  • 这意味着：∇f\nabla f 必须与约束曲面垂直（即与所有切向量点积为 0）。
  • 而约束曲面的法线方向恰好是 ∇g\nabla g 的方向。
    因此，∇f\nabla f 必须与 ∇g\nabla g 平行，即存在实数 λ\lambda 使得： [ \nabla f + \lambda \nabla g = 0 ] 这正是拉格朗日函数对 xx 求偏导为零的向量形式。
代数推导（简版）

在极值点 x∗x^* 处，对约束 g(x)=0g(x)=0 作微小扰动 dxdx（须满足 ∇g⋅dx=0\nabla g \cdot dx = 0），由于 ff 取极值，也有 ∇f⋅dx=0\nabla f \cdot dx = 0。
因此，∇f\nabla f 和 ∇g\nabla g 都正交于同一个切空间（由所有 dxdx 张成），所以二者必须共线。引入比例系数 λ\lambda 即得上述方程。

乘子 λ\lambda 的额外含义（敏感性）

λ\lambda 本身也有实际意义：它表示约束右端项（即常数项）发生微小变化时，目标函数最优值的变化率。
在经济学中，λ\lambda 被称为“影子价格”，反映约束资源的稀缺程度。

五、总结（一张图概括）

维度核心内容
解决目标等式约束下求多元函数的极值
应用条件等式约束、可微、约束梯度线性无关（LICQ）；求出的为候选点
应用方法构造 L=f+∑λkgk\mathcal{L}=f+\sum \lambda_k g_k，对各变量和 λ\lambda 求偏导为零，解方程组，再验证
原理极值点处 ∇f\nabla f 与约束梯度 ∇g\nabla g 平行（几何：梯度与约束曲面法线共线）