12

我找到的唯一 Google 搜索结果是 QuadProg++，但它无法解决矩阵不适用于 Cholesky 分解的二次规划问题。

那么任何人都可以给我一些关于其他图书馆的建议吗？谢谢。

4

5 回答 5

5

CGAL看起来非常适合二次规划。甚至还有一本手册。

  // by default, we have a nonnegative QP with Ax <= b
  Program qp (CGAL::SMALLER, true, 0, false, 0); 

  // now set the non-default entries: 
  const int X = 0; 
  const int Y = 1;
  qp.set_a(X, 0,  1); qp.set_a(Y, 0, 1); qp.set_b(0, 7);  //  x + y  <= 7
  qp.set_a(X, 1, -1); qp.set_a(Y, 1, 2); qp.set_b(1, 4);  // -x + 2y <= 4
  qp.set_u(Y, true, 4);                                   //       y <= 4
  qp.set_d(X, X, 2); qp.set_d (Y, Y, 8); // !!specify 2D!!    x^2 + 4 y^2
  qp.set_c(Y, -32);                                       // -32y
  qp.set_c0(64);                                          // +64

  // solve the program, using ET as the exact type
  Solution s = CGAL::solve_quadratic_program(qp, ET());
  assert (s.solves_quadratic_program(qp));

来自第一个示例的代码。

于 2012-11-08T13:16:43.100 回答
4

有几个库包含 QP 求解器。有开源和商业选项。现有的答案列出了其中的一些。我想澄清一下矩阵的问题。

我假设您指的是目标矩阵。约束矩阵只需要导致一个非空的可行集。您提到矩阵不适合 Cholesky 分解。由于可以为任何正定矩阵形成 Cholesky 分解，这意味着您的矩阵不是正定矩阵。

如果矩阵是半正定矩阵（即它有一个或多个零特征值），那么问题是一个凸 QP 并且可以有效地解决。然而，许多求解器需要一个明确的目标。由于正半定 QP 的目标具有非平凡的零空间，因此可能有许多解决方案。事实上，这组解决方案甚至可以是无限的。无论如何，数值算法只会给出近似解，因此矩阵的特征值恰好为零并不重要。您可以通过在对角线上添加一个具有小正值的对角矩阵来使矩阵正定。这将基本上选择具有最小 2 范数的解决方案。在实践中，即使矩阵是正定的，这样做也是一个好主意，因为特征值接近零的矩阵通常会导致数值求解器出现问题。添加多少对角线是稳定性和准确性之间的权衡。

如果矩阵是不确定的（即它甚至有一个负特征值），那么问题是 NP 难的。这意味着任何基于当前可用算法的代码都将具有不合理的最坏情况运行时间，即使对于中等规模的问题也是如此。如果你的问题有一些特殊的结构，或者你不需要全局最优解，那么你可能没问题。一种典型的方法是寻找凸松弛。

于 2013-12-30T03:12:09.903 回答
4

LAPACK有许多 Cholesky 分解例程（他们称之为 Cholesky 分解）。有可用于 LAPACK 的 C++ 包装器（请参阅此 SO问题以获取列表）。

Anycom 在该帖子中的回答有点神秘，但他的意思是有 LAPACK 绑定可以与 Boost 的线性代数库uBLAS一起使用。

我找到了这个库：OOQP（面向对象的二次编程软件）。如果您向下滚动该页面，您会找到一份研究论文和一份用户指南。该库似乎有一个 C++ API。希望这可以帮助。

于 2011-11-06T17:46:49.897 回答
2

The subtlety that many of the answers above are missing is whether the matrix is only positive semi-definite (PSD) or is actually indefinite. I haven't used quadprog, but if it fails on a PSD objective matrix, that's a sign of the software's lack of robustness (convex QPs are often PSD, where only strictly convex QPs are positive definite). According to Golub's book "Matrix Computations", Cholesky factorization can be applied to PSD matrices, but numerical stability tends to suffer.

For general nonlinear programming software- both convex and non-convex, the COIN-OR project maintains lists of free and non-free software. One of the solvers they list is IPOPT, which is certainly capable of solving your problem. IPOPT uses an interior-point algorithm, which for small problems, is generally slower than the active-set methods (like quadprog uses). As an alternative, you can formulate your QP as a linear complementarity problem (LCP) and then solve it using an LCP solver. I've found Fackler and Miranda's Matlab code LEMKE to be easily portable to C++.

于 2013-07-25T22:33:53.507 回答
1

如果你愿意付费，你可以使用Mosek。不过，有 30 天免费试用。它通常被认为是可用的最快的求解器（没有引用，抱歉）接口是 C 风格的，尽管显然完美地从 C++ 调用。Mosek 实际上更像是一个圆锥规划求解器，但是如果你不想将你的问题重新表述为一个圆锥问题（Mosek 有很多关于如何做到这一点的文档），你仍然可以使用它的随机梯度下降求解器来解决你的二次公式。

于 2012-11-08T13:28:04.770 回答