线性规划算法
线性规划的定义
找到一个向量的线性规划问题
这样的一个或多个以下控制:
·x≤
Aeq·x=
l≤
内点linprog算法
的“内点”
算法非常相似<一个href="//www.tatmou.com/ch/ch/help/optim/ug/quadratic-programming-algorithms.html" class="a">interior-point-convex quadprog算法。它也有许多共同特征“interior-point-legacy”
算法。这些算法具有相同的概要:
Presolve,意思是简化和转换问题的标准形式。
生成一个初始点。一个初始点的选择尤其重要解决内点算法有效,这一步可以耗时。
预估解决马方程迭代。这一步通常是最耗时的。
Presolve
该算法首先尝试通过删除冗余和简化约束简化问题。presolve阶段中执行的任务可以包括以下:
检查如果任何变量有上界和下界。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性不等式约束只涉及一个变量。如果是这样的话,检查的可行性,然后改变线性约束绑定。
检查任何线性等式约束包括只有一个变量。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性约束矩阵为零行。如果是这样的话,检查的可行性,然后删除行。
确定范围和线性约束是一致的。
检查任何变量只出现在目标函数为线性的条件并没有出现在任何线性约束。如果是这样的话,检查可行性和有界性,然后固定在适当的范围的变量。
改变任何线性不等式约束线性等式约束通过增加松弛变量。
如果算法检测到一个不可行或无限问题,停止和一个适当的出口问题的消息。
算法可能到达一个可行点,代表了解决方案。
如果算法没有检测到一个不可行或无限问题在presolve步骤中,如果presolve还没有产生解决方案,该算法继续下一个步骤。达到停止条件后,该算法重建原始问题,取消任何presolve转换。这最后一步是postsolve一步。
为简单起见,如果这个问题不解决presolve步骤,算法转移所有有限的下界为零。
生成初始点
设置起始点,
初始化
x0来 的(n, 1),在那里 n是目标函数向量的元素的数量吗 f。 转换所有的组件有一个下界的0。如果组件
我有一个有限的上限 u(我),然后 x0 (i) = u / 2。 对于只有一个绑定的组件,必要时修改组件严格躺在里面的束缚。
把
x0靠近中央路径,需要一个预估的步骤,然后修改产生的位置和松弛变量躺在任何范围内。中央路径的详细信息,请参见Nocedal和赖特<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7],397页。
预估
类似于
现在,假设所有变量至少有一个有限的约束。通过转移和否定组件,如果有必要,这种假设意味着所有
x组件有一个下界的0。 扩展线性矩阵包括线性不等式和线性等式。<年代p一个ncl一个年代年代="inlineequation"> 平等是相应的线性向量。<年代p一个ncl一个年代年代="inlineequation"> 还包括条款扩展向量
x与松弛变量 年代把不等式约束等式约束: 在哪里
x0意味着原 x向量。 t是休闲裤的向量转换上界平等。
这个系统的拉格朗日涉及下列向量:
y,拉格朗日乘数法与线性等式
v拉格朗日乘数法与下界(积极约束)
w拉格朗日乘数法与上界
拉格朗日是
因此,这个系统的马条件
的λ
。
该算法预测的第一步从牛顿迭代公式,然后计算校正步骤。校正器试图减少非线性互补方程中的残留<年代p一个ncl一个年代年代="inlineequation">年代<年代ub>我z<年代ub>我= 0。牛顿-步骤是
(1) |
在哪里
r<年代ub>d,双残留
r<年代ub>p,原始的残余
r<年代ub>乌兰巴托上界残留
r<年代ub>vx,下界互补残留
r<年代ub>wt上界互补残留
迭代显示报告这些量:
来解决<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1,首先将其转化为对称矩阵形式
(2) |
在哪里
所有的矩阵逆的定义
获得<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2从<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1第二排的,请注意<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2是一样的第二个矩阵的行吗<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1。第一行的<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2来自于解决的最后两行<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程1对于Δ
方程2是对称的,但它不是正定的-
第二组行<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程2是
和第一组行
替换
给了
(3) |
通常,最有效的方式找到牛顿一步是解决<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程3对于Δ
更多的算法细节,看到Mehrotra<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[6]。
计算修正牛顿一步后,算法执行更多的计算得到当前步骤较长,和准备更好的后续步骤。这些多个校正计算可以提高性能和鲁棒性。详情,请参阅Gondzio<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[4]。
预估算法在很大程度上是一样的“interior-point-convex”
版本,除了二次项。看到<一个href="//www.tatmou.com/ch/ch/help/optim/ug/quadratic-programming-algorithms.html" class="a">完整的预估。
停止条件
预估算法迭代,直到达到一个点,是可行的(满足约束在公差内)和相对步大小很小的地方。具体来说,定义
该算法满足所有这些条件时停止:
在哪里
r<年代ub>c基本措施互补残差的大小
Interior-Point-Legacy线性规划
介绍
interior-point-legacy方法是基于<一个cl一个年代年代="indexterm" name="d124e35113">LIPSOL (<一个href="//www.tatmou.com/ch/ch/help/optim/ug/selected-bibliography.html" class="a">[52]),这是一个变体<一个cl一个年代年代="indexterm" name="d124e35118">Mehrotra预估的算法(<一个href="//www.tatmou.com/ch/ch/help/optim/ug/selected-bibliography.html" class="a">[47]),一个<一个cl一个年代年代="indexterm" name="d124e35123">内点方法。
主要算法
该算法首先应用一系列的<一个cl一个年代年代="indexterm" name="d124e35132">预处理步骤(见<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">预处理)。预处理后,问题的形式
(4) |
上界约束是隐式地包含在约束矩阵
(5) |
这被称为<年代p一个ncl一个年代年代="emphasis">原始的问题:
(6) |
在哪里
(7) |
在哪里
的λ
。
二次方程<年代p一个ncl一个年代年代="inlineequation">x<年代ub>我z<年代ub>我= 0和<年代p一个ncl一个年代年代="inlineequation">年代<年代ub>我w<年代ub>我= 0被称为“<年代p一个ncl一个年代年代="emphasis">互补线性规划的条件;其他(线性)方程被称为<一个cl一个年代年代="indexterm" name="d124e35239">可行性条件。的数量
x<年代up>Tz+
是<年代p一个ncl一个年代年代="emphasis">二元性的差距衡量互补的剩余部分
该算法是一个<年代p一个ncl一个年代年代="emphasis">非算法,这意味着原始和双程序同时得到解决。它可以被视为一个Newton-like方法,应用线性二次系统<年代p一个ncl一个年代年代="inlineequation">F(
该算法的一种变体<一个cl一个年代年代="indexterm" name="d124e35298">预估Mehrotra提出的算法。考虑一个迭代<年代p一个ncl一个年代年代="inlineequation">v= (
这是牛顿方向;那么所谓的<年代p一个ncl一个年代年代="emphasis">校正器方向
在哪里<年代p一个ncl一个年代年代="inlineequation">μ> 0被称为<年代p一个ncl一个年代年代="emphasis">定心参数,必须仔细选择。<年代p一个ncl一个年代年代="inlineequation">
是一个0 - 1向量与相应的二次方程
步长参数在哪里
v<年代up>+= (
满足
(
在解决前预测/校正方向,算法计算(稀疏)直接修改的柯列斯基因素分解<年代p一个ncl一个年代年代="inlineequation">一个?<年代up>T。如果低密度脂蛋白
函数引用页面。)
然后算法循环,直到迭代收敛。停止准则的主要是一个标准:
在哪里
是原始的残余,双残留,上限分别可行性(<年代p一个ncl一个年代年代="inlineequation">{
之间的区别是原始的和双目标价值,然后呢<年代p一个ncl一个年代年代="emphasis">托尔是一些宽容。的总和<一个cl一个年代年代="indexterm" name="d124e35455">停止标准措施的总相对误差最优性条件<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程7。
原始的不可行性的措施<年代p一个ncl一个年代年代="inlineequation">| |
预处理
该算法首先尝试通过删除冗余和简化约束简化问题。presolve阶段中执行的任务可以包括以下:
检查如果任何变量有上界和下界。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性不等式约束只涉及一个变量。如果是这样的话,检查的可行性,然后改变线性约束绑定。
检查任何线性等式约束包括只有一个变量。如果是这样的话,检查的可行性,然后修复和删除变量。
检查任何线性约束矩阵为零行。如果是这样的话,检查的可行性,然后删除行。
确定范围和线性约束是一致的。
检查任何变量只出现在目标函数为线性的条件并没有出现在任何线性约束。如果是这样的话,检查可行性和有界性,然后固定在适当的范围的变量。
改变任何线性不等式约束线性等式约束通过增加松弛变量。
如果算法检测到一个不可行或无限问题,停止和一个适当的出口问题的消息。
算法可能到达一个可行点,代表了解决方案。
如果算法没有检测到一个不可行或无限问题在presolve步骤中,如果presolve还没有产生解决方案,该算法继续下一个步骤。达到停止条件后,该算法重建原始问题,取消任何presolve转换。这最后一步是postsolve一步。
为了简单起见,该算法转移所有下界为零。
虽然这些预处理步骤可以做得加快迭代算法的一部分,如果<一个cl一个年代年代="indexterm" name="d124e35504">拉格朗日乘数法,预处理步骤必须消除由于乘数计算算法为转换后的问题,而不是原始的。因此,如果乘数<年代p一个ncl一个年代年代="emphasis">不要求,这种转变不是计算,可能会节省一些时间计算。
对偶单纯形算法
在高级别上,对偶单纯形的
算法本质上执行一个单纯形算法
该算法首先预处理中描述<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">预处理。,安德森,安德森<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[1]和Nocedal莱特<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7]第13章。这种预处理降低了原始形式的线性规划问题<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程4:
一个和
原始定义的可行性<年代up>+函数
原始的不可行性的措施
在解释<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">方程6,对偶问题是找到向量
的λ
。
双不可行性的措施
众所周知(例如,明白了<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7]),任何有限的对偶问题的解决方案给原始问题的解,以及任何有限解决原始问题给出了对偶问题的解决方案。此外,如果原始或对偶问题是无界的,然后另一个问题是不可行的。如果原始或对偶问题是不可行的,那么另一个问题是不可行或无限。因此,这两个问题是等价的获得有限的解决方案,如果一个人的存在。因为原始和对偶问题在数学上是等价的,但计算的步骤不同,它可以更好地解决原始问题的对偶问题的解决。
帮助缓解退化(见Nocedal和赖特<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[7],366页),首先扰动目标函数对偶单纯形算法。
对偶单纯形算法的第一阶段是要找到一个对偶可行点。该算法通过解决一个辅助线性规划问题。
在第二阶段,解决重复选择一个输入变量和一个变量。该算法选择离开变量根据福勒斯特技术建议和戈德法布<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[3]被称为双重steepest-edge定价。算法选择一个输入变量使用哈里斯的比率的变化由Koberstein测试建议<一个href="//www.tatmou.com/ch/ch/help/optim/ug/linear-programming-algorithms.html" class="intrnllnk">[5]。为了帮助缓解退化,算法可以在第二阶段引入额外的扰动。
迭代的求解程序,试图保持双重可行性,同时减少原始的不可行性,直到解决减少,摄动问题是原始可行和对偶可行。该算法展开的扰动。如果解决方案(摄动问题)是双非微扰(原始)问题不可行,那么解决恢复双重使用原始单纯形或第一阶段算法的可行性。最后,解算器打开预处理步骤回到最初的问题的解决方案。
基本和非基本变量
本节定义了条件<年代p一个ncl一个年代年代="emphasis">基础,<年代p一个ncl一个年代年代="emphasis">nonbasis,<年代p一个ncl一个年代年代="emphasis">基本可行的解决方案金宝搏官方网站为一个线性规划问题。定义假设问题给出以下标准形式:
(注意,
如果
引用
[1]安徒生,e D。,K. D. Andersen.
[2]阿普尔盖特,d . L。,R。E. Bixby, V. Chvátal and W. J. Cook,
[3]福勒斯特,J·J。和d·戈德法布。
[4]Gondzio, j .“多个中心修正原始对偶线性规划的方法。”https://www.maths.ed.ac.uk/ gondzio /软件/ correctors.ps
。
[5]Koberstein,。
[6]Mehrotra,美国“在一个非内点方法的实现。”
[7]Nocedal, J。,S. J. Wright.