1 基本概念
约束优化研究的是在满足既定条件的前提下，选择变量取值以使目标函数达到最优的问题。与无约束优化相比，它更强调现实条件的限制性，因此在建模时通常需要同时描述“想要优化什么”和“必须满足什么”。
1.1 优化问题的定义
一个典型的约束优化问题可写为在给定变量集合中，最小化或最大化某个目标函数，并要求解满足若干约束条件。若以最小化问题为例，常见形式是求变量向量在限定区域内使目标值尽可能小。不同领域中的表达方式各异，但核心结构通常一致：目标、变量与限制条件共同构成完整问题。
1.2 目标函数与约束条件
目标函数用于刻画优劣标准，约束条件则限定可接受的解的范围。二者结合后，才形成可供分析和计算的优化模型。目标函数可以来源于成本、误差、能耗、风险或收益等，而约束往往来自物理规律、资源上限、逻辑关系或设计规范。
1.2.1 等式约束
等式约束要求变量必须满足精确的代数关系，例如某些守恒条件、平衡条件或配置关系。这类约束把可行解限制在更低维的集合上，使问题的结构更紧凑，也常常增加求解难度。
1.2.2 不等式约束
不等式约束表示变量需要落在某个区间或半空间内，例如容量不超过上限、误差不高于阈值等。它们在工程与管理问题中十分常见，并常与“活跃约束”概念联系在一起，即在最优点处恰好取等号的约束。
1.2.3 边界约束
边界约束是对变量取值范围的直接限制，常写成上下界形式。它们在数值算法中很常见，例如参数必须非负、比例必须介于 0 与 1 之间，或者设计变量不能超过特定物理边界。
1.3 可行域与最优解
满足所有约束的解构成可行域。若在可行域中比较目标函数值，就可以判断哪些点更优。最优解既可能是单点，也可能是一组等价解，具体取决于问题结构与目标函数性质。
1.3.1 局部最优解
局部最优解是指在某个邻域内无法通过微小变化进一步改善目标值的可行解。对于非凸问题，局部最优并不一定是全局最佳，因此它在理论与算法中都具有独立意义。
1.3.2 全局最优解
全局最优解是在整个可行域内都最优的解。若问题满足凸性等良好性质，局部最优常可直接推出全局最优；而在一般非凸情形下，寻找全局最优往往更为困难。
1.4 约束优化问题的分类
约束优化可按约束形式、函数性质和变量类型进行分类。不同类型的问题对应不同的理论工具与算法路线，因此分类是理解该领域的基础步骤。
1.4.1 线性约束优化
线性约束优化中，目标函数和约束条件通常都是线性表达式。这类问题结构规整，理论成熟，常作为优化理论的入门模型，也广泛用于生产、运输和资源配置。
1.4.2 非线性约束优化
当目标或约束中出现非线性项时，就构成非线性约束优化。此类问题更贴近实际，但通常更难分析，可能出现多个局部极值、不可微点或复杂可行域。
1.4.3 凸约束优化
若目标函数与可行域同时具有凸性，则问题属于凸约束优化。凸问题具有较好的结构性质，局部最优即全局最优，并且在许多情况下可通过高效算法稳定求解。
1.4.4 整数约束优化
整数约束优化要求部分或全部变量取整数值，常见于排产、选址和组合设计等问题。由于解空间离散，其复杂度通常显著高于连续优化。
2 理论基础
约束优化的理论基础主要来自凸分析、最优性条件和可行性理论。相关结论不仅用于证明解的存在与性质，也为算法设计提供判据。
2.1 可行性与紧致性
一个问题首先要讨论的是是否存在可行解，其次才是最优解是否能够达到。紧致性等拓扑条件在此类讨论中非常关键，因为它们常常保证极值存在。
2.1.1 可行解的存在条件
若约束彼此矛盾，问题就没有可行解。判定可行性通常依赖于几何分析、代数条件或数值检验，在实际建模中也是检查模型合理性的第一步。
2.1.2 紧致集上的最优性
当可行域是紧致集且目标函数连续时，最优解往往可以保证存在。这一结论是极值理论中的基本结果，也常被用作证明优化模型可解性的起点。
2.2 凸分析基础
凸分析研究凸集、凸函数及其相关性质，是凸优化的重要数学背景。许多约束优化的经典结论都建立在这一框架下。
2.2.1 凸集与凸函数
凸集指任意两点连线上的点仍留在集合内；凸函数则满足“弦在图像上方”的性质。二者的结合使问题具有较强的可分析性，也让局部信息能够有效反映整体结构。
2.2.2 支撑超平面
支撑超平面是与凸集相切且不穿过其内部的超平面。它在分离定理、对偶理论和几何解释中都很重要，能够帮助理解约束边界与最优点之间的关系。
2.2.3 次梯度与亚微分
对于不可微的凸函数，次梯度可视为梯度的推广。亚微分则描述了所有次梯度的集合，为非光滑优化提供了可操作的导数替代工具。
2.3 最优性条件
最优性条件是判断一个可行点是否可能成为最优解的核心工具。它们通常分为必要条件、充分条件以及结合约束结构后的判别形式。
2.3.1 一阶必要条件
一阶必要条件强调在最优点附近，目标函数的局部变化必须与约束结构相协调。对于可微问题，这通常表现为梯度与约束法向量之间的平衡关系。
2.3.2 二阶必要条件
二阶必要条件进一步利用曲率信息判断候选解是否可能为最优。它能排除某些虽然满足一阶条件、但实际上并非极值的点。
2.3.3 充分条件
充分条件在满足一定附加假设时，可直接保证某个可行点就是最优解。对凸问题而言，这类条件尤其简洁，常常只需验证一阶条件即可。
2.4 约束资格条件
约束资格条件用于确保最优性条件中的乘子理论能够正常成立。若这些条件失效，某些经典结论可能不再适用。
2.4.1 正则性条件
正则性条件是对约束集合局部结构的要求，用于避免约束之间出现过度依赖或退化。它通常是拉格朗日乘子法成立的重要前提。
2.4.2 Slater 条件
Slater 条件要求凸优化中存在严格满足不等式约束的点。它不仅便于证明强对偶，也能提升问题结构的良性程度。
2.4.3 LICQ 与 MFCQ
LICQ 表示活跃约束的梯度线性无关，MFCQ 则是更宽松的约束资格条件。二者都常用于非线性规划中，用来保证乘子存在性与KKT条件的适用性。
3 经典理论与定理
经典理论构成约束优化的骨架，其中拉格朗日乘子法、KKT条件和对偶理论尤为重要。它们把几何、代数与优化目标统一到一个分析框架中。
3.1 拉格朗日乘子法
拉格朗日乘子法通过引入辅助变量，将约束问题转化为无约束或较易处理的形式。它的核心思想是：在最优点处，目标函数与约束面之间存在某种局部平衡。
3.1.1 单约束情形
在单个等式约束下，拉格朗日函数通常由目标函数与约束函数线性组合而成。最优点处，目标梯度与约束梯度平行，这是该方法最直观的几何解释。
3.1.2 多约束情形
当存在多个约束时，需要为每个约束引入相应乘子。此时最优条件表现为若干约束梯度的线性组合抵消目标函数的变化方向。
3.1.3 乘子解释
乘子可理解为约束的“影子价格”或边际影响量。它反映了约束放松一点点时，最优值可能发生的变化，因此在经济学与工程敏感性分析中很有用。
3.2 Karush-Kuhn-Tucker 条件
KKT 条件是带不等式约束问题中最重要的最优性条件之一。它将可行性、梯度平衡和互补关系统一起来，构成现代非线性优化的基础工具。
3.2.1 KKT 条件的形式
KKT 条件通常包括原始可行性、对偶可行性、梯度站立性与互补松弛。若满足适当约束资格条件，这些条件对最优解通常是必要的。
3.2.2 KKT 条件的适用范围
KKT条件广泛适用于光滑非线性规划、凸优化以及部分约束结构良好的问题。对于非光滑或退化问题，往往需要结合次梯度或更一般的条件。
3.2.3 KKT 条件与互补松弛
互补松弛表示某个不等式约束要么是活跃的，要么对应乘子为零。它揭示了“约束是否真正起作用”与“乘子是否非零”之间的对应关系。
3.3 Fritz John 条件
Fritz John 条件比KKT条件更一般，在缺少某些正则性假设时仍可成立。它引入额外系数，以覆盖更广的退化情况。
3.3.1 与 KKT 条件的关系
当满足合适的资格条件时，Fritz John 条件可以退化为KKT条件。也就是说，KKT可视为更强假设下的简化形式。
3.3.2 退化情形处理
在约束高度相关或梯度失去独立性的情况下，Fritz John 条件能够提供备用分析框架。它对研究异常点和理论边界情形具有重要价值。
3.4 对偶理论
对偶理论通过构造另一个相关问题，从不同角度审视原问题的最优性。对偶问题常用于下界估计、灵敏度分析和算法设计。
3.4.1 拉格朗日对偶问题
拉格朗日对偶问题由原问题的拉格朗日函数推导而来，通过对原变量取下确界构造对偶函数，再在对偶变量上求最大值。
3.4.2 弱对偶与强对偶
弱对偶指出任意对偶可行解都给出原问题最优值的下界；强对偶则说明两者最优值相等。后者通常依赖凸性与资格条件。
3.4.3 对偶间隙
对偶间隙是原问题最优值与对偶问题最优值之间的差。间隙为零时，说明原对偶之间达到完全一致，这在理论和算法停止准则中都很重要。
4 主要算法
约束优化算法大体可分为梯度类、牛顿类、罚函数类、活跃集类、内点法以及启发式方法。不同算法在效率、稳定性和适用范围上各有侧重。
4.1 梯度类方法
梯度类方法通过沿目标下降方向迭代更新变量，并在每一步处理约束限制。它们通常实现简单，适合大规模问题的基础求解。
4.1.1 投影梯度法
投影梯度法先沿负梯度方向移动，再将结果投影回可行域。它特别适合边界简单、投影容易计算的约束集合。
4.1.2 约束梯度下降
约束梯度下降在更新时直接考虑约束结构，避免每步都偏离可行域过远。其设计常与可行方向、线搜索等策略结合。
4.1.3 加速梯度方法
加速梯度方法通过引入动量或外推机制提高收敛速度。对于具有良好结构的问题，它能显著减少迭代次数。
4.2 牛顿类方法
牛顿类方法利用二阶信息构造更精确的局部近似，因此通常具有较快的局部收敛性能。其代价是每步计算和线性代数求解较重。
4.2.1 约束牛顿法
约束牛顿法在牛顿方向计算中显式纳入约束条件，常通过求解KKT线性系统实现。它适合中等规模、结构清晰的光滑问题。
4.2.2 内点牛顿法
内点牛顿法将牛顿框架与屏障思想结合，在可行域内部迭代逼近最优解。它在大规模凸优化中表现突出。
4.3 罚函数与增广拉格朗日法
这类方法通过把约束违反程度转化为目标函数中的惩罚项，使原问题逐步接近无约束形式。它们在工程实现中较为灵活。
4.3.1 外罚函数
外罚函数对违反约束的解施加惩罚，随着惩罚参数增大，解会逐步逼近可行域。其优点是概念简单，但参数调节可能较敏感。
4.3.2 内罚函数
内罚函数要求迭代始终留在可行域内部，通常适合不等式约束。它在逼近边界时可能变得数值上较为困难。
4.3.3 增广拉格朗日法
增广拉格朗日法将乘子更新与罚项结合，兼顾约束满足与数值稳定性。它常被认为是处理复杂约束问题的实用方案。
4.4 活跃集方法
活跃集方法假设最优点附近真正起作用的约束集合相对稳定，并在迭代中逐步识别这些约束。它对稀疏约束结构尤其有效。
4.4.1 活跃约束识别
识别活跃约束是活跃集方法的关键步骤。算法会判断哪些不等式在最优点附近应当取等号，并据此调整搜索方向。
4.4.2 子问题求解
一旦活跃集确定，原问题便可转化为较小规模的等式约束子问题。子问题通常更容易处理，也便于迭代更新。
4.5 内点法
内点法通过始终保持在可行域内部，并逐步逼近边界上的最优解。它在现代大规模优化中应用极广。
4.5.1 中心路径
中心路径描述了随着屏障参数变化，内点解如何平滑地趋近最优解。它为算法设计提供了连续追踪的理论基础。
4.5.2 屏障函数
屏障函数通过在目标中加入趋于无穷大的惩罚，阻止迭代点碰到不可行边界。它使问题在内部保持良好定义。
4.5.3 原始-对偶内点法
原始-对偶内点法同时更新原变量与对偶变量，兼顾可行性与最优性残差。其工程表现稳定，因而成为许多求解器的核心框架。
4.6 启发式与混合算法
启发式算法不一定依赖严格的梯度或凸性假设，常用于复杂、非凸或离散优化问题。混合算法则把不同方法的优点组合起来。
4.6.1 遗传算法
遗传算法模拟群体进化过程，通过选择、交叉和变异搜索较优解。它适合搜索空间复杂、目标函数难以解析处理的问题。
4.6.2 模拟退火
模拟退火利用随机接受较差解的机制避免过早陷入局部最优。其思想来自物理退火过程，常用于组合优化。
4.6.3 局部搜索与全局搜索结合
这类方法通常先用全局策略寻找较优区域，再用局部算法精细改进。它兼顾搜索广度与收敛精度，在实际问题中较常见。
5 特殊类型问题
约束优化中有若干结构特殊、理论成熟的子类。它们不仅单独形成研究方向，也常作为通用方法的测试平台。
5.1 线性规划
线性规划研究线性目标函数在一组线性约束下的最优问题，是最经典、最成熟的优化模型之一。
5.1.1 标准形式
线性规划的标准形式通常是在线性等式与非负约束下最小化或最大化线性函数。这种形式便于理论分析和算法实现。
5.1.2 单纯形法
单纯形法沿可行域的顶点移动，通过逐步改进目标值寻找最优解。尽管理论上存在最坏情形较复杂，但在实践中非常高效。
5.1.3 对偶单纯形法
对偶单纯形法从对偶可行或近似可行的状态出发迭代，常用于重新优化和受扰动后的问题求解。它在某些场景下比原始单纯形法更方便。
5.2 二次规划
二次规划的目标函数为二次型，约束则通常为线性或部分非线性形式。它广泛出现在控制、组合近似和金融建模中。
5.2.1 凸二次规划
若二次项对应的矩阵半正定，则问题为凸二次规划。此时最优解结构良好，可通过KKT条件与高效算法求解。
5.2.2 非凸二次规划
当二次项不再凸时，问题可能出现多个局部最优甚至鞍点。此类问题常需要全局搜索或特殊分解技巧。
5.3 非线性规划
非线性规划是最一般的连续约束优化形式之一，涵盖大量现实模型。其特点是表达能力强，但分析和求解通常更复杂。
5.3.1 光滑非线性规划
光滑非线性规划假设目标函数与约束可微，便于使用梯度、Hessian和KKT理论。许多数值方法都以此类问题为基础。
5.3.2 非光滑非线性规划
非光滑问题中可能出现绝对值、最大值或分段函数等结构。对此类问题，常需要借助次梯度、平滑化或分裂技术。
5.4 半定规划
半定规划以矩阵半正定约束为核心，是凸优化的重要分支。它能自然表达许多矩阵形式的几何和控制问题。
5.4.1 矩阵变量优化
半定规划中的决策变量常是对称矩阵，目标可以是线性矩阵函数。与标量变量优化相比，它更适合处理相关性和协方差结构。
5.4.2 矩阵不等式约束
矩阵不等式通常要求某个矩阵表达式半正定或半负定。它在控制稳定性和系统分析中具有重要地位。
5.5 整数与混合整数规划
这类问题要求部分变量取离散值，因而组合特征明显。它们往往比连续优化更难，但也更贴近实际决策逻辑。
5.5.1 纯整数规划
纯整数规划要求所有决策变量都是整数，常见于计数、选取和排列类问题。其可行解空间离散，搜索复杂度较高。
5.5.2 混合整数规划
混合整数规划同时包含连续变量和整数变量，能够兼顾数量调节与离散选择。它在生产、物流和网络设计中应用广泛。
5.5.3 分支定界法
分支定界法通过不断划分搜索空间并计算上下界来排除不可能优解的区域。它是求解整数规划的重要通用框架。
6 应用领域
约束优化几乎贯穿所有需要做有限资源分配和受限决策的领域。其价值在于把现实问题转化为可计算模型。
6.1 工程优化
工程优化关注在材料、结构、能耗和控制精度等限制下获得最优性能。它常与仿真、实验和建模联合使用。
6.1.1 结构设计
结构设计中常需在强度、重量与成本之间寻找平衡。约束优化可用于梁、桁架、壳体等对象的参数选取。
6.1.2 控制系统优化
控制系统优化研究如何调节控制器参数，使系统稳定、响应快速且能耗较低。相关问题常带有动态约束和鲁棒要求。
6.1.3 机械与材料优化
机械与材料优化涉及零件形状、材料配比和制造参数的联合设计。目标通常是提升性能、延长寿命或降低重量。
6.2 运筹与管理
运筹与管理中的许多问题本质上是资源与流程优化。约束优化为计划制定、调度安排和运输组织提供了统一方法。
6.2.1 生产计划
生产计划需要在产能、库存和交付期限之间作出协调。优化模型可用于确定生产量、批次与时间安排。
6.2.2 供应链优化
供应链优化关注采购、仓储、配送和节点协同。它通常涉及多阶段决策以及成本与服务水平的平衡。
6.2.3 运输与调度
运输与调度问题包括车辆路径、任务排序和班次安排等。它们通常具有离散结构，是整数规划的重要应用场景。
6.3 经济与金融
经济与金融中的优化通常围绕收益、成本、风险和预算约束展开。模型往往要求在不确定条件下做出谨慎选择。
6.3.1 资源分配
资源分配问题关注如何在多个项目或部门之间配置有限资源。约束优化可帮助实现效率与公平之间的平衡。
6.3.2 投资组合优化
投资组合优化试图在预期收益和风险之间找到合适配置。它通常还要考虑资金比例、交易成本和持仓限制。
6.3.3 风险约束模型
风险约束模型把波动性、损失概率或尾部风险纳入优化目标或约束中。这样可使决策更符合稳健性要求。
6.4 机器学习
机器学习中的训练过程常可视为带约束或正则化的优化问题。许多模型性能提升都依赖于良好的优化设计。
6.4.1 正则化问题
正则化通过加入惩罚项限制模型复杂度，防止过拟合。它本质上是一种带结构约束的优化方式。
6.4.2 支持向量机
支持向量机将分类问题转化为带间隔约束的优化问题。其核心是寻找最大化分类边界的超平面。
6.4.3 约束下的模型训练
在某些任务中，训练过程还需满足公平性、稀疏性或资源限制等条件。此时需要把这些要求显式写入优化模型。
7 数值分析与实现
由于大多数约束优化问题难以解析求解，数值分析与实现成为理论落地的关键环节。算法效果通常由收敛性、复杂度和稳定性共同决定。
7.1 收敛性分析
收敛性分析研究算法迭代是否会走向最优解，以及在多快的速度下达到目标。它是评价算法优劣的核心标准之一。
7.1.1 全局收敛
全局收敛通常指从较一般的初始点出发，算法能够逐步逼近某类驻点或最优解。它强调算法的可靠性。
7.1.2 局部收敛
局部收敛关注算法在接近最优解时的行为。很多高阶方法在局部区域内表现出更快的收敛速度。
7.1.3 收敛速度
收敛速度描述误差随迭代次数减少的快慢，常见有线性、超线性和二次收敛等概念。速度越快，算法通常越高效。
7.2 计算复杂度
计算复杂度衡量算法随问题规模增长所需的时间和资源。它帮助判断某类方法在大规模场景中的可行性。
7.2.1 多项式时间算法
多项式时间算法通常被视为可规模化求解的重要标准。在线性规划、部分凸优化中，存在这类理论上高效的方法。
7.2.2 NP 难问题
许多整数优化和非凸问题属于 NP 难问题，意味着不存在已知的普适高效算法。实际中往往依赖近似、分解或启发式策略。
7.3 数值稳定性
数值稳定性关注算法在有限精度计算下是否仍能保持可靠表现。即使理论上正确的方法，也可能因数值误差而失效。
7.3.1 条件数问题
条件数反映问题对输入扰动的敏感程度。条件数过大时，求解过程容易放大误差。
7.3.2 误差传播
迭代过程中舍入误差、截断误差和模型误差都可能逐步传播。稳定的算法设计需要尽量抑制这种累积效应。
7.4 软件与工具
现代约束优化离不开专业软件、建模语言和自动化求解器。它们使复杂模型能够被快速表达和验证。
7.4.1 通用求解器
通用求解器通常支持多种优化类型，能够自动选择适合的算法框架。它们在科研与工业实践中都很常见。
7.4.2 建模语言
建模语言用于以接近数学表达式的方式描述优化问题。它们降低了编码难度，也便于模型修改与复用。
7.4.3 实验验证与调参
实际应用中，算法效果常依赖参数设置、初值选择和停止准则。通过实验验证可以检验模型合理性，并为后续调优提供依据。
8 相关概念与扩展
约束优化与多个优化分支密切相关，许多扩展问题都可视为其自然延伸。理解这些相关概念有助于把握现代优化理论的整体脉络。
8.1 无约束优化
无约束优化是约束优化的基础情形，不需要考虑显式限制。许多约束算法也会通过变换或惩罚将问题转化为近似无约束形式。
8.2 多目标优化
多目标优化同时考虑多个彼此冲突的目标，不再只有单一最优值。其结果通常表现为一组帕累托最优解。
8.3 鲁棒优化
鲁棒优化关注参数不确定时仍能保持性能的解。它强调最坏情况下的可行性与稳定性，适合高不确定环境。
8.4 随机优化
随机优化处理目标函数或约束中含有随机因素的问题。它常用于需求波动、噪声观测和随机过程建模。
8.5 变分不等式
变分不等式研究在约束集合上寻找满足特定不等式关系的点。它与均衡问题、互补问题和优化理论关系密切。
8.6 最优控制
最优控制研究在动力系统约束下如何选择控制输入，使性能指标最优。它可看作带时间演化结构的约束优化。