约束优化 约束优化是运筹学中研究在给定限制条件下寻找目标函数最优值的数学分支。我将从基本概念开始，逐步深入其核心理论与方法。 第一步：问题定义与基本概念 约束优化问题的标准形式为： 最小化 f(x) 满足约束条件： g_ i(x) ≤ 0, i = 1,2,...,m (不等式约束) h_ j(x) = 0, j = 1,2,...,p (等式约束) 其中 x ∈ Rⁿ 是决策变量。 关键概念： 可行域：所有满足约束条件的x的集合 全局最优解：在整个可行域上使f(x)最小的点 局部最优解：在某个邻域内使f(x)最小的点 第二步：约束条件的分类与影响 约束条件可分为： 起作用约束（紧约束）：在最优解处取等号的约束 不起作用约束（松约束）：在最优解处严格满足不等式的约束 约束的存在使得最优解可能出现在： 可行域内部（无约束极值点） 可行域边界（约束边界上） 约束曲线的交点上 第三步：一阶必要条件 - KKT条件 Karush-Kuhn-Tucker条件是约束优化的核心理论，扩展了无约束优化的驻点条件。对于局部最优点x* ，存在拉格朗日乘子λ_ i ≥ 0和μ_ j使得： ∇f(x* ) + Σλ_ i∇g_ i(x* ) + Σμ_ j∇h_ j(x* ) = 0 (平稳性) λ_ i g_ i(x* ) = 0, i = 1,...,m (互补松弛性) g_ i(x* ) ≤ 0, h_ j(x* ) = 0 (原始可行性) λ_ i ≥ 0 (对偶可行性) 第四步：约束规格 约束规格保证KKT条件在最优解处成立的重要假设，常见的有： 线性约束规格：所有约束函数都是线性的 线性无关约束规格：在x* 处起作用的约束梯度线性无关 Mangasarian-Fromovitz约束规格：更一般的正则性条件 当约束规格不满足时，即使是最优点也可能不满足KKT条件。 第五步：数值求解方法分类 可行方向法：在迭代过程中始终保持在可行域内，如梯度投影法 罚函数法：将约束违反作为惩罚项加入目标函数，转化为无约束问题 增广拉格朗日法：结合罚函数和拉格朗日乘子的优点，具有更好的收敛性 序列二次规划：每次迭代求解一个二次规划子问题 第六步：实际应用中的特殊结构 针对特定类型的约束结构，有更高效的专门方法： 等式约束优化：可使用消元法或拉格朗日乘子法 边界约束（变量上下界）：投影梯度法特别有效 线性约束：单纯形法和内点法的自然扩展 凸约束：当目标函数和约束都是凸函数时，局部最优即全局最优 理解约束优化需要结合几何直观和代数分析，既要看到约束如何改变搜索空间，也要掌握相应的数学工具来处理这些限制条件。