線性規劃算法

考慮以下線性規劃算法，用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

是的，它是一種內點法，但它並不試圖設置障礙，所以它與維基百科中描述的方法大不相同文章。 –

線性規劃算法

回答

相關問題