linprog(method=‘内点’)

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='interior-point', callback=None, options={'maxiter': 1000, 'disp': False, 'presolve': True, 'tol': 1e-08, 'autoscale': False, 'rr': True, 'alpha0': 0.99995, 'beta': 0.1, 'sparse': False, 'lstsq': False, 'sym_pos': True, 'cholesky': True, 'pc': True, 'ip': False, 'permc_spec': 'MMD_AT_PLUS_A'}, x0=None)

线性规划：使用的内点法最小化受线性等式和不等式约束的线性目标函数 [4].

线性规划解决以下形式的问题：

\[\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 。

参数
c一维阵列

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

A_ub二维数组，可选

不等式约束矩阵。每行 A_ub 上的线性不等式约束的系数。 x 。

b_ub一维阵列，可选

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

A_eq二维数组，可选

等式约束矩阵。每行 A_eq 上的线性等式约束的系数。 x 。

b_eq一维阵列，可选

相等约束向量。的每个元素 A_eq @ x 必须等于 b_eq 。

bounds序列，可选

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

method应力

这是“内点”的方法特定文档。 'highs' ， 'highs-ds' ， 'highs-ipm' ， 'revised simplex' ，以及 'simplex' (传统)也可用。

callback可调用，可选

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

退货
resOptimizeResult

A scipy.optimize.OptimizeResult 由以下字段组成：

X一维阵列

在满足约束的同时使目标函数最小化的决策变量的值。

有趣的浮动

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

松弛一维阵列

松弛变量的(标称为正)值， b_ub - A_ub @ x 。

圆锥体一维阵列

等式约束的(标称为零)残差， b_eq - A_eq @ x 。

成功布尔尔

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

状态集成

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

0 ：优化已成功终止。

1 ：已达到迭代限制。

2 问题似乎是不可行的。

3 ：问题似乎是无界的。

4 ：遇到了数字上的困难。

消息应力

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

NIT集成

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

参见

有关参数睡觉的文档，请参阅 scipy.optimize.linprog

选项
maxiterINT(默认值：1000)

算法的最大迭代次数。

disp布尔值(默认值：FALSE)

设置为 True 如果每次迭代都要将优化状态指示器打印到控制台。

presolve布尔值(默认值：TRUE)

在将问题发送到主解算器之前，PResolve试图识别琐碎的不可行之处、识别琐碎的无界性，并简化问题。通常建议保留默认设置 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)

路径参数的所需减少量 \(\mu\) (请参阅 [6]) 当梅赫罗塔的预估-校正器没有使用时(不常见)。

sparse布尔值(默认值：FALSE)

设置为 True 如果要将问题视为预先解决后的稀疏问题。如果有任何一个 A_eq 或 A_ub 是稀疏矩阵，则将自动设置此选项 True ，即使在预解算期间，问题也将被视为稀疏问题。如果约束矩阵大多包含零，并且问题不是很小(少于大约100个约束或变量)，请考虑设置 True 或提供 A_eq 和 A_ub 作为稀疏矩阵。

LSTSQ ：Bool(默认值： False )布尔值(默认值：

设置为 True 如果预计问题的状况会非常糟糕。这应该始终保留 False 除非遇到严重的数字困难。将其保留为默认值，除非您收到另一条建议的警告消息。

sym_pos布尔值(默认值：TRUE)

离开吧 True 如果期望问题产生一个条件良好的对称正定法方程矩阵(几乎总是)。将其保留为默认值，除非您收到另一条建议的警告消息。

cholesky布尔值(默认值：TRUE)

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

pc布尔值(默认值：TRUE)

离开吧 True 如果要使用Mehrota的预测-校正方法。这几乎总是(如果不是总是)有益的。

ip布尔值(默认值：FALSE)

设置为 True 如果由于以下原因而改进的起始点建议 [4] 需要第4.3节。这是否有益取决于问题所在。

permc_spec字符串(默认值：‘MMD_AT_PLUS_A’)

(仅在以下情况下有效 sparse = True ， lstsq = False ， sym_pos = True ，并且没有SuiteSparse。)在算法的每次迭代中对矩阵进行因式分解。此选项指定如何置换矩阵的列以保持稀疏性。可接受的值包括：

  • NATURAL ：自然排序。

  • MMD_ATA A^T，A，A的结构上的最小度序。

  • MMD_AT_PLUS_A A^T+A结构上的最小度序

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

此选项可能会影响内点算法的收敛性；测试不同的值以确定哪个值最适合您的问题。有关详细信息，请参阅 scipy.sparse.linalg.splu 。

unknown_optionsDICT

此特定求解器未使用的可选参数。如果 unknown_options 非空，则会发出警告，列出所有未使用的选项。

注意事项

此方法实现中概述的算法 [4] 带着来自 [8] 和一个结构的灵感来自于更简单的方法 [6].

原始-对偶路径追踪法从标准型问题的原始变量和对偶变量的初始“猜测”开始，迭代地尝试求解问题的(非线性)卡鲁什-库恩-塔克条件，并在目标上添加一个逐渐减小的对数屏障项。此特定实现使用同构的自对偶公式，它在适用的情况下提供不可行性或无界证书。

原始变量和对偶变量的默认起始点是在中定义的起始点 [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] 第四节方程式8.6-8.8)。求解正规方程而不是直接求解8.25的优点是所涉及的矩阵是对称正定的，因此可以使用Cholesky分解而不是更昂贵的LU分解。

使用默认选项时，用于执行因子分解的求解器取决于第三方软件的可用性和问题的条件。

对于密集问题，解算器按以下顺序尝试：

  1. scipy.linalg.cho_factor

  2. scipy.linalg.solve with option sym_pos=True

  3. scipy.linalg.solve with option sym_pos=False

  4. scipy.linalg.lstsq

对于稀疏问题：

  1. sksparse.cholmod.cholesky (如果安装了SCRICKIT-Sparse和SuiteSparse)

  2. scipy.sparse.linalg.factorized (如果安装了SCRICKIT-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)

题名/责任者：Aleason，and Knud D.Andersen，and Knud D.Andersen.“用于线性规划的MOSEK内点优化器：齐次算法的一种实现。”高性能优化。斯普林格美国，2000年。197-232。

6(1,2)

作者：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

题名/责任者：Aleason，and Knud D.Andersen，and Knud D.Andersen.“线性规划中的预求解。”“数学规划”71.2(1995)：221-245。

9

题名/责任者：A.“线性规划导论”“雅典娜科学”1(1997)：997。

10

Andersen，Erling D.等人。大规模线性规划的内点法实现。高等商学院/日内瓦大学，1996年。

上一页

linprog(method=‘simplex’)

下一页

linprog(method=‘修正单纯形’)