linear-algebra - 使用 CGAL 进行二次规划的最大化

我正在使用 CGAL 来解决一些 quadratic programming 问题。

假设我想最小化 x^2 for x 从 -oo (-infinity) 到+oo 。这可以通过执行以下操作轻松解决:

      Program qp (CGAL::SMALLER, false, 0, false, 0);
      qp.set_d(0, 0, 2);

      Solution s = CGAL::solve_quadratic_program(qp, ET());

结果当然会返回 0 。现在假设我想最大化x^2 。为此，我必须最小化 -x^2 。但以下 不 “工作”
在 CGAL 中:

      Program qp (CGAL::SMALLER, false, 0, false, 0);
      qp.set_d(0, 0, -2);

      Solution s = CGAL::solve_quadratic_program(qp, ET());

因为现在矩阵 D = [-2] 不是半正定的(二次规划问题的 API“要求” D 是半正定的)。通过运行上面的代码片段，会返回错误的结果 0 而不是 -oo 。

为了最大化 CGAL 中的 x^2 等目标函数，我应该怎么做？

最佳答案

CGAL 的 documentation 说你的目标函数必须是凸函数的最小化。您正在尝试最小化 -x^2，它不是凸面的 - 所以您不能用 CGAL 做到这一点。

此外，在我链接的文档的第 10.2.2 节中，它说尝试最小化非凸函数甚至可能不会警告您问题是非凸的，而是返回一条消息而不是找到最佳解决方案。也就是说，如果您打算将 CGAL 用于 QP，请确保它是凸二次的，否则您将得到错误的答案。

您可能会考虑使用可以处理非凸非线性优化的求解器。 IPOPT 是开源的，如果您的目标函数和约束是连续可微的两次，它将起作用。 COIN-OR 有几个可能适合您的求解器(请参阅“优化确定性非线性”)。 KNITRO 是一个优秀的商业求解器。

关于linear-algebra - 使用 CGAL 进行二次规划的最大化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13694473/