考虑以下线性规划算法,使用 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,但如果在一定公差范围内足够接近多个超平面,则可以取法线的平均值。
这可以通过在函数级别上遵循测地线推广到任何凸目标函数。特别是对于二次规划,将解决方案旋转到单纯形的内部。
问题:
此算法是否有名称或是否属于线性规划算法的类别?
它是否有我忽略的明显缺陷?
最佳答案
我很确定这行不通,除非我遗漏了什么:在大多数情况下,您的算法不会开始移动。
假设您的变量 x
拍摄于R^n
.
Ax <= b
形式的多面体包含在“最大”仿射子空间中 P
维度 p <= n
, 通常是 p
比 n
小得多(您将有很多等式约束,这些约束可以是隐式的也可以是显式的:您不能假设 P
的表达式很容易从 A
和 b
获得)。
现在假设您可以找到一个初始点 x_0
(顺便说一句,这远非显而易见);梯度方向的可能性很小 c
是一个可行的方向。您需要考虑方向的投影 c
在 P
,这在实践中很难做到(你将如何计算这样的投影?)。
然后,您在步骤 (3) 中想要的不是您到达的超平面的法线方向,而是它在 P
上的投影(将多面体想象成嵌入 3d 空间中的 2d 多面体会有所帮助)。
在内点方法中使用障碍函数有一个很好的理由:在实践中很难从约束(即使是像多边形这样的简单凸集)描述高维凸集的几何形状,并且事物当多面体的尺寸增加时,在一张纸上画图时“看起来很明显”通常不会起作用。
最后一点是您的算法不会给出精确解,而单纯形在理论上可以给出(我在某处读到它可以通过使用精确的有理数在实践中完成)。
关于algorithm - 线性规划算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19548023/