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

Question

我正在使用 CGAL 来解决一些二次规划问题。

假设我想最小化x^2从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.

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

score 4 · Accepted Answer

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

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

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

1 回答 1