我應該使用哪種線性編程軟件包來處理大量約束和「熱啓動」

Question

我有一個「連續」線性編程問題，它涉及在曲線凸空間上最大化線性函數。在典型的LP問題中，凸空間是一個多面體，但在這種情況下，凸空間是分段彎曲的 - 也就是說，它具有面，邊和頂點，但邊不直並且面不平坦。我有一個連續無限的數字，而不是有限數量的線性不等式。我目前正在通過用多面體近似表面來處理這個問題，這意味着將連續無限的約束條件離散爲非常大的有限數量的約束條件。

我也在這種情況下，我想知道答案在小的擾動下如何改變底層問題。因此，我希望能夠根據附近的解決方案爲解算器提供初始條件。我相信這種能力被稱爲「熱情開始」。

有人可以幫助我區分不同的LP包嗎？我不太關心用戶友好性，因爲速度（對於大量的約束），高精度算術和熱啓動。

謝謝！

編輯：從與問題回答者的對話到目前爲止，我應該更清楚我想解決的問題。簡化版本如下：

我有一個單一的實變量y的固定函數f_i（y）。我想找到X_I（I = 1，...，N），該最小化\ sum_ {I = 1}^N X_I f_i（0），受約束：

• \ sum_ {I = 1 }^N X_I f_i（1）= 1，和
• \ sum_ {I = 1}^N X_I f_i（Y）> = 0對所有Y> 2

更簡潔地說，如果我們定義函數F（y）= \ sum_ {i = 1}^N x_i f_i（y），那麼我想在F（1）= 1且F（y）爲正的條件下使F整個區間[2，無窮大）。請注意，後者的積極性條件實際上是x_i上的線性約束的數量，每個y都有一個線性約束。你可以把y看作一個標籤 - 它不是一個優化變量。具體的y_0將我限制在x_i空間中的半空間F（y_0）> = 0。當我在2和無窮之間改變y_0時，這些半空間不斷變化，雕刻出一個彎曲的凸形。這種形狀的幾何形狀依賴於（並且以複雜的方式）在函數f_i上。

Answer 1

• 至於LP求解器的建議，最好的兩個是Gurobi和CPLEX（谷歌他們）。它們對學術用戶是免費的，並且能夠解決大規模問題。我相信他們擁有你需要的所有功能。您可以從影子價格（即擾動）獲得敏感度信息（即擾動）。拉格朗日乘子）。

• 但我對你最初的問題更感興趣。據我瞭解，它看起來像這樣：

設S = {1,2，...，N}其中N是函數的總數。 y是一個標量。 f_ {i}：R^{1} - > R^{1}。

minimize sum{i in S} (x_{i} * f_{i}(0)) 
    x_{i} 
s.t. 
(1) sum {i in S} x_{i} * f_{i}(1) = 1 
(2) sum {i in S} x_{i} * f_{i}(y) >= 0 for all y in (2,inf] 

• 它只是在我看來，你可能會想嘗試解決這個問題作爲一個凸NLP而非LP。像IPOPT這樣的大規模內部點NLP求解器應該能夠輕鬆處理這些問題。我強烈推薦嘗試IPOPT http://www.coin-or.org/Ipopt

• 從數值的角度來看：對於凸問題，內點解算器不需要熱啓動;你不必擔心活動組合的循環。你所說的「熱啓動」實際上是擾亂了解決方案 - 這更類似於敏感性分析。按照優化的說法，熱啓動通常意味着爲求解器提供初始猜測 - 解算器將採取這種猜測並最終得到相同的解決方案，這實際上並不是你想要的。唯一的例外是，如果活動集隨着不同的初始猜測而改變 - 但對於具有獨特最佳值的凸問題，這不會發生。

如果您需要更多信息，我很樂意提供。

編輯：

很抱歉的非標符號 - 我希望我能像MathOverflow.net鍵入乳膠。 （順便說一下，你可能會嘗試發佈這裏 - 我認爲那裏的數學家會對這個問題感興趣）

現在我看到關於「y> 2」。它不是一個真正的優化約束，而是一個定義空間的區間（我上面編輯了我的描述）。我的錯。我想知道你是否能以某種方式將問題從無限轉變爲有限的問題？我現在想不出任何事情，但我只是想知道這是否可能。我猜你選擇了一個非常大的數字來表示inf和一個精細的離散化網格Oooo棘手，我想離散化可能是離散化的你最好的選擇也許那些做真正的分析的人有想法

我見過類似的問題，涉及Lyapunov函數需要在凸包內的每個點執行一個屬性。有限的。

Answer 2

您不應該使用LP解算器並自己進行離散化。你可以用一個體面的一般凸解算器做得更好。請查看，例如cvxopt。這可以處理約束條件中的各種不同功能，或者允許您編寫自己的約束。這比自己嘗試線性化要好得多。

至於熱啓動，對於LP而言，比一般凸面程序更有意義。如果您自己手動編寫整個算法，熱啓動可能會有用，但通常仍需要幾個牛頓步驟，所以收益並不那麼重要。熱啓動的大部分好處都來自於活動集方法，它們大多隻用於LP。

Answer 3

我遇到了類似的問題。我搜索了網頁，發現這個問題可能被歸類爲「半無限」問題。MATLAB有解決這類問題的工具（函數「fseminf」）。但我沒有詳細檢查。當然，人們遇到了這樣的問題。