使用Numpy在Python中进行二次规划？

Question

我正在将一些 MATLAB 代码翻译成 Python。有一行让我有些困惑：

[q,f_dummy,exitflag, output] = quadprog(H,f,-A,zeros(p*N,1),E,qm,[],[],q0,options);

我查阅了MATLAB的文档，发现quadprog函数被用于优化（尤其是最小化）。

我尝试在Python中寻找一个类似的函数（使用NumPy），但好像没有。

是否有更好的方法将这行代码转换为Python？还是有其他可用的软件包？我需要创建一个完成同样任务的新函数吗？

感谢您的时间和帮助！

- A.Torres

---

你有没有看过scipy.optimize的内部结构？NumPy只提供了基本的处理数字数组的功能；而SciPy在此基础上构建了许多其他数学和科学相关的功能，包括各种优化算法。 - abarnert

如果没有现成的库，你需要使用第三方库。通过快速搜索，有一个叫做quadprog的库，还有一些Python绑定的QuadProg++，当然也可能有其他的库。（但其中一些可能不是基于NumPy构建的。）但到了这个地步，这就变成了一个关于推荐库的问题，而Stack Overflow不幸地不是寻找这些库的地方。 - abarnert

最后一件事：如果你确实需要去搜索，你可能首先想决定是否需要一个与MATLAB使用相同二次规划算法的实现（无论是哪一个；我相信它已经被记录下来了，然后你可以搜索Python实现该算法的内容），或者只是任何适用于你的数据的东西（在这种情况下，你可以尝试很多并看看哪个有效）。 - abarnert

你看过cvxpy吗？它是一个库，可以让你轻松实现凸优化（因此也包括二次规划）。 - linello

Answer 1

我将首先提到，二次规划问题是凸优化问题的子集，而凸优化问题是优化问题的子集。

有多个解决二次规划问题的Python包，特别是：

1. cvxopt - 可以解决各种凸优化问题（包括二次规划问题）。这是之前cvx MATLAB package的Python版本。 2. quadprog - 这专门用于二次规划问题，但似乎没有太多文档。 3. scipy.optimize.minimize - 这是一个非常通用的最小化器，可以解决二次规划问题，以及其他凸和非凸优化问题。

您还可以查看这个stackoverflow帖子的答案，其中有更多详细信息和参考资料。

注意：user1911226答案中的代码片段似乎来自于这篇博客文章： https://scaron.info/blog/quadratic-programming-in-python.html 该文章比较了一些二次规划软件包。我无法评论他们的回答，但他们声称提到了cvxopt解决方案，但代码实际上是quadprog解决方案。

- Lisa

Answer 2

有一个名为CVXOPT的库，其中包含二次规划。

def quadprog_solve_qp(P, q, G=None, h=None, A=None, b=None):
    qp_G = .5 * (P + P.T)   # make sure P is symmetric
    qp_a = -q
    if A is not None:
        qp_C = -numpy.vstack([A, G]).T
        qp_b = -numpy.hstack([b, h])
        meq = A.shape[0]
    else:  # no equality constraint
        qp_C = -G.T
        qp_b = -h
        meq = 0
    return quadprog.solve_qp(qp_G, qp_a, qp_C, qp_b, meq)[0] 

- user1911226

---

正如Lisa所指出的那样，这段代码片段是用于quadprog而不是CVXOPT的。 - Tastalian

Answer 3

OSQP是一款基于ADMM的专业免费QP求解器。我已经针对您的问题调整了OSQP文档演示和qpsolvers存储库中的OSQP调用。

请注意，矩阵H和G应该以CSC格式稀疏表示。以下是脚本：

import numpy as np
import scipy.sparse as spa
import osqp


def quadprog(P, q, G=None, h=None, A=None, b=None,
             initvals=None, verbose=True):
    l = -np.inf * np.ones(len(h))
    if A is not None:
        qp_A = spa.vstack([G, A]).tocsc()
        qp_l = np.hstack([l, b])
        qp_u = np.hstack([h, b])
    else:  # no equality constraint
        qp_A = G
        qp_l = l
        qp_u = h
    model = osqp.OSQP()
    model.setup(P=P, q=q,
                A=qp_A, l=qp_l, u=qp_u, verbose=verbose)
    if initvals is not None:
        model.warm_start(x=initvals)
    results = model.solve()
    return results.x, results.info.status


# Generate problem data
n = 2   # Variables
H = spa.csc_matrix([[4, 1], [1, 2]])
f = np.array([1, 1])
G = spa.csc_matrix([[1, 0], [0, 1]])
h = np.array([0.7, 0.7])
A = spa.csc_matrix([[1, 1]])
b = np.array([1.])

# Initial point
q0 = np.ones(n)

x, status = quadprog(H, f, G, h, A, b, initvals=q0, verbose=True)

- bstellato

---

嗨@bstellao，在执行不等式约束时，我遇到了以下错误。LDL_factor中的ERROR：计算非零元素时KKT矩阵LDL分解出错。问题似乎是非凸的。 osqp_setup中的ERROR：KKT矩阵因子分解。问题似乎是非凸的。 ERROR：工作区分配错误！ - Prateek Jain

Answer 4

您可以使用solve_qp函数，该函数来自qpsolvers。您可以通过pip install qpsolvers[open_source_solvers]安装它以及一组开源求解器的起始套件。然后，您可以将您的代码行替换为以下内容：

from qpsolvers import solve_qp

solver = "proxqp"  # or "osqp", "quadprog", "cvxopt", ...
x = solve_qp(H, f, G, h, A, b, initvals=q_0, solver=solver, **options)

Python中有许多可用的求解器，每个求解器都有其优缺点。请确保尝试使用不同的值作为solver关键字参数，以找到最适合您问题的求解器。

这里是一个基于您的问题和其他评论的独立示例：

import numpy as np

from qpsolvers import solve_qp

H = np.array([[4.0, 1.0], [1.0, 2.0]])
f = np.array([1.0, 1])
G = np.array([[1.0, 0.0], [0.0, 1.0]])
h = np.array([0.7, 0.7])
A = np.array([[1.0, 1.0]])
b = np.array([1.0])
q_0 = np.array([1.0, 1.0])

solver = "cvxopt"  # or "osqp", "proxqp", "quadprog", ...
options = {"verbose": True}
x = solve_qp(H, f, G, h, A, b, initvals=q_0, solver=solver, **options)

- Tastalian