问C++中有没有二次编程库？

EN

对于二次编程来说，CGAL看起来很棒。甚至还有a manual。

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

来自the first example的代码。

LAPACK有许多乔列斯基分解例程(他们称之为乔列斯基分解)。有可用于LAPACK的C++包装器(请参阅此，以便question获取列表)。

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

我找到了这个库：OOQP (面向对象的二次编程软件)。如果您向下滚动该页面，您将找到一篇研究论文和一份用户指南。似乎有一个用于该库的C++应用程序接口。希望这能有所帮助。

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

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

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

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