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

Question

我正在使用 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？

Answer 1

CGAL 的 documentation说你的目标函数必须是凸函数的最小化。您正在尝试最小化 -x^2，它不是凸的 - 因此您不能使用 CGAL 执行此操作。

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

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