二次规划

二次规划（QP）是一种特殊类型的数学优化问题。它是优化领域的重要课题，被广泛应用于金融、机器学习和控制系统等许多实际应用中。本指南旨在以简单的方式解释二次规划的概念、数学和应用。

什么是二次规划？

二次规划涉及在线性约束的情况下优化（二次目标函数的最小化或最大化）。让我们详细了解：

• 二次目标函数 是一个数学函数，其中项的最高次幂是平方。其一般形式为：

  f(x) = 0.5 * x t qx + c t x,
              

  其中 Q 是一个 nxn 对称矩阵，c 是一个由 n 个实数组成的向量，x 是一个变量向量。
• 线性约束 是限制变量可取值的约束。其一般形式为：

  a ≤ b,
              

  其中 A 是一个矩阵，x 是一个变量向量，而 b 是一个约束向量。约束可以是相等或不等关系。

数学表示

二次规划问题的标准形式如下：

最小化：f(x) = 0.5 * x T Qx + c T x

满足以下条件：
    axis ≤ b
    x = d
    x ≥ 0
    

这里：

• x T 是向量 x 的转置。
• Q 是确保问题是凸的正半定矩阵。
• A 和 E 分别是表示不等约束和相等约束的矩阵。
• b 和 d 分别是不等约束和相等约束的常量向量。

通过简单示例理解

为了更好地理解，让我们考虑一个简单的二次规划问题。

示例 1：简单的投资组合优化

假设你有两个投资选择，需要决定在每个选项中投资多少。目标是最小化风险（方差），同时实现一定的期望收益。二次函数表示组合的方差（风险）。

假设方差可以通过以下二次方程表示：

最小化：f(x) = 0.5 * (x 1 2 + 2x 1 x 2 + x 2 2 )

满足以下条件：
    x 1 + x 2 = 1 （分配的总和必须为1）
    x 1 ≥ 0
    x 2 ≥ 0
    

问题要求我们找到x 1 和x 2 的值，以便在其总和为1且两者都不为负的情况下最小化风险。

二次规划的可视化

观察二次函数和约束有助于理解问题的解空间：

在上面的可视化中，浅蓝色圆圈表示函数的二次特性。红线表示约束。可行区域（解可能存在的地方）是约束与目标函数可能值的交集。

解决二次规划问题

根据问题的规模和复杂性，可以使用不同的方法解决二次规划问题。以下是一些常用方法：

• 解析方法：适用于小问题，这些方法涉及计算导数并将其设为零以找到最小点。
• 数值方法：对于较大问题，采用数值方法，如活动集方法或内点法。这些方法通过在可行区域中搜索来找到最优解。
• 软件工具：工具如 MATLAB、CVX 和 Python 的 SciPy 库允许轻松设置和解决 QP 问题。

二次规划的应用

由于其高效处理二次关系和约束的能力，二次规划在各种行业和领域中都有应用。

金融

在金融领域，QP 用于投资组合优化，在给定诸如实现期望收益水平等约束条件下，最小化投资组合收益的方差（或风险）。

机器学习

在机器学习中，QP 用于支持向量机的分类任务，帮助找到最大间隔的超平面以分隔不同类别。

控制系统

二次规划也用于模型预测控制（MPC），优化控制输入使其符合系统动态和约束以实现期望性能。

深入的数学理解

为了更形式化地理解二次规划，让我们看看一些数学方面：

凸性

矩阵 Q 确保二次函数是凸的。凸函数具有任何局部最小值也是全局最小值的特殊性质，这简化了问题求解过程。

一个矩阵为正半定 ，必须所有特征值都非负。这一性质确保了凸性。

对偶问题

二次规划也有对偶问题，类似于线性规划。解决对偶问题通常可以提供见解或替代数值解。

二次规划的对偶问题通过对偶变量连接到原始问题，并提供关于原始问题的目标函数的界限。

结论

二次规划是一种在目标函数为二次且受到线性约束时的多才多艺且强大的优化方法。处理大型和复杂问题的能力使其在许多领域中具有不可或缺的价值。通过理解基本概念、应用和解法技巧，可以在实际场景中有效应对二次规划挑战。

评论