二次规划 二次规划是运筹学中一类特殊的非线性规划问题，其目标函数是决策变量的二次函数，约束条件是决策变量的线性函数。其标准形式可以写为： 最小化 \( f(x) = \frac{1}{2} x^T Q x + c^T x \) 满足 \( Ax \leq b \) 以及 \( Ex = d \) 其中，\( x \) 是决策变量向量，\( Q \) 是一个 \( n \times n \) 的对称矩阵（称为Hessian矩阵），\( c \) 是一个 \( n \) 维向量，\( A \) 和 \( E \) 是矩阵，\( b \) 和 \( d \) 是相应维度的向量。如果 \( Q \) 是半正定矩阵，则该二次规划问题是一个凸优化问题，其任何局部最优解也是全局最优解。 与线性规划的关系 线性规划可以看作是二次规划的一个特例，即当Hessian矩阵 \( Q \) 为零矩阵时，目标函数就退化为线性函数。因此，二次规划继承了线性规划的一些特性，比如约束条件构成一个多面体（可行域）。但更重要的是，由于目标函数是二次的，其最优解的行为与线性规划有显著不同。在线性规划中，最优解总是出现在可行域（多面体）的顶点上。而在二次规划中，最优解可能出现在顶点上，也可能出现在可行域的边界上，甚至在可行域的内部，这取决于目标函数的形状（由矩阵 \( Q \) 决定）。 最优性条件：KKT条件 对于约束优化问题，一个核心的工具是Karush-Kuhn-Tucker条件。对于凸二次规划问题（即 \( Q \) 半正定），KKT条件不仅是最优解的必要条件，也是充分条件。这意味着，只要找到一个满足KKT条件的点，我们就找到了全局最优解。 KKT条件包含： 原始可行性 ：解必须满足所有原始约束（\( Ax \leq b, Ex = d \)）。 对偶可行性 ：引入的拉格朗日乘子（或称对偶变量）对于不等式约束必须非负。 互补松弛条件 ：对于每个不等式约束，其拉格朗日乘子要么为零，要么该不等式约束是紧的（即取等号）。 梯度条件 ：目标函数的梯度与约束函数梯度的线性组合在最优解处为零，即 \( \nabla f(x) + A^T \lambda + E^T \nu = 0 \)，其中 \( \lambda \) 和 \( \nu \) 是对偶变量。对于二次规划，这个条件具体化为 \( Qx + c + A^T \lambda + E^T \nu = 0 \)。 求解算法 由于KKT条件对于凸二次规划是一个线性方程组（加上互补松弛条件），这催生了一些高效的求解算法。 有效集法 ：这是求解中小规模二次规划问题的经典方法。其核心思想是猜测在最优解处哪些不等式约束是“活跃的”（即取等号），然后将这些活跃约束当作等式约束来处理。这样问题就变成了一个等式约束的二次规划，其解可以通过求解一个线性方程组（来自KKT条件）得到。然后算法检查这个解是否满足原始问题的所有约束以及互补松弛条件。如果不满足，则调整对活跃约束集的猜测，并重复过程，直到找到最优解。 内点法 ：与你已学过的线性规划内点法思想类似，内点法通过引入障碍函数，将约束问题转化为一系列无约束问题来求解。求解过程中，迭代点始终保持在可行域的内部，并沿着一条“中心路径”逼近边界上的最优解。内点法对于大规模稀疏的二次规划问题尤其有效。 梯度投影法 ：这类方法适用于只有边界约束（即变量有上下界）的二次规划。算法沿着目标函数负梯度的方向搜索，当碰到约束边界时，将梯度投影到边界上，然后沿着投影后的方向继续搜索，迭代直至收敛。 应用领域 二次规划的应用极其广泛，因为它能很好地模拟许多现实世界中涉及“成本”或“收益”且存在边际效应（即非线性）的问题。 投资组合优化（马科维茨模型） ：在金融领域，投资者希望在给定风险水平下最大化收益，或在给定收益水平下最小化风险。风险通常用资产收益率的方差来衡量，而方差是权重的二次函数，因此该问题自然表述为一个二次规划问题。 最小二乘估计与回归分析 ：在统计学和机器学习中，普通最小二乘法就是求解一个无约束的二次规划问题（\( Q \) 是正定的）。当参数需要满足某些线性约束（如非负性）时，就变成了约束二次规划。 支持向量机 ：机器学习中强大的分类工具，其核心训练问题可以归结为一个二次规划问题，目标是最大化分类间隔。 工程优化 ：在许多工程设计中，如结构优化、信号处理中的滤波器设计等，目标函数常被建模为二次型，从而使用二次规划求解。