KNOWECON WIKI

ARTICLE

约束优化问题

约束优化问题 (Constrained Optimization) 约束优化问题是数学优化中最核心的框架之一。与无约束优化不同，约束优化要求在满足一组等式或不等式约束的前提下，寻找目标函数的极值。标准形式为： 其中 x R^n 为决策变量，f : R^n R 为目标函数，g_i 为不等式约束，h_j 为等式约束。可行域 F = \x g_i(x) 0,\;

浏览 6 更新 2025-11-04

约束优化问题 (Constrained Optimization)

约束优化问题是数学优化中最核心的框架之一。与无约束优化不同，约束优化要求在满足一组等式或不等式约束的前提下，寻找目标函数的极值。标准形式为：

minimize⁡f(x)subject togi(x)≤0,i=1,…,mhj(x)=0,j=1,…,p\begin{aligned} \operatorname{minimize} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \leq 0, \quad i = 1, \ldots, m \\ & h_j(x) = 0, \quad j = 1, \ldots, p \end{aligned}

其中 x∈Rnx \in \mathbb{R}^n 为决策变量，f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} 为目标函数，gig_i 为不等式约束，hjh_j 为等式约束。可行域 F={x∣gi(x)≤0,  hj(x)=0}\mathcal{F} = \{x \mid g_i(x) \leq 0,\; h_j(x) = 0\} 是所有满足约束的点的集合。约束的存在使得最优点未必是目标函数的驻点，这是约束优化区别于无约束优化的本质特征。

等式约束与 Lagrange 乘子法

仅含等式约束的情形是约束优化的起点：

minimize⁡  f(x)s.t.hj(x)=0,  j=1,…,p\operatorname{minimize} \; f(x) \quad \text{s.t.} \quad h_j(x) = 0,\; j = 1,\ldots,p

核心工具是 Lagrange 乘子法。构造 Lagrange 函数：

L(x,λ)=f(x)+∑j=1pλjhj(x)\mathcal{L}(x, \lambda) = f(x) + \sum_{j=1}^{p} \lambda_j h_j(x)

其中 λj∈R\lambda_j \in \mathbb{R} 称为 Lagrange multiplier（拉格朗日乘子）。一阶必要条件为：

∇xL(x∗,λ∗)=∇f(x∗)+∑j=1pλj∗∇hj(x∗)=0,hj(x∗)=0\nabla_x \mathcal{L}(x^*, \lambda^*) = \nabla f(x^*) + \sum_{j=1}^{p} \lambda_j^* \nabla h_j(x^*) = 0, \quad h_j(x^*) = 0

Lagrange 乘子的几何直觉清晰而深刻：在最优点 x∗x^*，目标函数的梯度 ∇f(x∗)\nabla f(x^*) 必须位于所有约束梯度 ∇hj(x∗)\nabla h_j(x^*) 张成的子空间中，即不存在在切空间内进一步下降的可行方向。Lagrange 乘子 λj\lambda_j 度量了约束 hjh_j 的影子价格——放松第 jj 个约束一个单位对最优目标值的边际影响，这一性质由包络定理给出。

不等式约束与 KKT 条件

引入不等式约束 gi(x)≤0g_i(x) \leq 0 后，情况更加复杂：最优解可位于约束边界（gi(x∗)=0g_i(x^*) = 0，称为紧约束或 binding constraint）或严格内部（gi(x∗)<0g_i(x^*) < 0，称为松约束）。Karush-Kuhn-Tucker (KKT) 条件提供了处理不等式约束的完整框架。对标准形式的约束优化问题，KKT 条件包括：

  1. 驻点条件（Stationarity）：∇f(x∗)+∑iμi∗∇gi(x∗)+∑jλj∗∇hj(x∗)=0\nabla f(x^*) + \sum_i \mu_i^* \nabla g_i(x^*) + \sum_j \lambda_j^* \nabla h_j(x^*) = 0
  2. 原始可行性（Primal Feasibility）：gi(x∗)≤0,  hj(x∗)=0g_i(x^*) \leq 0,\; h_j(x^*) = 0
  3. 对偶可行性（Dual Feasibility）：μi∗≥0\mu_i^* \geq 0
  4. 互补松弛条件（Complementary Slackness）：μi∗gi(x∗)=0\mu_i^* g_i(x^*) = 0

互补松弛条件是理解不等式约束的关键：对于松约束（gi(x∗)<0g_i(x^*) < 0），必有 μi∗=0\mu_i^* = 0，该约束不发挥作用；对于紧约束（gi(x∗)=0g_i(x^*) = 0），μi∗>0\mu_i^* > 0 表明约束在最优解处具有正的影子价格，放松约束将改善目标值。

当目标函数和不等式约束均为凸函数、等式约束为仿射函数时，KKT 条件不仅是必要的，而且是充分的——满足 KKT 条件的点即为全局最优解。这是凸优化理论的核心结果。

约束品性

KKT 条件的必要性并非无条件成立，需要约束品性 (Constraint Qualification)来保证最优解处切锥与线性化可行方向锥重合。常见的约束品性包括：

  • Slater 条件：若不等式约束为凸函数，则存在严格可行内点 gi(x)<0g_i(x) < 0 对所有 ii 成立。Slater 条件是凸优化中最常用且最易验证的约束品性，保证强对偶性和 KKT 必要性。
  • 线性独立约束品性 (LICQ)：活跃约束的梯度集合线性独立。
  • Mangasarian-Fromovitz 约束品性 (MFCQ)：比 LICQ 更弱的条件，仅要求等式约束梯度线性独立且存在方向使所有不等式约束梯度严格为负。

若约束品性不满足，KKT 条件可能在最优解处不成立，这是实践中需要警惕的边界情形。

对偶理论

约束优化问题的Lagrange 对偶函数定义为：

q(μ,λ)=inf⁡xL(x,μ,λ)=inf⁡x{f(x)+∑iμigi(x)+∑jλjhj(x)}q(\mu, \lambda) = \inf_{x} \mathcal{L}(x, \mu, \lambda) = \inf_x \left\{ f(x) + \sum_i \mu_i g_i(x) + \sum_j \lambda_j h_j(x) \right\}

对偶函数具有两个关键性质：它是凹函数（即使原问题非凸），且对任意 μ≥0,λ\mu \geq 0, \lambda 给出原问题最优值 p∗p^* 的下界（弱对偶性）。对偶问题为在 μ≥0\mu \geq 0 约束下最大化 q(μ,λ)q(\mu, \lambda)，是一个凹最大化问题，通常在计算上更易处理。

当原问题为凸优化且满足约束品性时，强对偶性 d∗=p∗d^* = p^* 成立，对偶间隙为零。强对偶性使得可以通过求解对偶问题获得原问题的最优解，这一原理支撑着支持向量机（SVM）、LASSO 的对偶推导以及拍卖理论中的许多机制设计。

经济学应用

约束优化构成了微观经济学几乎所有最优决策问题的数学基础。

消费者理论中，效用最大化问题是在预算约束 p⋅x≤wp \cdot x \leq w 下最大化效用函数 u(x)u(x)，Lagrange 乘子即为收入的边际效用。由对偶性导出的支出最小化问题给出了希克斯需求函数，两者通过恒等式 h(p,u)=x(p,e(p,u))h(p, u) = x(p, e(p, u)) 和 x(p,w)=h(p,v(p,w))x(p, w) = h(p, v(p, w)) 相互联系。Slutsky 方程将价格变化的需求效应分解为替代效应和收入效应，其数学根源正是约束优化的包络性质。

生产者理论中，成本最小化给定产量约束下的要素需求是标准的约束优化问题，成本函数 c(w,q)c(w, q) 是值函数，条件要素需求由 Shephard 引理给出。利润最大化则可视为无约束优化，但技术约束通过生产函数间接体现。

契约理论中，道德风险和逆向选择模型的激励相容约束（IC）和参与约束（IR）构成典型的约束优化结构，最优契约设计即是在信息不对称约束下最大化委托人期望收益。拉姆齐定价问题涉及在盈亏平衡约束下最大化社会福利，其 Lagrange 乘子给出了偏离边际成本定价的最优加价幅度。

计量经济学中，带有参数约束的最大似然估计、假设检验中的似然比检验（其统计量通过约束与无约束似然比构造），以及 GMM 估计中的矩条件约束均可纳入约束优化的统一框架。