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{使得} \ & 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

请注意，默认情况下，除非使用 bounds 指定，否则 lb = 0 且 ub = None。

参数:
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 的预测校正搜索方向的最大步长；请参见 [4] 表 8.1 中的 \(\beta_{3}\)。

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 节公式 8.25 推导出的法方程 [4] 第 5.1 节公式 8.31 和 8.32 来实现的（与 [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 节概述了解决在其他稀疏问题中与密集列相关联的问题的潜在改进；后者还讨论了减轻与自由变量的替换方法相关的精度问题。

在计算搜索方向后，计算不会激活非负性约束的最大可能步长，并应用此步长和 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., and Knud D. Andersen. “The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm.” High performance optimization. Springer US, 2000. 197-232.

[6] (1,2)

Freund, Robert M. “Primal-Dual Interior-Point Methods for Linear Programming based on Newton’s Method.” Unpublished Course Notes, March 2004. Available 2/25/2017 at 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., and Knud D. Andersen. “Presolving in linear programming.” Mathematical Programming 71.2 (1995): 221-245.

[9]

Bertsimas, Dimitris, and J. Tsitsiklis. “Introduction to linear programming.” Athena Scientific 1 (1997): 997.

[10]

Andersen, Erling D., et al. Implementation of interior point methods for large scale linear programming. HEC/Universite de Geneve, 1996.