C++中是否有二次编程库？

Question

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

那么有人能给我一些关于其他图书馆的建议吗？谢谢.

Answer 1

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));

来自第一个示例的代码。

Answer 2

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

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

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

如果矩阵是不确定的(即它甚至有一个负的特征值)那么问题就是NP难.这意味着任何基于当前可用算法的代码都会有不合理的最坏情况运行时间,即使对于中等大小的问题也是如此.如果您的问题有一些特殊结构,或者您不需要全局最优解决方案,那么您可能没问题.典型的方法是寻找凸松弛.

Answer 3

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

Anycom 在那篇文章中的答案有点神秘，但他的意思是有 LAPACK 绑定可以与 Boost 的线性代数库uBLAS一起使用。

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