WOLFRAM

Wolfram 语言与系统参考资料中心

线性优化

引言线性优化问题的应用实例
LinearOptimization 函数线性优化的算法
例子参考文献
导入大型数据集和求解大规模问题

引言

线性优化问题被定义为目标函数和约束条件都是线性的问题.

Wolfram 语言收集了大量的算法来解决实变量的线性优化问题，这些算法都可通过 LinearOptimization、FindMinimum、FindMaximum、NMinimize、NMaximize、Minimize 和 Maximize 调用执行. LinearOptimization 对各种线性优化算法提供直接的支持，并提供了最灵活的方式来指定使用哪个算法，而且能够最有效地解决大规模问题. FindMinimum、FindMaximum、NMinimize、NMaximize、Minimize 和 Maximize 对求解等式和不等式形式的线性优化问题更为方便.     

这里求解一个线性优化问题 使用 Minimize：
Wolfram Language code: Minimize[{x + 2 y, -5x + y == 7 && x + y ≥ 26 && x ≥ 3 && y ≥ 4}, {x, y}]
这里使用 NMinimize 求解相同的问题. NMinimize 返回一个机器精度的解：
Wolfram Language code: NMinimize[{x + 2 y, -5x + y == 7 && x + y ≥ 26 && x ≥ 3 && y ≥ 4}, {x, y}]
这里使用 LinearOptimization 求解相同的问题：
Wolfram Language code: LinearOptimization[x + 2y, {-5x + y == 7, x + y >= 26, x >= 3, y >= 4}, {x, y}]

LinearOptimization 函数

LinearOptimization 是线性优化问题的主要函数，它能够最灵活地指定应该使用哪一个函数，并且对于解决大规模问题是最有效的.     

线性优化求可解决原始问题的 ：

最小化
受限于约束条件
其中

下面给出了线性优化的 Lagrangian 对偶问题：

最大化
受限于约束条件
其中

我们可以使用下面的选项：

选项名
默认值
MethodAutomatic解决线性优化问题采用的方法
ToleranceAutomatic收敛容差
MaxIterationsAutomatic使用的最大迭代次数
PerformanceGoal$PerformanceGoal优化的目标
WorkingPrecisionAutomatic内部计算使用的精度

LinearOptimization 的选项

Method 选项用来指定求解线性优化问题所使用的算法. 可能的值包括 Automatic、"Simplex"、"RevisedSimplex" 、"InteriorPoint"、 "CLP"、"MOSEK" 和 "Gurobi". 默认值是 Automatic，可以根据问题的大小和精度需要从其他方法中自动选择合适的算法.

Tolerance 选项可以用来指定收敛容差的大小.

当设置为 WorkingPrecision->Automatic 时，精度是从输入参数的精度自动获取的，除非指定的方法仅适用于机器精度，在这种情况下使用机器精度.

可通过 LinearOptimization 函数获取许多解的属性：

"PrimalMinimizer"{,…}一个最小化目标函数的变量值列表
"PrimalMinimizerRules"{v1,…}最小化 的变量值 vars={v1,…}
"PrimalMinimizerVector"x*最小化 的向量
"PrimalMinimumValue"最小值
"DualMaximizer"最大化
的向量
"DualMaximumValue"对偶最大值
"DualityGap"对偶值和原始最优值之间的差（由于强对偶性，差应为 0）
"Slack"
约束松弛向量
"ConstraintSensitivity"
 对约束条件扰动的敏感性
"ObjectiveVector"
线性目标向量
"LinearInequalityConstraints"线性不等式约束矩阵和向量
"LinearEqualityConstraints"线性等式约束矩阵和向量
{"prop1","prop2",...}解的几个属性

LinearOptimization 的解的属性.

例子

内点法和单纯形法和/或修正单纯形法的区别

单纯形法和修正单纯形法通过以下方法解决线性优化问题: 沿着约束条件所定义的多面体边缘移动，从一个顶点到达另一个顶点，以使得目标函数值逐渐减小，直至达到最小值. Wolfram 语言通过稠密线性代数实现单纯形法和修正单纯形法. 这种实现方法的独特之处在于它有可能解决精确/扩展精度问题. 因此，这些方法对于需要非机器精度结果的小规模问题或者当我们期待得到一个在顶点上的解时更为适用.

笼统地说，线性优化的内点算法是从约束条件定义的多面体的内部依次迭代的. 它们可以非常快地接近问题的解，但是与单纯形法/修正单纯形法不同的是，他们不能精确地找到解. Wolfram 语言利用机器精度稀疏线性代数执行内点法. 因此，对于大规模机器精度线性优化问题，内点法更为有效，更为适用.

这里求解一个具有多个解的线性优化问题（任何在 {0,1} 和 {1,0} 之间的线段上的点是一个解）；内点算法给我们提供了一个位于解集中点的一个解：
Wolfram Language code: LinearOptimization[-x - y, x + y <= 1, {x, y}, Method -> "InteriorPoint"]
利用 Simplex 或者 RevisedSimplex，则给出一个在解集边界上的解.     
Wolfram Language code: LinearOptimization[-x - y, x + y <= 1, {x, y}, Method -> "RevisedSimplex"]
这里表明对于下面的具有 200 个变量的随机稀疏线性优化问题，内点法要快的多，并且产生差不多相同的最优值：
Wolfram Language code: m = SparseArray[RandomChoice[{0.1, 0.9} -> {1., 0.}, {50, 200}]]; xi = LinearOptimization[Range[200].x, {m.x0, x0}, x, "PrimalMinimizerVector", Method -> "InteriorPoint"]; //Timing
Wolfram Language code: xs = LinearOptimization[Range[200].x, {m.x0, x0}, x, "PrimalMinimizerVector", Method -> "Simplex"]; //Timing
Wolfram Language code: Range[200].(xi - xs)

寻找对偶变量

对于一般线性优化问题

其相应的对偶问题是

对于一些应用问题来说，同时知道这两个问题的解是很有用的.

下列表格给出原始问题和对偶问题的解之间的关系.     

如果原始问题是
那么对偶问题是
可行可行
无界不可行或者无界
不可行无界或者不可行

当这两个问题都是可行的时候，(P) 和 (D) 的最优值是相同的，并且下面的补充条件对于原始问题的解 和对偶问题的解 是成立的.

可通过解的 "DualMaximizer" 属性从 LinearOptimization 获取对偶最大值点.

这里求解原问题 以及对偶问题
Wolfram Language code: primal = LinearOptimization[3x + 4y, {x + 2y >= 5, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, {"PrimalMinimizerRules", "DualMaximizer"}]
求解对偶问题来确认结果：
Wolfram Language code: dual = LinearOptimization[-(5Subscript[λ, 1] + Subscript[λ, 2] - 4Subscript[λ, 3] + Subscript[λ, 4] - 4Subscript[λ, 5]), {Subscript[λ, 1] + Subscript[λ, 2] - Subscript[λ, 3] == 3, 2Subscript[λ, 1] + Subscript[λ, 4] - Subscript[λ, 5] == 4, Subscript[λ, 1] >= 0, Subscript[λ, 2] >= 0, Subscript[λ, 3] >= 0, Subscript[λ, 4] >= 0, Subscript[λ, 5] >= 0}, {Subscript[λ, 1], Subscript[λ, 2], Subscript[λ, 3], Subscript[λ, 4], Subscript[λ, 5]}]
这里证实了原始问题和对偶问题给出了相同的目标函数值：
Wolfram Language code: {3, 4}.{x, y} /. primal[[1]]
Wolfram Language code: {5, 1, -4, 1, -4}.{Subscript[λ, 1], Subscript[λ, 2], Subscript[λ, 3], Subscript[λ, 4], Subscript[λ, 5]} /. dual
用解的属性直接确认原始和对偶目标函数值：
Wolfram Language code: LinearOptimization[3x + 4y, {x + 2y >= 5, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, {"PrimalMinimumValue", "DualMaximumValue"}]
约束条件 的对偶是 ，这意味着如果约束条件右侧增加一个单位，目标函数将增加两个单位. 这可以通过对约束条件的右侧添加 0.001 的扰动来确认：
Wolfram Language code: pval = LinearOptimization[3x + 4y, {x + 2y >= 5 + 0.001, 1 <= x <= 4, 1 <= y <= 4}, {x, y}, "PrimalMinimumValue"]
的确，目标函数值增加了相应数额的两倍：
Wolfram Language code: pval - {3, 4}.{x, y} /. primal[[1]]
用 "ConstraintSensitivity" 属性来查看扰动 对约束条件 的影响：
Wolfram Language code: {a, b} = {{{1, 2}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}, {-5, -1, 4, -1, 4}}; {p^ * , {Subscript[s, λ], Subscript[s, ν]}} = LinearOptimization[3x + 4y, a.{x, y} + b0, {x, y}, {"PrimalMinimumValue", "ConstraintSensitivity"}]
Wolfram Language code: p^ * + Subscript[s, λ].{-0.001, 0, 0, 0, 0}

处理内点法中的不可行性和无界性

原始-对偶内点法是为可行问题而设计的；对于不可行/无界问题，它是发散的，而在目前的执行过程中，我们很难查明发散是由于不可行性，还是由于无界性.

一种启发式的方法捕捉到了不可行/无界问题，并且发布一个适当的信息.     
Wolfram Language code: LinearOptimization[x + y, {x + y <= 1, x + y >= 2}, {x, y}, Method -> "InteriorPoint"]
有时候，该启发式的方法不能肯定地告诉我们一个问题是否是不可行的或者无界的.     
Wolfram Language code: LinearOptimization[-x - y, {x + y >= 1, x >= 0, y >= 0}, {x, y}, Method -> "InteriorPoint"]
使用提示中所建议的 Simplex 单纯形法表明，该问题是无界的：
Wolfram Language code: LinearOptimization[-x - y, {x + y >= 1, x >= 0, y >= 0}, {x, y}, Method -> "Simplex"]

"InteriorPoint" 的方法选项

"TreatDenseColumn" 是 "InteriorPoint" 的一个方法选项，它决定对稠密列是否要分别处理. 稠密列指的是具有许多非零元素的约束矩阵的列. 在默认情况下，该方法选项的值为 Automatic，此时分别处理稠密列是分别处理的.

包含稠密列的大型问题通常受益于对稠密列的处理.     
Wolfram Language code: A = SparseArray[{{i_, i_} -> 1., {i_, 1} -> 1.}, {300, 300}]; c = Table[1, {300}]; b = A.Range[300];
Wolfram Language code: {x1 = LinearOptimization[c.x, {A.xb, x0}, x, "PrimalMinimizerVector", Method -> "InteriorPoint"]; // Timing, x2 = LinearOptimization[c.x, {A.xb, x0}, x, "PrimalMinimizerVector", Method -> {"InteriorPoint", "TreatDenseColumns" -> False}];//Timing}
Wolfram Language code: x1.c - x2.c

导入大型数据集和求解大规模问题

一个用于记录线性优化问题的常用格式是数学规划系统 (MPS) 格式. 这是一个包含若干章节的文本格式.

以方程形式导入 MPS 格式文件

Wolfram 语言可以导入 MPS 格式的文件. 默认情况下，MPS 数据的 Import 返回一个方程形式的线性优化问题，这样就可以通过使用 LinearOptimization、Minimize 或者 NMinimize 求解.     

这里求解 MPS 文件 "afiro.mps" 指定的线性优化问题.     
Wolfram Language code: {eqns, vars} = Import["Optimization/Data/afiro.mps"]
Wolfram Language code: LinearOptimization[eqns[[1]], Rest[eqns], vars]

大规模问题：以矩阵和向量形式导入

对于大规模问题，导入 MPS 数据文件并用矩阵和向量表示线性优化问题，然后用 LinearOptimization 求解更有效.

这里表明对于 MPS 格式的数据，可以导入下面三个元素：
Wolfram Language code: Import["Optimization/Data/ganges.mps", "Elements"]
这里导入 "ganges" 问题，其中有 1309 个约束条件和 1681 个变量：
Wolfram Language code: {c, linIneq, linEq} = Import["Optimization/Data/ganges.mps", "LinearOptimizationData"];
这里求解该问题并且找到最优值：
Wolfram Language code: x = LinearOptimization[c, linIneq, linEq];
Wolfram Language code: c.x
使用 "ConstraintMatrix" 可以用来单独地获得稀疏矩阵：
Wolfram Language code: p = Import["Optimization/Data/ganges.mps", "ConstraintMatrix"]

自由格式的 MPS 文件

标准格式的 MPS 文件采用一个固定的格式，其中每个域占有一个严格固定的字符位置. 然而，一些建模系统以自由格式输出 MPS 文件，其中每个域自由地放置. 对于这种文件，对 Import 可以选用选项"FreeFormat"->True.

该字符串描述了一个自由格式的 MPS 文件：
Wolfram Language code: txt = "NAME TESTPROB ROWS N COST L CON1 G CON2 E CON3 COLUMNS x COST 1 CON1 2 x CON2 3 y COST 4 CON1 5 y CON3 6 Z COST 7 CON2 8 Z CON3 9 RHS RHS1 CON1 10 CON2 11 RHS1 CON3 12 BOUNDS UP BND1 x 13 LO BND1 y 14 UP BND1 y 15 ENDATA ";
这里获得一个临时文件名，并且把字符串导出到该文件中：
Wolfram Language code: file = Close[OpenWrite[]]; Export[file, txt, "Text"];
这里采用 "FreeFormat"->True 选项导入该文件：
Wolfram Language code: Import[file, "MPS", "FreeFormat" -> True]

线性优化测试问题

通过 ExampleData 函数，所有 NetLib 线性优化测试问题都可以被访问.     

下面给出了 Netlib 集里的所有问题：
Wolfram Language code: ExampleData["LinearOptimization"]
这里导入 "afiro" 问题并且求解该问题.     
Wolfram Language code: afiroData = ExampleData[{"LinearOptimization", "afiro"}]
Wolfram Language code: LinearOptimization@@afiroData
这里显示了对 "afiro" 问题可以导入的其他属性.     
Wolfram Language code: ExampleData[{"LinearOptimization", "afiro"}, "Properties"]
下面导入等式形式的 "afiro" 问题，可直接用来求解问题：
Wolfram Language code: afiroEqns = ExampleData[{"LinearOptimization", "afiro"}, "Equations"]
Wolfram Language code: LinearOptimization[Sequence@@afiroEqns[[1]], afiroEqns[[2]]]

线性优化问题的应用实例

L1-范数最小化

求解 最小化问题是可能的

方法是把系统转换成线性优化问题

定义输入和输出点：
Wolfram Language code: {input, output} = IconizedObject[«Block»]; dataplot = ListPlot[output, PlotRange -> All]
拟合数据：
Wolfram Language code: Clear[a, b, s, x]; res = LinearOptimization[Total[s], {a == input, b == output, -sa.x - bs}, {x, s}]
下面绘制该直线，并表明它对异常值是稳健的：
Wolfram Language code: Show[ dataplot, Plot[Evaluate[x.{1, t} /. res], {t, 1, 30}]]
与用 LeastSquares 获取的拟合相比较：
Wolfram Language code: line = Fit[output, {1, t}, t]
Wolfram Language code: Show[ dataplot, Plot[Evaluate[{x.{1, t} /. res, line}], {t, 1, 30}]]

一个最优桁架的设计

这个例子是从 [2] 中引入的. 目的是要设计一个锚，使用尽可能少的材料来支撑负载.     

11.gif

这个问题可以通过离散化并用节点和链路对其进行模拟来建模. 建模过程通过下面的图标显示. 在此一个具有7×10个节点的网格被产生. 每个节点通过链路与所有其他曼哈顿距离小于或等于三的节点链接. 三个红色节点假设固定在墙上，而在所有其他节点上，压力和张力必须平衡.     

12.gif

每个链路代表一个具有一定粗细的刚性棒，其重量和它上面的力以及它的长度成正比. 我们的目的是最小化使用的材料总量，即:

因此从数学理论上看，这是一个线性约束极小化问题，其目标函数是线性函数绝对值的和.

目标函数中绝对值 可以通过把 分成压力和张力的组合来代替，其中每个项都是非负的. 因此假设 是链路的集合， 是节点的集合， 是节点 和 之间的链路长度，而 和 是链路上的压力和张力；那么上述模型可以被转化为一个线性优化问题.

选择几个将桁架固定在墙上的特定位置.
Wolfram Language code: anchorPoints = Thread[{0, Range[-3, 3]}];
施加负载的位置在桁架的末端.
Wolfram Language code: forcingPoint = {30, 0};
可以用链路和节点对桁架进行建模. 每个节点通过链路连接到相邻节点. 下面给出了连接模式：
Wolfram Language code: connectivityPattern = Partition[Flatten[{Thread[{{-1, 1}, 0}], Outer[List, Range[-3, 3], {-1, 1}], Outer[List, {-3, -1, 1, 3}, {-2, 2}], Outer[List, {-2, -1, 1, 2}, {-3, 3}]}], 2];
将候选节点放在矩形点阵中.
Wolfram Language code: bounds = {{0, 30}, {-10, 10}}; nodes = Flatten[Outer[List, Sequence@@Apply[Range, bounds, 1]], 1]; np = Length[nodes];
可视化节点位置、锚点位置、施加力的位置以及桁架中部单个节点的连接.
Wolfram Language code: mid = Round[Map[Mean, bounds]]; cmid = Map[Plus[mid, #]&, connectivityPattern]; Graphics[{Point[nodes], Blue, Map[Circle[#, .5]&, anchorPoints], Red, Arrow[{forcingPoint, forcingPoint - {0, 2}}], Map[Line[{mid, #}]&, cmid]}, ImageSize -> Medium]
每个节点与一个唯一索引关联. Association 提供了一个可高效进行查找的表格.
Wolfram Language code: toIndex = AssociationThread[nodes -> Range[np]]; fromIndex = AssociationThread[Range[np] -> nodes];
找到与锚点和着力点相关联的索引.
Wolfram Language code: anchorPointIndex = Lookup[toIndex, anchorPoints]; forcePointIndex = toIndex[forcingPoint];
构建一个函数，提供对于给定的连接模式点阵中点的连接.
Wolfram Language code: connectivity[index_, pat_] := Module[{point = fromIndex[index], connectedPoints, connectedIndexes}, connectedPoints = Map[Plus[point, #]&, pat]; connectedIndexes = Cases[Map[toIndex, connectedPoints], Except[_Missing]]; Thread[{index, Sort[connectedIndexes]}]];
用 描述一组链路. 用之前定义的模式构建一个节点的稀疏连接矩阵 ，其中，如果链路 则 ，否则 .
Wolfram Language code: nodePosition = Join@@Map[connectivity[#, connectivityPattern]&, Range[np]]; nodeConnectivityMatrix = SparseArray[nodePosition -> 1, {np, np}]
Wolfram Language code: links = DeleteDuplicates[Map[Sort, nodeConnectivityMatrix["NonzeroPositions"]]]; nlinks = Length[links];
描述 中的链路的便捷方式是有一个链路的索引.
Wolfram Language code: linkToIndex = AssociationThread[links -> Range[nlinks]];
目标是最小化 ，其中 是节点 和 之间的长度， 是由 形成的链路在其末端结点上施加的力.
Wolfram Language code: links = DeleteDuplicates[Map[Sort, nodeConnectivityMatrix["NonzeroPositions"]]]; nlinks = Length[links]; linkLengths = Map[EuclideanDistance@@nodes[[#]]&, links];
函数 是非线性的，但可以通过引入 表示为线性函数，使得 ， . 目标函数是：
Wolfram Language code: objective = linkLengths.(xp + xm);
在除施力点之外的每个节点处没有施加外力.
Wolfram Language code: nodeForce = ConstantArray[0., {np, 2}];
在施力点处，施加垂直向下的单位力.
Wolfram Language code: nodeForce[[forcePointIndex]] = {0., -1.};
在每个非锚定节点 处，要处于力平衡状态 ，其中 是节点 的位置.
Wolfram Language code: columns = nodeConnectivityMatrix["MatrixColumns"]; linkToIndex = AssociationThread[links -> Range[nlinks]]; linkConstraints = Table[ mi = columns[[i]]; vii = Map[Sort, Thread[{i, mi}]]; vi = Map[Indexed[xp, linkToIndex[#]] - Indexed[xm, linkToIndex[#]]&, vii]; s = Map[(nodes[[#]] - nodes[[i]])&, mi]; lhs = Total[Map[# / Norm[#]&, s] * vi]; Thread[lhs == nodeForce[[i]]] , {i, Complement[Range[np], anchorPointIndex]}];
最终的约束条件为：
Wolfram Language code: constraints = Join[Flatten[linkConstraints], {xp0, xm0}];
对所得系统进行求解.
Wolfram Language code: res = LinearOptimization[objective, constraints, {xp∈Vectors[nlinks], xm∈Vectors[nlinks]}];
可视化最佳桁架，用蓝色系表示链路的压缩，用红色系表示链路的扩展.
Wolfram Language code: totalf = (xp - xm) /. res; maxForce = Max[Abs[totalf]]; index = Pick[Range[nlinks], Thread[Abs[totalf] / maxForce ≥ 0.001], True]; allLinks = Table[ f = totalf[[i]] / maxForce; vlink = nodes[[links[[i]]]]; {Hue[(1 + f) / 2.5], Thickness[.025 Abs[f]], Line[vlink]}, {i, index}]; Graphics[{allLinks, {PointSize[0.02], Point[anchorPoints]}, {EdgeForm[StandardGray], FaceForm[None], Rectangle[{-1, -10}, {0.01, 10}]}}, ImageSize -> Medium]

线性优化的算法

单纯形法和修正单纯形法

单纯形法和修正单纯形法通过以下方法求解线性优化问题：先在约束条件所定义的多面体的一个顶点构造一个可行解，然后沿着该多面体边，从一个顶点移动到另一个顶点，以使得我们的目标函数值逐渐减小，直至达到最小值.     

虽然单纯形法和修正单纯形法的稀疏实现方法在实践上很有效，并且能够保证找到全局最优解，该算法有一个很差的最坏情况下的行为表现：即有可能会建立这样一个线性优化模型，使得单纯形法和修正单纯形法的步骤数目与问题大小呈指数关系.

Wolfram 语言通过稠密线性代数实现单纯形法和修正单纯形法. 这种实现方法的独特之处在于它有可能可以解决精确/扩展精度问题. 因此，这些方法对于需要非机器精度结果的小规模问题更为适用.

这里我们建立一个具有 20 个约束条件和 200 个变量的随机线性优化问题：
Wolfram Language code: SeedRandom[123]; {m, n} = {20, 100}; c = RandomInteger[{1, 10}, n]; A = RandomInteger[{-100, 100}, {m, n}]; b = A.ConstantArray[1, n]; constraints = {A.xb, -10x10};
下面求解该问题. 通常情况下，如果线性优化问题的变量数目远多于约束数目，修正单纯形法的速度比较快. 反过来，如果约束条件的数目比变量数目多的话，则单纯形法比较快：
Wolfram Language code: t = Timing[res = LinearOptimization[c.x, constraints, x, "PrimalMinimizerVector", Method -> "Simplex"];]; Print["time = ", t[[1]], " optimal value = ", c.res, " or ", N[c.res]]
Wolfram Language code: t = Timing[res = LinearOptimization[c.x, constraints, x, "PrimalMinimizerVector", Method -> "RevisedSimplex"];]; Print["time = ", t[[1]], " optimal value = ", c.res, " or ", N[c.res]]
如果我们只希望得到机器精度的结果，那么问题应该转化成机器精度数字，而且应该使用内点法：
Wolfram Language code: t = Timing[res = LinearOptimization[c.x, constraints, x, "PrimalMinimizerVector", Method -> "InteriorPoint"];]; Print["time = ", t[[1]], " optimal value = ", c.res]

内点算法

虽然单纯形法和修正单纯形法平均上看可以非常有效，可是它们最差情况下的行为却很糟糕. 我们有可能会建立一个线性优化模型，其中单纯形法和修正单纯形法的步骤数目随问题大小呈指数增长. 而内点算法收敛所需的步骤数目已经被证明随问题大小呈多项式变化.

此外，Wolfram 语言的单纯形法和修正单纯形法的实现利用稠密线性代数，而它的内点法的实现利用机器精度的稀疏线性代数. 因此对于大规模，机器精度线性优化问题，其内点法更为有效并且更应该使用.

内点法表述

考虑下面的标准化线性优化问题

其中 、、. 这个问题可以通过使用障碍函数方法来处理正值约束来求解.

上述问题的一阶必要条件得出

设 表示由向量 构成的对角矩阵，并且 .

这是一个由 个有约束条件的线性/非线性方程组成的集合. 它可以使用牛顿法

及

得到求解.

求解这个线性系统的一个方法是使用高斯消去法把矩阵简化成块三角矩阵的形式.     

为了求解这个块三角矩阵，我们可以求解所谓的正规系统，该正规系统中的矩阵：

这个矩阵是正定的，但是当接近我们要求的解时就变得非常病态了. 因此我们使用数值技术来稳定求解的过程，并且通常情况下我们只能期待内点法求解该问题到一个大约为 的容差，容差的概念在 "收敛容差" 中有解释. Wolfram 语言使用 Mehrotra 的预估校正方案 [1].

收敛容差

一般线性优化问题可以首先被转化成标准形式

其相应的对偶问题是

内点算法的收敛标准是

在默认情况下，容差设置为 .

参考文献

[1] Vanderbei, R. Linear Programming: Foundations and Extensions. Springer-Verlag, 2001.
[2] Mehrotra, S. "On the Implementation of a Primal-Dual Interior Point Method." SIAM Journal on Optimization 2 (1992): 575–601.