# 约束最优化 (Constrained Optimization)
约束最优化 (Constrained Optimization) 是{{{应用数学}}}、{{{运筹学}}}、{{{经济学}}}和{{{统计学}}}等领域中的一个核心分支。它研究的问题是：如何在满足一系列特定约束条件（constraints）的前提下，寻找一个或多个变量的取值，使得一个给定的目标函数（objective function）达到最大值或最小值。
与{{{无约束最优化}}}（Unconstrained Optimization）在整个定义域内自由地寻找最优解不同，约束最优化必须在一个由等式或不等式限制的可行域 (feasible set/region) 内寻找最优解。现实世界中的绝大多数决策问题，从个人理财到企业生产再到国家宏观调控，本质上都是约束最优化问题。
## 问题的数学表述
一个标准的约束最优化问题可以表述为以下形式：
目标： $$ \min_{x \in \mathbb{R}^n} f(x) \quad \text{或} \quad \max_{x \in \mathbb{R}^n} f(x) $$
约束条件 (subject to)： $$ g_i(x) = 0, \quad i = 1, \ldots, m \quad (\text{等式约束}) $$ $$ h_j(x) \le 0, \quad j = 1, \ldots, k \quad (\text{不等式约束}) $$
其中： * $x = (x_1, x_2, \ldots, x_n)$ 是一个包含 $n$ 个决策变量（decision variables）的向量。 * $f(x): \mathbb{R}^n \to \mathbb{R}$ 是需要被最小化或最大化的目标函数。 * $g_i(x): \mathbb{R}^n \to \mathbb{R}$ 是 $m$ 个等式约束 (equality constraints) 函数。 * $h_j(x): \mathbb{R}^n \to \mathbb{R}$ 是 $k$ 个不等式约束 (inequality constraints) 函数。
所有满足上述所有约束条件的点 $x$ 的集合构成了可行域。我们的任务就是在这个集合中找到使 $f(x)$ 最优的点 $x^*$。
## 核心方法：拉格朗日乘子法
处理约束最优化问题的基本分析工具是拉格朗日乘子法 (Method of Lagrange Multipliers)。它通过引入一个辅助变量——{{{拉格朗日乘子}}} (Lagrange Multiplier)——将一个有约束的优化问题转化为一个更大维度的无约束优化问题。
### 1. 仅有等式约束的情况
考虑一个只包含等式约束的优化问题： $$ \min_{x} f(x) \quad \text{s.t.} \quad g_i(x) = 0, \quad i=1, \ldots, m $$
我们可以构造一个拉格朗日函数 (Lagrangian function)： $$ L(x, \lambda) = f(x) - \sum_{i=1}^{m} \lambda_i g_i(x) $$ 这里的 $\lambda = (\lambda_1, \ldots, \lambda_m)$ 就是拉格朗日乘子向量。
寻找这个约束问题最优解的一阶必要条件 (First-Order Necessary Conditions, FOCs) 是拉格朗日函数对所有变量（包括 $x$ 和 $\lambda$）的{{{偏导数}}}均为零： $$ \frac{\partial L}{\partial x_k} = \frac{\partial f}{\partial x_k} - \sum_{i=1}^{m} \lambda_i \frac{\partial g_i}{\partial x_k} = 0, \quad \text{for } k = 1, \ldots, n $$ $$ \frac{\partial L}{\partial \lambda_i} = -g_i(x) = 0, \quad \text{for } i = 1, \ldots, m $$ 最后一个条件恰好就是我们原始的等式约束。
几何直观：在最优解 $x^*$ 处，目标函数 $f(x)$ 的{{{梯度}}}向量 $\nabla f(x^*)$ 必须是所有约束函数梯度向量 $\nabla g_i(x^*)$ 的线性组合。也就是说， $$ \nabla f(x^*) = \sum_{i=1}^{m} \lambda_i \nabla g_i(x^*) $$ 这意味着在最优解处，目标函数的等高线（或等高面）与约束条件所定义的曲线（或曲面）相切。如果它们不相切而是相交，那么我们总可以沿着约束曲面移动，找到一个使目标函数值更优的点。
经济学解释：拉格朗日乘子 $\lambda_i$ 有着重要的经济学含义，它通常被称为影子价格 (shadow price)。它衡量了当第 $i$ 个约束 $g_i(x)=0$ 被略微放松时（例如，变为 $g_i(x)=\epsilon$），目标函数的 optimal value 会改变多少。在{{{消费者理论}}}中，当最大化{{{效用}}}受到{{{预算约束}}}时，$\lambda$ 就是收入的{{{边际效用}}}。
### 2. 包含不等式约束：卡罗需-库恩-塔克 (KKT) 条件
当问题包含不等式约束 $h_j(x) \le 0$ 时，情况变得更为复杂。因为在最优解处，一个不等式约束可能是紧的 (binding, 即 $h_j(x^*) = 0$)，也可能是松的 (non-binding, 即 $h_j(x^*) < 0$)。
处理这种情况的理论是卡罗需-库恩-塔克 (Karush-Kuhn-Tucker, KKT) 条件。它是拉格朗日乘子法的推广。
对于问题： $$ \min_{x} f(x) \quad \text{s.t.} \quad h_j(x) \le 0, \quad j=1, \ldots, k $$
我们构造拉格朗日函数： $$ L(x, \mu) = f(x) + \sum_{j=1}^{k} \mu_j h_j(x) $$ 注意，为了方便，这里对不等式约束的乘子 $\mu_j$ 使用了正号。最优解 $x^*$ 和对应的 KKT 乘子 $\mu^*$ 必须满足以下条件（假设满足一定的正则性条件，如{{{约束规范}}} (constraint qualification)）：
1. 平稳性 (Stationarity)： $$ \nabla_x L(x^*, \mu^*) = \nabla f(x^*) + \sum_{j=1}^{k} \mu_j^* \nabla h_j(x^*) = 0 $$
2. 原始可行性 (Primal Feasibility)： $$ h_j(x^*) \le 0, \quad \text{for all } j=1, \ldots, k $$
3. 对偶可行性 (Dual Feasibility)： $$ \mu_j^* \ge 0, \quad \text{for all } j=1, \ldots, k $$ 这个条件是关键。它表明，对于一个最小化问题，使得约束 $h_j(x) \le 0$ 更难满足（即增加 $h_j(x)$ 的值）不会使得目标函数的最优值变得更小。
4. 互补松弛性 (Complementary Slackness)： $$ \mu_j^* h_j(x^*) = 0, \quad \text{for all } j=1, \ldots, k $$ 这个条件优雅地处理了不等式约束的两种可能性： * 如果约束是松的，即 $h_j(x^*) < 0$，那么其对应的乘子必须为零，$\mu_j^*=0$。这意味着该约束在最优解附近是无效的，对目标函数没有贡献，其“影子价格”为零。 * 如果一个乘子是正的，即 $\mu_j^* > 0$，那么其对应的约束必须是紧的， $h_j(x^*)=0$。这意味着该约束是积极限制目标函数达到更优值的“障碍”，因此它有一个正的“影子价格”。
当问题同时包含等式和不等式约束时，KKT 条件会结合上述两种情况。
## 主要应用领域
* {{{经济学}}}： * {{{消费者理论}}}：在{{{预算约束}}}下最大化{{{效用函数}}}。 * {{{生产者理论}}}：在成本预算内最大化产量，或在给定产量下最小化成本。 * {{{一般均衡理论}}}：在资源和技术的约束下求解社会福利最大化问题。
* {{{金融学}}}： * {{{现代投资组合理论}}} (MPT)：在给定的预期收益率下最小化投资组合的{{{方差}}}（风险），或者在给定的风险水平下最大化预期收益。求解结果构成了{{{效率前沿}}}。 * {{{期权定价}}}：无套利定价原理可以被构建为一个约束最优化问题。
* {{{统计学}}}与{{{机器学习}}}： * {{{支持向量机}}} (SVM)：其核心是求解一个{{{二次规划}}}问题，旨在找到一个最大化分类间隔的超平面。 * {{{最大熵模型}}}：在满足从数据中观察到的特征期望的约束下，寻找熵最大的概率分布。 * {{{Lasso回归}}}：在线性回归中加入 L1 {{{正则化}}}项，本质上是一个带有不等式约束的最小二乘问题。
## 进一步的讨论：凸优化
在约束最优化中，一个特别重要且研究深入的子领域是{{{凸优化}}} (Convex Optimization)。如果一个最小化问题的目标函数是{{{凸函数}}}，且可行域是一个{{{凸集}}}（即由仿射函数定义的等式约束和凸函数定义的不等式约束构成），那么该问题就是一个凸优化问题。
凸优化问题的优良特性在于： * 局部最优即全局最优：在非凸问题中找到的解可能是局部最优解而非全局最优解，但在凸优化问题中，任何局部最优解都保证是全局最优解。 * 高效的算法：存在许多高效且可靠的算法（如内点法）可以在多项式时间内求解大规模的凸优化问题。
许多经济和工程问题都可以被建模为{{{线性规划}}} (Linear Programming) 或{{{二次规划}}} (Quadratic Programming)，它们都是凸优化的特例。