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{这样} \ & 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 指定。

参数:
c1-D 数组

要最小化的线性目标函数的系数。

A_ub2-D 数组，可选

不等式约束矩阵。A_ub 的每一行都指定 x 上一个线性不等式约束的系数。

b_ub1-D 数组，可选

不等式约束向量。每个元素都表示 A_ub @ x 相应值的某个上限。

A_eq2-D 数组，可选

A_eq 的每一行都指定 x 上的一个线性相等性约束的系数。

b_eq1-D 数组，可选

A_eq @ x 的每个元素都必须等于 b_eq 的相应元素。

bounds序列，可选

(min, max) 对的序列，表示 x 中的每个元素，定义该决策变量的最小值和最大值。使用 None 表示没有界限。默认情况下，边界是 (0, None) （所有决策变量都是非负的）。如果提供单个元组 (min, max)，那么 min 和 max 将用作所有决策变量的界限。

methodstr

这是特定于“interior-point”方法的文档。‘highs’、‘highs-ds’、‘highs-ipm’、‘revised simplex’和‘simplex’（旧版）也可用。

callbackcallable，可选

每个迭代执行一次的回调函数。

返回:
resOptimizeResult

包含以下字段的scipy.optimize.OptimizeResult

x1 维数组

在满足约束条件的情况下最小化目标函数的决策变量值。

fun浮点数

目标函数的最优值c ＠ x。

slack1 维数组

松弛变量的（名义上的正向）值，b_ub - A_ub ＠ x。

con1 维数组

相等约束的（名义上的零）残差，b_eq - A_eq ＠ x。

success布尔值

当算法成功找到最优解时为True。

status整数

表示算法退出状态的整数。

0：优化成功终止。

1：达到迭代限制。

2：问题看起来不可行。

3：问题看起来是无限的。

4：遇到数值困难。

message字符串

算法退出状态的字符串描述符。

nit整数

在所有阶段执行的总迭代次数。

另请参阅

有关其余参数的文档，请参阅scipy.optimize.linprog

选项:
————————————————
maxiterint (默认: 1000)

算法的最大迭代次数。

dispbool (默认: False)

如果希望在每次迭代时将优化状态指示符打印到控制台，将其设置为 True。

presolvebool (默认: True)

预处理尝试识别平凡不可行性、识别平凡无界性并在将问题发送到主求解器之前对其进行简化。通常建议保留默认设置 True；如果要禁用预处理，将其设置为 False。

tolfloat (默认: 1e-8)

将用于所有终止准则的终止公差；参见 [4] 第 4.5 节。

autoscalebool (默认: False)

将其设置为 True 以自动执行平衡。如果约束中的数值相差几个数量级，请考虑使用此选项。

rrbool (默认: True)

将其设置为 False 以禁用自动冗余删除。

alpha0float (默认: 0.99995)

Mehrota 预测校正搜索方向的最大步长；参见 [4] 表 8.1，\(\beta_{3}\)。

betafloat (默认: 0.1)

当不使用 Mehrota 预测校正器（不常见）时，路径参数 \(\mu\)（参见 [6]）的期望减少。

sparsebool (默认: False)

如果要在预处理后将问题视为稀疏问题，将其设置为 True。如果 A_eq 或 A_ub 是稀疏矩阵，此选项将自动设置为 True，并且即使在预处理期间，问题也将被视为稀疏问题。如果你的约束矩阵主要包含零且问题不是特别小（小于大约 100 个约束或变量），请考虑设置 True 或提供 A_eq 和 A_ub 作为稀疏矩阵。

lstsqbool (默认: False)

将值设置为 True，如果预计问题条件极差。除非遇到严重的数学难题，否则始终将此选项留为 False。除非您收到建议采取其他措施的警告消息，否则将其保留为默认值。

sym_posbool（默认值：True）

将值留为 True，如果预计问题将产生条件良好的对称正定正规方程矩阵（通常如此）。除非您收到建议采取其他措施的警告消息，否则将其保留为默认值。

choleskybool（默认值：True）

将值设置为 True，如果要通过显式 Cholesky 分解后跟显式前向/后向替换来求解正规方程。对于数值表现良好的问题，这通常更快。

pcbool（默认值：True）

将值留为 True，如果要使用 Mehrota 预测-校正方法。这几乎始终（如果不是始终）有益的。

ipbool（默认值：False）

将值设置为 True，如果需要由于 [4] 第 4.3 节而改善的初始点建议。这是否有益取决于问题。

permc_specstr（默认值：“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_optionsdict

此特定求解器不使用的可选参数。如果 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 节中描述的多重修正方法。）在实践中，这是通过求解由 Newton 等式 [4] 第 5 节等式 8.25 （与 [4] 第 4 节等式 8.6-8.8 进行比较）得出的法向方程 [4] 第 5.1 节等式 8.31 和 8.32 来实现的。求解法向方程而不是直接求解 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 节概述了在稀疏问题中处理与密集列相关的问题的潜在改进方法；后者还讨论了与自由变量替换方法相关联的精度问题的缓解措施。

在计算搜索方向后，会计算不会激活非负约束的最大可能步长，并应用该步长与 1 中较小的一个（如 [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，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/日内瓦大学，1996 年。