保证边界点的二次规划求解器？

我有一个问题，我已经表示为具有线性约束的凸二次方程的最小化。问题是我想禁止任何严格内部的点（即，如果它位于可行区域的顶点，我只能找到有用的答案）。保证边界点的二次规划求解器？

我想在不修改目标函数的情况下执行此操作。我已经考虑了几个修改，这将使这是一个没有问题，但他们都有不幸的结果，使程序非凸。

据我估计，我唯一的选择有效的解决方案将是一个求解器，使用有没有人知道一个像样的求解器？

我目前的目标函数是parabol ic圆筒。

2011-09-28 Tim Seguine

我发现这个... [链接]（http://www.cgal.org/Manual/latest/doc_html/cgal_manual/packages.html#Pkg:QPSolver）他们说这是基于单形的泛化方法，这似乎暗示它只返回顶点。它似乎也运行得非常快。有没有人知道这个包的任何内容？例如它是否具有多项式时间保证？也许我应该尝试一下，看看它做了什么。 –

你能找到可行区域的顶点，然后取最小化目标函数的顶点吗？这应该只涉及一些线性代数，然后对目标函数进行有限的评估。

来源

2011-09-28 17:22:18

除顶点数量可以以指数速率增长外。它会很快失去控制。 –

保证边界点的二次规划求解器？

回答

相关问题