如何將二次曲線轉換爲線性曲線？

Question

我有一個優化問題，在目標函數2乘以變量，使模型二次。

我目前使用zimpl來解析模型，glpk來解決它。由於他們不支持二次編程，我需要將其轉換爲MILP。

。第一個變量是實數，在範圍[0，1]中，第二個變量是實數，範圍從0到inf。這一個可以沒有問題是整數。

在目標函數中的重要組成部分看起來是這樣的：

max ... + var1 * var2 + ... 

我曾在約束類似的問題，但他們很容易解決的。

我該如何解決目標函數中的這類問題？

Answer 1

這種形式的模型實際上被稱爲雙線性優化問題。線性化雙線性項的典型方法是通過稱爲McCormick包絡的東西。

考慮變量x和y，你想要x*y在你的最大化問題的目標。如果我們假設x和y由xL <= x <= xU和yL <= y <= yU爲界，那麼我們就可以用w，上限爲數量代替x*y，有以下限制（你可以看到推導here）：

w <= xU*y + x*yL - xU*yL 
w <= x*yU + xL*y - xL*yU 
xL <= x <= xU 
yL <= y <= yL 

注意這些約束在決策變量中都是線性的。麥考密克信封中有相應的下限，但是由於你在最大化它們對你的情況並不重要。如果你想在x*y上加一個更緊的界限，你可以將其中一個變量（我將在這裏使用x）的間隔分割成範圍[xL1，xU1]，[xL2，xU2]，...， [xLn，xUn]，引入輔助連續變量{x1，x2，...，xn}和{w1，w2，...，wn}以及輔助二元變量{z1，z2，...，zn} ，這將指示選擇了哪個x值範圍。約束以上可以被替代（我會告訴索引1的情況下，但你會需要這些對所有的n指數）：

w1 <= xU1*y + x1*yL - xU1*yL*z1 
w1 <= x1*yU + xL1*y - xL1*yU*z1 
xL*z1 <= x1 <= xU*z1 

基本上你將有X1 = 0，W1 < = 0，每當Z1 = 0（即未選擇範圍的這一部分），並且如果z1 = 1（即選擇此範圍的這部分），則將具有正常的McCormick包絡。

最後一步是生成x和w超出這些變量的範圍特定版本。這可以通過以下方式完成：

x = x1 + x2 + ... + xn 
w = w1 + w2 + ... + wn 

n越大，對雙線性項的估計就越準確。然而，n的大數值會影響解決模型的易處理性。

最後一個注意事項 - 您表明您的一個變量無限制，但麥考密克信封需要兩個變量的界限。你應該修正界限，解決問題，如果你的最優值在邊界上，那麼你應該用不同的邊界重新求解。