0

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

(1) 从可行点 x_0 开始

(2) 给定一个可行点 x_k，找到最大的 alpha 使得 x_k - alpha.c 是可接受的（直截了当，看看 A.x0 与 Ac 的分量的比率）

(3) 取法线单位向量n到我们刚刚到达的超平面，指向内。在平面 [c,.] 上投影 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，但如果一个在一定容差内足够接近多个超平面，则可以取法线的平均值。

  • 这可以通过在函数级别上遵循测地线来推广到任何凸目标函数。特别是对于二次规划，将解旋转到单纯形的内部。

问题：

  • 该算法是否有名称或属于线性规划算法的类别？

  • 它有我忽略的明显缺陷吗？

4

2 回答 2

1

我很确定这不起作用，除非我错过了什么：在大多数情况下，您的算法不会开始移动。

假设你的变量x被R^n.

形式的多面体包含在维度Ax <= b的“最大”仿射子空间中，并且通常比（您将有很多等式约束，可以是隐式的或显式的：您不能假设从和) 获得。Pp <= npnPAb

现在假设您可以找到一个初始点x_0（顺便说一句，这远非显而易见）；c梯度的方向是可行方向的可能性很小。您需要考虑在 上的方向投影，c这P在实践中很难做到（您将如何计算这样的投影？）。

然后，您在步骤 (3) 中想要的不是您到达的超平面的法线方向，而是它的投影P（将多面体可视化为嵌入 3d 空间中的 2d 多面体会有所帮助）。

在内点方法中使用障碍函数有一个很好的理由：在实践中很难从约束中描述高维凸集的几何形状（即使是像多面体这样简单的），以及“似乎很明显”当你在一张纸上画一幅画时，当多面体的尺寸增加时，通常不会起作用。

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

于 2013-10-24T01:42:40.537 回答
0

阅读内点方法： http ://en.wikipedia.org/wiki/Interior_point_method

这种方法可以具有很好的理论特性，但算法性能在实践中往往会下降

于 2013-10-23T18:04:46.560 回答