algorithm - 线性规划算法

Question

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

---

(1) 从一个可行点x_0开始

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

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

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

---

问题:

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

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

Answer 1

我很确定这行不通，除非我遗漏了什么:在大多数情况下，您的算法不会开始移动。

假设您的变量 x拍摄于R^n .

Ax <= b 形式的多面体包含在“最大”仿射子空间中 P维度 p <= n , 通常是 p比 n 小得多(您将有很多等式约束，这些约束可以是隐式的也可以是显式的:您不能假设 P 的表达式很容易从 A 和 b 获得)。

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

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

在内点方法中使用障碍函数有一个很好的理由:在实践中很难从约束(即使是像多边形这样的简单凸集)描述高维凸集的几何形状，并且事物当多面体的尺寸增加时，在一张纸上画图时“看起来很明显”通常不会起作用。

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