线性规划算法

考虑以下线性规划算法，用A.x < = b最小化[c，x]。线性规划算法

（1）启动与一个可行的点X_0

（2）给定一个可行点X_K，找到最大的α，使得X_K - alpha.c是受理（简单明了，看的比率A.x0到Ac的组件）

（3）将正常单位矢量n拿到我们刚刚到达的超平面，向内指向。在平面[n，n]上给出r = n - [n，c]/[c，c] .c，然后查找x_k - alpha.c + beta.r可接受的最大beta。设置x_ {k + 1} = x_k-alpha.c + 1/2 * beta.r

如果x_ {k + 1}足够接近x_k的范围内，则返回它，否则返回（2）

基本的想法是按照渐变直到碰到墙壁。然后，不像单纯形法的外壳那样遵循单纯形法则，解决方案在法向矢量的方向上，在解决方案没有变坏的平面内被踢回。解决方案在此方向的起点和下一个约束之间移动一半。它并没有比以前更糟糕，但是现在它更多地在单纯的“内部”，在那里有一个向着最佳状态迈进的长步。

虽然击中多于一个超平面的交点的概率是0，如果一个得到一定的容差范围内足够接近的多个超平面，法线的平均可以采取。
通过跟踪函数级别上的测地线，可以推广到任何凸目标函数。特别是对于二次编程，可以将解决方案转向单工的内部。

问题：

这是否算法有一个名字或下降的线性规划算法类别中？
它有一个明显的缺陷，我忽略了吗？

来源

2013-10-23 Arthur B.

听起来像一个作业问题 –

不，没有任何想象的延伸 –

我敢肯定，这并不工作，除非我错过了一些东西：在大多数情况下，你的算法不会开始移动。

假设您的变量x取自R^n。

形式Ax <= b的多面体包含在“最大”仿射子空间维度p <= n的P，通常p比n小得多（你将有很多的等式约束，它可以是隐性或显性的：你不能假设的P表达是简单从Ab和）获得的。

现在，假设你可以找到一个初始点x_0（这远不是显而易见的，顺便说一句）;很少有机会，梯度c的方向是可行的方向。您需要考虑在P上方向c的投影，这在实践中非常困难（您将如何计算这种投影？）。然后，你在步骤（3）中想要的不是你到达的超平面的法线方向，而是在P（将polyedron可视化为嵌入3d空间中的二维polyedron可以帮助）上的投影。

为什么在内点方法中使用屏障函数有一个很好的理由：实际上很难用约束（即使像polyedrons这样简单的）来描述高维凸集的几何形状，事情“似乎是显而易见的”，当你画上一张纸的图片不会平时工作时的polyedron增加的尺寸。

最后一点是，你的算法不会给出确切的解决方案，而单纯形法在理论上是这样做的（我通过使用精确的有理数来阅读它在实践中可以完成的地方）。

来源

2013-10-24 01:42:40

我确实假设我的多面体不是平的。我对一类没有平等约束的问题感兴趣，我会澄清这一点。 –

但是，这表明扁平化的单形可能会产生问题。在R^2中，假设我们希望将y坐标最小化，并且单形看起来像是一个45度角的非常细的针，算法最终将向下并向左走。 –

显然，还有[一些polyedrons]（http://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube），在其单面将表现不佳。然而，考虑y'的''上x中最小化<= 1'，回答'y <= 1'，回答'y <= x'。单工最多只需要一次迭代即可获得最佳解决方案;从'（1,1）'开始的算法将采用log2（n）次迭代求解，以“1/n”的容差“接近”最优值！ –

阅读了关于内点法：http://en.wikipedia.org/wiki/Interior_point_method

这种方法可以有很好的理论性，但算法性能往往尾关在实践

来源

2013-10-23 18:04:46

是的，它是一种内点法，但它并不试图设置障碍，所以它与维基百科中描述的方法大不相同文章。 –

线性规划算法

回答

相关问题