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

Question

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

假设我想要使x从-oo(负无穷)到+oo，最小化x^2。这可以通过以下方式轻松解决：

      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 的目标函数？

- insumity

Answer 1

CGAL的文档说你必须最小化一个凸函数。你正在尝试最小化的-x^2不是凸的，因此你不能使用CGAL解决这个问题。

此外，在我提供的文档第10.2.2节中，它说尝试最小化一个非凸函数可能甚至不会警告您该问题是非凸的，而是返回一条消息，表示找到了最优解。也就是说，如果你要使用CGAL进行QP，请确保它是凸二次的，否则你会得到错误的答案。

你可以考虑使用可以处理非凸非线性优化的求解器。IPOPT是开源的，如果你的目标函数和约束满足两次连续可微分性，则可以使用它。COIN-OR有几个求解器（见“Optimization deterministic nonlinear”），可能适合你。 KNITRO是一个出色的商业求解器。

- user327301