二次规划（Quadratic Programming, QP） 是一种优化问题，其目标函数是二次函数，约束条件是线性函数。二次规划问题的一般形式如下：

$$\underset{x}{\min }\frac{1}{2}{x}^{T}Qx+c^{T}x$$
$$\text{subject to}Ax\le b$$
$$A_{\text{eq}}x=b_{\text{eq}}$$
$$x_{\text{min}}\le x\le x_{\text{max}}$$

其中：

• $(x)$ 是优化变量（向量）。
• $(Q)$ 是一个对称矩阵（通常为正定或半正定）。
• $(c)$ 是线性项的系数向量。
• $(A)$ 和 (b) $是不等式约束的矩阵和向量。
• $(A_{\text{eq}})$ 和 $(b_{\text{eq}})$ 是等式约束的矩阵和向量。
• $(x_{\text{min}})$ 和 $(x_{\text{max}})$ 是变量的上下界。

---

1. 求解二次规划问题的步骤

（1）问题标准化

将问题转化为标准形式：
$$\underset{x}{\min }\frac{1}{2}{x}^{T}Qx+c^{T}x$$
$$\text{subject to}Ax\le b$$
$$A_{\text{eq}}x=b_{\text{eq}}$$

（2）选择求解方法

根据问题的规模和性质，选择合适的求解方法：

• 小型问题：解析法或通用求解器。
• 大型问题：迭代法或专用求解器。

（3）调用求解器

使用现有的优化工具包或库（如 MATLAB、Python 的 cvxopt 或 quadprog）求解。

（4）验证结果

检查解是否满足约束条件，并验证目标函数值。

---

2. 求解方法

（1）解析法

对于无约束的二次规划问题，最优解可以通过求解线性方程组得到：
$$\nabla f(x)=Qx+c=0⟹x^{\ast }=-Q^{-1}c$$

（2）拉格朗日乘子法

对于有约束的二次规划问题，可以通过拉格朗日乘子法将问题转化为无约束问题：
$$\mathcal{L}(x,\lambda )=\frac{1}{2}{x}^{T}Qx+c^{T}x+{\lambda }^T(Ax-b)$$
然后求解 KKT 条件（Karush-Kuhn-Tucker 条件）：
$${\nabla }_x\mathcal{L}=Qx+c+A^T\lambda =0$$
$$Ax\le b,\lambda \ge 0,{\lambda }^T(Ax-b)=0$$

（3）内点法

内点法是一种迭代算法，通过在可行域内寻找路径逼近最优解。它适用于大规模问题。

（4）有效集法

有效集法通过识别活动约束（即等式约束和紧的不等式约束）来简化问题，适用于中小规模问题。

（5）梯度投影法

梯度投影法通过将梯度方向投影到可行域上来更新解，适用于简单约束问题。

---

3. 常用工具包

（1）MATLAB

MATLAB 提供了 quadprog 函数，可以直接求解二次规划问题：

x = quadprog(Q, c, A, b, Aeq, beq, lb, ub);

（2）Python

• cvxopt：

  from cvxopt import matrix, solvers
  Q = matrix(Q)  # 二次项矩阵
  c = matrix(c)  # 线性项向量
  G = matrix(A)  # 不等式约束矩阵
  h = matrix(b)  # 不等式约束向量
  sol = solvers.qp(Q, c, G, h)
  x = sol['x']
  

• quadprog：

  from quadprog import solve_qp
  x, fval, _, _, _ = solve_qp(Q, c, A, b, Aeq, beq)
  

（3）C++

• Eigen：结合 Eigen 库和二次规划求解器（如 qpOASES）：

  #include <qpOASES.hpp>
  qpOASES::QProblem qp(nVars, nConstraints);
  qp.init(Q.data(), c.data(), A.data(), lb.data(), ub.data(), lbA.data(), ubA.data());
  qp.getPrimalSolution(x.data());
  

---

4. 示例

问题描述

求解以下二次规划问题：
$$\underset{x}{\min }\frac{1}{2}{x}_1^2+x_2^2+x_1{x}_2-2x_1-3x_2$$
$$\text{subject to}{x}_1+x_2\le 1$$
$$x_1\ge 0,x_2\ge 0$$

标准化形式

• 目标函数：
  $$Q=\left[\begin{array}{cc}1& 0.5\\ 0.5& 2\end{array}\right],c=\left[\begin{array}{c}-2\\ -3\end{array}\right]$$
• 约束条件：
  $$A=\left[\begin{array}{cc}1& 1\end{array}\right],b=\left[\begin{array}{c}1\end{array}\right]$$
  $$x_{\text{min}}=\left[\begin{array}{c}0\\ 0\end{array}\right]$$

Python 实现

from cvxopt import matrix, solvers

# 定义矩阵和向量
Q = matrix([[1.0, 0.5], [0.5, 2.0]])
c = matrix([-2.0, -3.0])
G = matrix([[1.0, 1.0], [-1.0, 0.0], [0.0, -1.0]])
h = matrix([1.0, 0.0, 0.0])

# 求解
sol = solvers.qp(Q, c, G, h)
x = sol['x']
print("Optimal solution:", x)

输出

Optimal solution: [ 0.50, 0.50 ]

---

5. 总结

• 二次规划问题的求解方法包括解析法、拉格朗日乘子法、内点法、有效集法等。
• 可以使用 MATLAB、Python、C++ 等工具包快速求解。
• 在实际应用中，选择合适的求解方法和工具包是关键。