线性规划算法&MATLAB和Simulink金宝app - 金宝app,下载188bet金宝搏,金宝搏官方网站

线性规划算法

线性编程定义

线性规划是寻找向量的问题x使线性函数最小化F^Tx受线性约束的影响：

$\underset{x}{闵} F^{T} x$

这样一个或多个以下持有：

A·x≤B
AEQ·X.=贝基
L≤x≤U。

内点linprog算法

这个linprog'内点'算法非常相似内点凸四边形算法。它还分享了许多功能linprog“内点遗产”算法。这些算法具有相同的总体轮廓：

预解，意思是将问题简化并转化为标准形式。
生成初始点。初始点的选择对于高效求解内点算法尤为重要，并且此步骤可能非常耗时。
用于求解KKT方程的预测-校正迭代。此步骤通常最耗时。

预溶

该算法首先尝试通过消除冗余和简化约束来简化问题。在预解步骤中执行的任务可以包括以下内容：

检查是否有任何变量的上下限相等。如果是，请检查可行性，然后修复并删除这些变量。
检查是否有任何线性不等式约束涉及只有一个变量。如果是这样，请检查可行性，然后将线性约束更改为绑定。
检查是否有任何线性平等约束涉及一个变量。如果是这样，请检查可行性，然后修复并删除变量。
检查任何线性约束矩阵是否有零行。如果是，请检查可行性，然后删除行。
确定边界和线性约束是否一致。
检查是否有任何变量在目标函数中仅作为线性项出现，而不在任何线性约束中出现。如果是，请检查可行性和有界性，然后将变量固定在适当的边界上。
通过添加松弛变量，将任何线性不等式约束更改为线性等式约束。

如果算法检测到不可行或无界问题，它将停止并发出相应的退出消息。

该算法可能到达单个可行点，表示解决方案。

如果该算法在预定步骤中没有检测到不可行或无界问题，并且如果预定寄存器没有产生解决方案，则该算法继续下次步骤。达到停止标准后，算法重建原始问题，撤消任何预定变换。这一步骤是Postsolve步骤。

为简单起见，如果问题未在预解步骤中解决，则该算法将所有有限下界移到零。

生成初始点

要设置初始点，x0，该算法执行以下操作。

初始化x0到一（n，1），在哪里N目标函数的元素数是向量吗F。
将所有有界组件转换为下限为0.如果组件我有一个有限的上限u（i）然后x0（i）=u/2。
对于只有一个绑定的组件，如果需要，在必要时修改组件以严格地在绑定内部。
放置x0靠近中心路径，采取一个预测-校正步骤，然后修改结果位置和松弛变量，使其完全位于任何边界内。有关中心路径的详细信息，请参阅Nocedal和Wright[7]，第397页。

预测校正器

类似于铁铬镍铁合金内部点算法这个内部点算法试图找到卡鲁什·库恩·塔克（KKT）条件不变。为了描述线性规划问题的这些方程，考虑预处理后线性规划问题的标准形式：

$\underset{x}{闵} F^{T} x 从属于 {\begin{matrix} \bar{A.} x = \bar{B} \\ x + T = U \\ x, T \geq 0 \end{matrix}$

现在假设所有变量至少有一个有限界。如果必要，通过改变和否定成分，这一假设意味着x组件具有下限为0。
$\bar{A.}$ 是包含线性不等式和线性等式的扩展线性矩阵。 $\bar{B}$ 是对应的线性等式向量。 $\bar{A.}$ 还包括扩展载体的条款x使用松弛变量s将不平等约束转化为平等约束：

$\bar{A.} x = (\begin{matrix} {A.}_{E Q} & 0 \\ A. & 我 \end{matrix}) (\begin{matrix} x_{0} \\ s \end{matrix}),$

哪里x₀意味着原x向量。
T是将上限转换为相位的松弛的矢量。

该系统的拉格朗日涉及以下向量：

Y，与线性等式相关的拉格朗日乘数
v，与下限（正性约束）相关的拉格朗日乘数
W，与上界关联的拉格朗日乘数

拉格朗日函数是

$L = F^{T} x - Y^{T} (\bar{A.} x - \bar{B}) - v^{T} x - W^{T} (U - x - T) 。$

因此，该系统的KKT条件为：

$\begin{matrix} F - {\bar{A.}}^{T} Y - v + W = 0 \\ \bar{A.} x = \bar{B} \\ x + T = U \\ v_{我} x_{我} = 0 \\ W_{我} T_{我} = 0 \\ (x, v, W, T) \geq 0 \end{matrix}$

这个linprog算法对返回的拉格朗日乘数使用了与本讨论给出的不同的符号约定。这个讨论使用了和大多数文学作品一样的符号。看到兰姆达。

该算法首先根据牛顿-拉斐逊公式预测一个步长，然后计算一个校正步长。校正器试图减少非线性互补方程中的残差s_我Z_我= 0.牛顿-拉斐逊阶是

(\begin{matrix} 0 & - {\bar{A.}}^{T} & 0 & - 我 & 我 \\ \bar{A.} & 0 & 0 & 0 & 0 \\ - 我 & 0 & - 我 & 0 & 0 \\ v & 0 & 0 & X & 0 \\ 0 & 0 & W & 0 & T \end{matrix}) (\begin{matrix} δ. x \\ δ. Y \\ δ. T \\ \begin{array}{l} δ. v \\ δ. W \end{array} \end{matrix}) = - (\begin{matrix} F - {\bar{A.}}^{T} Y - v + W \\ \bar{A.} x - \bar{B} \\ U - x - T \\ \begin{array}{l} v X \\ W T \end{array} \end{matrix}) = - (\begin{matrix} R_{D} \\ R_{P} \\ R_{U B} \\ \begin{array}{l} R_{v x} \\ R_{W T} \end{array} \end{matrix}),

(1)

哪里X,v,W和T是对应于向量的对角矩阵x,v,W和T分别地方程式最右侧的剩余向量为：

R_D双残差
R_P，原始残留
R_乌兰巴托，上界残差
R_vx下界互补残差
R_WT。，上界互补残差

迭代显示报告这些数量：

$\begin{array}{l} 原始不可行性 = {‖ R_{P} ‖}_{1.} + {‖ R_{U B} ‖}_{1.} \\ 对偶不可行 = {‖ R_{D} ‖}_{\infty} 。 \end{array}$

解决等式1，首先将其转换为对称矩阵形式

(\begin{matrix} - D & {\bar{A.}}^{T} \\ \bar{A.} & 0 \end{matrix}) (\begin{matrix} δ. x \\ δ. Y \end{matrix}) = - (\begin{matrix} R \\ R_{P} \end{matrix}),

(2)

哪里

$\begin{array}{l} D = X^{- 1.} v + T^{- 1.} W \\ R = - R_{D} - X^{- 1.} R_{v x} + T^{- 1.} R_{W T} + T^{- 1.} W R_{U B} 。 \end{array}$

定义中的所有矩阵逆D和R因为矩阵是对角的，所以计算起来很简单。

推导等式2从等式1，请注意等式2与第二矩阵行相同等式1.第一排等式2来自解决最后两排等式1对于Δv和ΔW，然后求解ΔT。

等式2是对称的，但它不是正定的，因为——D因此，不能使用Cholesky分解来求解它。再多几个步骤，就会得到一个不同的正定方程，因此可以通过Cholesky分解有效地求解。

第二组行等式2是

$\bar{A.} δ. x = - R_{P}$

第一组行是

$- D δ. x + {\bar{A.}}^{T} δ. Y = - R 。$

替代

$δ. x = D^{- 1.} {\bar{A.}}^{T} δ. Y + D^{- 1.} R$

给予

\bar{A.} D^{- 1.} {\bar{A.}}^{T} δ. Y = - \bar{A.} D^{- 1.} R - R_{P} 。

(3)

通常，求牛顿步的最有效方法是解等式3.对于ΔY使用Cholesky分解。Cholesky因式分解是可能的，因为矩阵乘以ΔY显然是对称的，在没有简并的情况下，是正定的。之后，为了找到牛顿步，返回代换以找到Δx, ΔT, Δv，和ΔW。但是，当 $\bar{A.}$ 有一个稠密的柱，它可以更有效地解决等式2取而代之的是linprog内点算法根据柱的密度选择求解算法。

有关更多算法的详细信息，请参阅Mehrotra[6]。

在计算校正后的牛顿步长后，该算法将执行更多的计算，以获得更长的当前步长，并为更好的后续步骤做好准备。这些多次校正计算可以提高性能和鲁棒性。有关详细信息，请参阅Gondzio[4]。

预测-校正算法基本上与完整算法相同quadprog'内部point-convex'版本，二次项除外。请参阅完全预测器校正器。

停止条件

预测-校正算法迭代，直到达到可行点（满足公差范围内的约束）且相对步长较小。具体来说，定义

$ρ = 最大值 (1., ‖ \bar{A.} ‖, ‖ F ‖, ‖ \bar{B} ‖) 。$

当所有这些条件都满足时，算法停止：

$\begin{matrix} {‖ R_{P} ‖}_{1.} + {‖ R_{U B} ‖}_{1.} \leq ρ tolcon. \\ {‖ R_{D} ‖}_{\infty} \leq ρ 塔尔芬 \\ R_{C} \leq 托尔芬， \end{matrix}$

哪里

$R_{C} = \underset{我}{最大值} (闵 (| x_{我} v_{我} |, | x_{我} |, | v_{我} |), 闵 (| T_{我} W_{我} |, | T_{我} |, | W_{我} |)) 。$

R_C本质上衡量互补残差的大小XV.和tw，它们是一个解的每个零向量。

内点线性规划

介绍

内点传统方法基于Lipsol（[52])，它是Mehrotra的预测校正器算法（[47])，a原对偶内点法。

主算法

该算法首先应用一系列预处理步骤（参见预处理).经过预处理后，问题具有以下形式

\underset{x}{闵} F^{T} x 以致 {\begin{matrix} A. \cdot x = B \\ 0 \leq x \leq U 。 \end{matrix}

(4)

上界约束隐式包含在约束矩阵中A.. 通过添加原始松弛变量s,等式4.变成

\underset{x}{闵} F^{T} x 以致 {\begin{matrix} A. \cdot x = B \\ x + s = U \\ x \geq 0, s \geq 0 \end{matrix}

(5)

这被称为原始的问题:x包括原始变量和s由原始松弛变量组成二重的问题是

最大值 B^{T} Y - U^{T} W 以致 {\begin{matrix} {A.}^{T} \cdot Y - W + Z = F \\ Z \geq 0, W \geq 0, \end{matrix}

(6)

哪里Y和W包括双变量和Z由双宽松裤组成。这个此线性规划的最优性条件，即原始等式5.和双重等式6.是

\begin{array}{l} F (x, Y, Z, s, W) = (\begin{matrix} A. \cdot x - B \\ x + s - U \\ {A.}^{T} \cdot Y - W + Z - F \\ x_{我} Z_{我} \\ s_{我} W_{我} \end{matrix}) = 0, \\ x \geq 0, Z \geq 0, s \geq 0, W \geq 0, \end{array}

(7)

哪里x_我Z_我和s_我W_我表示组分 - 明智的乘法。

这个linprog算法对返回的拉格朗日乘数使用了与本讨论给出的不同的符号约定。这个讨论使用了和大多数文学作品一样的符号。看到兰姆达。

二次方程式x_我Z_我= 0和s_我W_我= 0被称为“互补性线性规划的条件；其他（线性）方程称为可行性状况。数量

x^TZ+s^TW

是对偶间隙，它度量了F什么时候(x，z，s，w) ≥ 0。

该算法是一个简单的算法原对偶算法，这意味着原始程序和对偶程序同时求解。它可以被认为是一个牛顿样的方法，适用于线性二次系统F(x、 y，z，s，w) = 0在里面等式7.，同时保持迭代x,Z,W和s正，因此命名为内点方法（迭代在由中的不等式约束表示的严格内部区域中）等式5..)

该算法是Mehrotra提出的预测-校正算法。考虑迭代v= [x; y; z; s; w]，在哪里[x、 z；s；w]> 0首先计算所谓的预言方向

$δ. v_{P} = - {(F^{T} (v))}^{- 1.} F (v),$

这是牛顿方向，然后是所谓的校正器方向

$δ. v_{C} = - {(F^{T} (v))}^{- 1.} F (v + δ. v_{P}) - μ. \hat{E},$

哪里μ.> 0被称为定心参数，必须仔细选择。 $\hat{E}$ 是一个与对应于二次方程的零矢量F(v），即扰动仅适用于互补条件，这些条件是所有二次的，而是不可行的可行性条件，这些条件都是线性的。两个方向与步长参数组合α.> 0更新v要获得新的迭代v⁺:

$v^{+} = v + α. (δ. v_{P} + δ. v_{C}),$

其中，步长参数α.被选为

v⁺= [x⁺; y⁺; Z.⁺; S.⁺; W.⁺]

满足

[x⁺; Z.⁺; S.⁺; W.⁺]> 0。

在求解前面的预测器/校正器方向时，该算法在修改的Cholesky因子的基础上计算（稀疏）直接因子分解A·A^T. 如果A.有在密集列中，它使用谢尔曼莫里森公式。如果该解决方案不足（残差太大），则执行步骤方程的增强系统形式的LDL分解，以找到解决方案。（看示例4-D的结构在MATLAB^®低密度脂蛋白函数参考页。）

然后，该算法循环，直到迭代收敛。主要停止标准为：

$最大值 (\frac{‖ R_{B} ‖}{最大值 (1., ‖ B ‖)}, \frac{‖ R_{F} ‖}{最大值 (1., ‖ F ‖)}, \frac{‖ R_{U} ‖}{最大值 (1., ‖ U ‖)}, \frac{| F^{T} x - B^{T} Y + U^{T} W |}{最大值 (1., | F^{T} x |, | B^{T} Y - U^{T} W |)}) \leq T o L,$

哪里

$\begin{matrix} R_{B} = A. x - B \\ R_{F} = {A.}^{T} Y - W + Z - F \\ R_{U} = {x} + s - U \end{matrix}$

分别是原始残差、对偶残差和上界可行性({x}指那些x具有有限上界），以及

$F^{T} x - B^{T} Y + U^{T} W$

是原始目标值和双重目标值之间的差异，以及托尔是一些公差。在停止标准测量在最优条件中的总相对误差等式7.。

原始不可行性的度量是||R_B||对偶不可行度的度量是||R_F||，其中范数为欧几里德范数。

预处理

该算法首先尝试通过消除冗余和简化约束来简化问题。在预解步骤中执行的任务可以包括以下内容：

检查是否有任何变量的上下限相等。如果是，请检查可行性，然后修复并删除这些变量。
检查是否有任何线性不等式约束涉及只有一个变量。如果是这样，请检查可行性，然后将线性约束更改为绑定。
检查是否有任何线性平等约束涉及一个变量。如果是这样，请检查可行性，然后修复并删除变量。
检查任何线性约束矩阵是否有零行。如果是，请检查可行性，然后删除行。
确定边界和线性约束是否一致。
检查是否有任何变量在目标函数中仅作为线性项出现，而不在任何线性约束中出现。如果是，请检查可行性和有界性，然后将变量固定在适当的边界上。
通过添加松弛变量，将任何线性不等式约束更改为线性等式约束。

如果算法检测到不可行或无界问题，它将停止并发出相应的退出消息。

该算法可能到达单个可行点，表示解决方案。

为简单起见，该算法将所有下界移到零。

而这些预处理步骤可以大大加快算法的迭代部分，如果如果需要拉格朗日乘子，则必须撤消预处理步骤，因为在算法过程中计算的乘子是用于转换的问题，而不是原始问题。因此，如果乘子是不请求时，不会计算此转换，可能会节省一些计算时间。

双单算法

在高层次上linprog'双重simplex'该算法本质上是在计算机上执行单纯形算法对偶问题。

该算法从预处理开始，如中所述预处理. 有关详细信息，请参见安达信和安达信［１］和nocedal和wright[7]，第13章，此预处理将原始的线性编程问题降低到了形式等式4.:

$\underset{x}{闵} F^{T} x 以致 {\begin{matrix} A. \cdot x = B \\ 0 \leq x \leq U 。 \end{matrix}$

A.和B是原始约束矩阵的转换版本。这是首要问题。

可以在原始可行性方面定义⁺作用

$x^{+} = {\begin{array}{l} x & 如果 x > 0 \\ 0 & 如果 x \leq 0 \end{array}$

原始不可行性的度量是

$原始不可行性 = \sqrt{{({(磅 - x)}^{+})}^{2.} + {({(x - 乌兰巴托)}^{+})}^{2.} + {({(A. x - B)}^{+})}^{2.} + {| Aeq x - 贝基 |}^{2.}} 。$

如上所述等式6.，对偶问题是寻找向量Y和W，和松弛变量向量Z解决方案

$最大值 B^{T} Y - U^{T} W 以致 {\begin{matrix} {A.}^{T} \cdot Y - W + Z = F \\ Z \geq 0, W \geq 0 \end{matrix}$

这个linprog算法对返回的拉格朗日乘数使用了与本讨论给出的不同的符号约定。这个讨论使用了和大多数文学作品一样的符号。看到兰姆达。

对偶不可行性的度量是

$对偶不可行 = {‖ {A.}^{T} Y + Z - W - F ‖}_{2.} 。$

这是众所周知的（例如，参见[7])对偶问题的任何有限解都给出了原问题的解，原问题的任何有限解都给出了对偶问题的解。此外，如果原始问题或对偶问题是无界的，那么另一个问题是不可行的。如果原始问题或对偶问题不可行，那么另一个问题要么不可行，要么无界。因此，这两个问题在获得有限解（如果存在）方面是等价的。由于原始问题和对偶问题在数学上是等价的，但计算步骤不同，因此通过求解对偶问题来解决原始问题会更好。

帮助缓解退化（见Nocedal和Wright[7]，第366页），对偶单纯形算法从扰动目标函数开始。

对偶单纯形算法的第一阶段是寻找对偶可行点。该算法通过求解一个辅助线性规划问题来实现这一点。

第1阶段轮廓

在第1阶段，算法找到初始基本可行解（参见基本变量和非基本变量通过求解辅助分段线性规划问题，辅助问题的目标函数为线性惩罚功能 $P = \sum_{J} P_{J} (x_{J})$ ,

哪里P_J(x_J)定义为

$P_{J} (x_{J}) = {\begin{array}{l} x_{J} - U_{J} & 如果 x_{J} > U_{J} \\ 0 & 如果 L_{J} \leq x_{J} \leq U_{J} \\ L_{J} - x_{J} & 如果 L_{J} > x_{J} 。 \end{array}$

P(x)衡量一个点有多少x违反下限和上限条件。辅助问题是

$\underset{x}{闵} \sum_{J} P_{J} 从属于 {\begin{matrix} A. \cdot x \leq B \\ A. E Q \cdot x = B E Q 。 \end{matrix}$

当且仅当辅助问题的最小值为0时，原问题才有可行的基点。

该算法通过启发式方法为辅助问题找到初始点，并在必要时添加松弛和人工变量。然后利用这个初始点和单纯形算法来解决辅助问题。该解是主算法第二阶段的初始点。

在第二阶段，解算器重复选择一个输入变量和一个离开变量。算法根据Forrest和Goldfarb建议的技术选择一个离开变量[3]该算法利用Koberstein提出的Harris比率检验的变化来选择输入变量[5].为了帮助缓解简并，该算法可以在第2阶段引入额外的扰动。

第二阶段大纲

解算器迭代，试图保持对偶可行性，同时减少原始不可行性，直到减少的扰动问题的解既是原始可行的，也是对偶可行的。该算法消除了引入的扰动。如果（扰动问题的）解对于未扰动（原始）问题是对偶不可行的，则解算器使用原始单纯形或第一阶段算法恢复对偶可行性。最后，解算器展开预处理步骤，将解决方案返回到原始问题。

基本变量和非基本变量

本节定义条款原因,非基础和基本可行的解决方案金宝搏官方网站对于一个线性规划问题。该定义假设问题以以下标准形式给出：

$\underset{x}{闵} F^{T} x 以致 {\begin{matrix} A. \cdot x = B, \\ L B \leq x \leq U B 。 \end{matrix}$

（注意A.和B不是定义原始问题中不等式的矩阵和向量。）假设A.是一个M-经过-N秩矩阵M<N，其列为{A._1.,A._2., ...,A._N}1.假设 ${{A.}_{我_{1.}}, {A.}_{我_{2.}}, ..., {A.}_{我_{M}}}$ 是的列空间的基础A.，索引集B= {我_1.,我_2., ...,我_M}，而且N={1，2，…，n}\B是补充B.子矩阵A._B被称为A.原因和互补子矩阵A._N被称为A.非基础.向量基本变量是x_B和非基本变量是x_N。在第2阶段的每次迭代中，算法将当前基的一列替换为非基的一列，并更新变量x_B和x_N照着

如果x是解决方案A·x=B以及所有非基本变量x_N等于其下限或上限，x被称为A.碱性溶液。此外，如果x_B满足其上下限，以便x是一个可行的点，x被称为A.基本可行解。

参考文献

[1] 安徒生，E.D.和K.D.安徒生。预定线性规划《数学编程》711995，第221-245页。

[2] Applegate，D. L.，R.，R. Bixby，V.Chvátal和W. J. Cook，旅行商问题：一个计算研究，普林斯顿大学出版社，2007年。

[3] 福里斯特、J.J.和D.戈德法布。线性规划的最陡边单纯形算法. 数学1992年第57期节目，第341-374页。

[4] 线性规划的原始-对偶方法中的多重中心校正计算优化及其应用，第6卷，第2期，1996年，第137-156页。可在https://www.maths.ed.ac.uk/~gondzio/software/correctors.ps.。

[5] 科伯斯坦，A。用于求解大规模LP问题的双单简单算法的进展：快速稳定实现的技术。计算无光。和应用41,2008，pp.185-204。

[6] Mehrotra，S。“关于基于双重内部点法的实施。”暹罗期刊优化，第2卷，1992年，第575-601页。

[7] Nocedal，J.和S.J.Wright。数值优化，第二版。运筹学中的Springer系列，Springer Verlag，2006年。