Ctrl+K

linprog(method=’interior-point’)#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)

線性規劃：使用 [4] 的內點法，最小化受限於線性等式和不等式約束的線性目標函數。

版本 1.9.0 開始棄用：method=’interior-point’ 將在 SciPy 1.11.0 中移除。它已被 method=’highs’ 取代，因為後者更快且更穩健。

線性規劃解決以下形式的問題

\[\begin{split}\min_x \ & c^T x \\ \mbox{such that} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

其中 \(x\) 是決策變數的向量；\(c\)、\(b_{ub}\)、\(b_{eq}\)、\(l\) 和 \(u\) 是向量；而 \(A_{ub}\) 和 \(A_{eq}\) 是矩陣。

或者，那是

最小化

c @ x

受限於

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

請注意，預設情況下 lb = 0 且 ub = None，除非使用 bounds 指定。

參數:
c一維陣列

要最小化的線性目標函數的係數。

A_ub二維陣列，選用

不等式約束矩陣。A_ub 的每一列指定了關於 x 的線性不等式約束的係數。

b_ub一維陣列，選用

不等式約束向量。每個元素表示 A_ub @ x 相應值的上限。

A_eq二維陣列，選用

等式約束矩陣。A_eq 的每一列指定了關於 x 的線性等式約束的係數。

b_eq一維陣列，選用

等式約束向量。A_eq @ x 的每個元素必須等於 b_eq 的相應元素。

bounds序列，選用

每個 x 元素的一系列 (min, max) 對，定義該決策變數的最小值和最大值。使用 None 表示沒有界限。預設情況下，界限為 (0, None)（所有決策變數都是非負的）。如果提供單個元組 (min, max)，則 min 和 max 將作為所有決策變數的界限。

method字串

這是 ‘interior-point’ 的特定方法文件。‘highs’、‘highs-ds’、‘highs-ipm’、‘revised simplex’ 和 ‘simplex’ (舊版) 也可用。

callback可調用物件，選用

每次迭代執行一次的回調函數。

返回:
resOptimizeResult

一個 scipy.optimize.OptimizeResult，包含以下欄位

x一維陣列

在滿足約束條件下，使目標函數最小化的決策變數值。

fun浮點數

目標函數 c @ x 的最佳值。

slack一維陣列

鬆弛變數的（名義上為正值）值，b_ub - A_ub @ x。

con一維陣列

等式約束的（名義上為零）殘差，b_eq - A_eq @ x。

success布林值

當演算法成功找到最佳解時為 True。

status整數

表示演算法退出狀態的整數。

0 : 最佳化成功終止。

1 : 達到迭代限制。

2 : 問題似乎不可行。

3 : 問題似乎無界。

4 : 遇到數值困難。

message字串

演算法退出狀態的字串描述。

nit整數

所有階段執行的總迭代次數。

另請參閱

有關其餘參數的文件，請參閱 scipy.optimize.linprog

選項:
——-
maxiter整數 (預設值：1000)

演算法的最大迭代次數。

disp布林值 (預設值：False)

如果要在每次迭代時將最佳化狀態的指標列印到控制台，請設定為 True。

presolve布林值 (預設值：True)

預解嘗試識別微不足道的可行性問題、識別微不足道的無界性，並在將問題發送到主求解器之前簡化問題。通常建議保留預設設定 True；如果要停用預解，請設定為 False。

tol浮點數 (預設值：1e-8)

用於所有終止條件的終止容差；請參閱 [4] 第 4.5 節。

autoscale布林值 (預設值：False)

設定為 True 以自動執行均衡化。如果約束中的數值相差幾個數量級，請考慮使用此選項。

rr布林值 (預設值：True)

設定為 False 以停用自動冗餘移除。

alpha0浮點數 (預設值：0.99995)

Mehrota 的預測校正器搜尋方向的最大步長；請參閱 \(\beta_{3}\) 的 [4] 表 8.1。

beta浮點數 (預設值：0.1)

當未使用 Mehrota 的預測校正器時（不常見），路徑參數 \(\mu\) 的期望縮減量（請參閱 [6]）。

sparse布林值 (預設值：False)

如果要在預解後將問題視為稀疏問題，請設定為 True。如果 A_eq 或 A_ub 是稀疏矩陣，則此選項將自動設定為 True，即使在預解期間，問題也將被視為稀疏問題。如果您的約束矩陣主要包含零，且問題不是非常小（少於約 100 個約束或變數），請考慮設定 True 或提供 A_eq 和 A_ub 作為稀疏矩陣。

lstsq布林值 (預設值：False)

如果預期問題的條件非常差，請設定為 True。除非遇到嚴重的數值困難，否則應始終將其保留為 False。除非您收到警告訊息建議您這樣做，否則請將其保留為預設值。

sym_pos布林值 (預設值：True)

如果預期問題會產生條件良好的對稱正定正規方程式矩陣（幾乎總是如此），請保留 True。除非您收到警告訊息建議您這樣做，否則請將其保留為預設值。

cholesky布林值 (預設值：True)

如果正規方程式要通過顯式 Cholesky 分解，然後進行顯式前向/後向替換來求解，請設定為 True。對於數值表現良好的問題，這通常更快。

pc布林值 (預設值：True)

如果要使用 Mehrota 的預測校正器方法，請保留 True。這幾乎總是（如果不是總是）有益的。

ip布林值 (預設值：False)

如果需要 [4] 第 4.3 節中提出的改進初始點建議，請設定為 True。這是否有益取決於問題。

permc_spec字串 (預設值：‘MMD_AT_PLUS_A’)

（僅在 sparse = True、lstsq = False、sym_pos = True 且沒有 SuiteSparse 的情況下有效。）在演算法的每次迭代中都會分解矩陣。此選項指定如何排列矩陣的列以保持稀疏性。可接受的值為

  • NATURAL：自然排序。

  • MMD_ATA：A^T A 結構上的最小度排序。

  • MMD_AT_PLUS_A：A^T+A 結構上的最小度排序。

  • COLAMD：近似最小度列排序。

此選項可能會影響內點演算法的收斂性；測試不同的值以確定哪個值最適合您的問題。有關更多資訊，請參閱 scipy.sparse.linalg.splu。

unknown_options字典

此特定求解器未使用的可選參數。如果 unknown_options 為非空，則會發出警告，列出所有未使用的選項。

註解

此方法實作了 [4] 中概述的演算法，並結合了 [8] 中的想法和受到 [6] 更簡單方法啟發的結構。

原始對偶路徑追蹤方法從標準形式問題的原始和對偶變數的初始「猜測」開始，並迭代嘗試求解問題的（非線性）Karush-Kuhn-Tucker 條件，並逐漸縮減添加到目標的對數障礙項。此特定實作使用同質自對偶公式，在適用情況下提供不可行性或無界性的證明。

原始和對偶變數的預設初始點是在 [4] 第 4.4 節方程式 8.22 中定義的點。或者（通過設定初始點選項 ip=True），可以根據 [4] 第 4.4 節的額外建議計算替代的（可能改進的）起點。

搜尋方向是使用 Mehrota 提出的預測校正器方法（單一校正）計算的，並在 [4] 第 4.1 節中詳細介紹。（一個潛在的改進是實作 [4] 第 4.2 節中描述的多重校正方法。）實際上，這是通過求解正規方程式來完成的，[4] 第 5.1 節方程式 8.31 和 8.32，從牛頓方程式 [4] 第 5 節方程式 8.25 導出（與 [4] 第 4 節方程式 8.6-8.8 比較）。求解正規方程式而不是直接求解 8.25 的優點是，所涉及的矩陣是對稱正定的，因此可以使用 Cholesky 分解，而不是更昂貴的 LU 分解。

使用預設選項，用於執行分解的求解器取決於第三方軟體的可用性和問題的條件。

對於稠密問題，求解器按以下順序嘗試

  1. scipy.linalg.cho_factor

  2. scipy.linalg.solve，選項 sym_pos=True

  3. scipy.linalg.solve，選項 sym_pos=False

  4. scipy.linalg.lstsq

對於稀疏問題

  1. sksparse.cholmod.cholesky（如果安裝了 scikit-sparse 和 SuiteSparse）

  2. scipy.sparse.linalg.factorized（如果安裝了 scikit-umfpack 和 SuiteSparse）

  3. scipy.sparse.linalg.splu（使用與 SciPy 一起發行的 SuperLU）

  4. scipy.sparse.linalg.lsqr

如果求解器因任何原因失敗，則會按指示的順序嘗試使用更穩健（但速度較慢）的求解器。嘗試、失敗和重新啟動分解可能很耗時，因此如果問題在數值上具有挑戰性，則可以設定選項以繞過失敗的求解器。設定 cholesky=False 會跳到求解器 2，sym_pos=False 會跳到求解器 3，而 lstsq=True 會跳到稀疏和稠密問題的求解器 4。

用於應對以其他方式稀疏問題中的稠密列相關問題的潛在改進在 [4] 第 5.3 節和 [10] 第 4.1-4.2 節中概述；後者還討論了減輕與自由變數的替換方法相關的準確性問題。

在計算搜尋方向後，會計算不會啟動非負性約束的最大可能步長，並應用此步長和單位步長中較小的一個（如 [4] 第 4.1 節中）。[4] 第 4.3 節提出了改進選擇步長的方法。

根據 [4] 第 4.5 節的終止條件測試新點。相同的容差（可以使用 tol 選項設定）用於所有檢查。（一個潛在的改進是公開要獨立設定的不同容差。）如果檢測到最佳性、無界性或不可行性，則求解程序終止；否則它會重複。

雖然頂層 linprog 模組期望表單的問題

最小化

c @ x

受限於

A_ub @ x <= b_ub
A_eq @ x == b_eq
 lb <= x <= ub

其中 lb = 0 且 ub = None，除非在 bounds 中設定。問題會自動轉換為表單

最小化

c @ x

受限於

A @ x == b
    x >= 0

以進行求解。也就是說，原始問題包含等式、上限和變數約束，而特定方法求解器需要等式約束和變數非負性。linprog 通過將簡單界限轉換為上限約束、為不等式約束引入非負鬆弛變數，以及將無界變數表示為兩個非負變數之間的差值，將原始問題轉換為標準形式。問題在報告結果之前會轉換回原始形式。

參考文獻

[4] (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16)

Andersen, Erling D., 和 Knud D. Andersen。“線性規劃的 MOSEK 內點最佳化器：同質演算法的實作。”高效能最佳化。Springer US, 2000. 197-232。

[6] (1,2)

Freund, Robert M. “基於牛頓法的線性規劃的原始對偶內點法。”未發表的課程筆記，2004 年 3 月。於 2017 年 2 月 25 日在 https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf 取得

[8]

Andersen, Erling D., 和 Knud D. Andersen。“線性規劃中的預解。”數學規劃 71.2 (1995): 221-245。

[9]

Bertsimas, Dimitris, 和 J. Tsitsiklis。“線性規劃導論。”Athena Scientific 1 (1997): 997。

[10]

Andersen, Erling D., 等人。大規模線性規劃的內點法實作。HEC/Universite de Geneve, 1996。