保證邊界點的二次規劃求解器？

我有一個問題，我已經表示爲具有線性約束的凸二次方程的最小化。問題是我想禁止任何嚴格內部的點（即，如果它位於可行區域的頂點，我只能找到有用的答案）。保證邊界點的二次規劃求解器？

我想在不修改目標函數的情況下執行此操作。我已經考慮了幾個修改，這將使這是一個沒有問題，但他們都有不幸的結果，使程序非凸。

據我估計，我唯一的選擇有效的解決方案將是一個求解器，使用有沒有人知道一個像樣的求解器？

我目前的目標函數是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

除頂點數量可以以指數速率增長外。它會很快失去控制。 –

保證邊界點的二次規劃求解器？

回答

相關問題