如果有最優解，為什麼單純形最終一定會達到最優解？

01-11

單純形演算法，是從一個較低的點，然後逐步走向較高的點，但是我有一個疑問。就好比有一座山，山上有兩個峰，一個峰高，一個峰低，為啥單純形他最後爬到的不是那個較低的峰，如果爬到了那個較低的峰，他就下不來了，當然也有可能一個山有很多個峰，單純形是如何確保就是那個最高的峰的？

你問的這個問題，表明有一些最基本的概念你還沒有理解。

我會盡量用最簡單的方法來講解，避免使用公式。

等到你完全理解了這個答案，再去看公式的時候就容易理解了。

1. 最基礎的是凸優化概念。

凸優化表示問題的可行域是「凸」的。「凸」形的可行域的標準是：你在這個可行域裡面（注意我說的「裡面」是包含邊緣的，下同），任意取2個點，然後把它們連成一條線，那麼這條線一定會在可行域內。

在你的大腦中想像一下球體，在球體內部（包含邊緣）任意選兩個點，是不是兩點的連線永遠在球體內部（包含邊緣，下面就不重複了...)？

再想像一下正方體，立方體，椎體...很多形狀都是凸的。

然而我們再來想一個非凸的例子：

在這個香薰台當中，很顯然如果我們選取香薰台頂部兩點，如果這兩點橫跨了中間凹進去的一部分，那連線就不在香薰台當中了。所以這個形狀不凸。

2. 峰

我不太確定你理解的峰是什麼，我覺得你可能理解錯了，所以在這裡我把正確的峰和我猜測你所理解的峰都講一下。

正確的峰：

峰的概念往往是與鞍點相關的。我就不用公式表示什麼是鞍點了，直接看下圖，乳溝里紅綠相交的位置就是鞍點。

出現鞍點，說明這個形狀肯定不是凸的。形狀不是凸的，那就會出現峰。如上圖，我們有左峰和右峰（怎麼感覺越說越邪惡）。左峰會比右峰高一些。

如果真的要定義它，我們就說：當你站在一個點上時，發現不管往哪個方向走，都不會比現在的位置更優，那你就到達峰了。

假設我們站在右峰上，而你又近視，只能看到下一步之內的地方。你要決定往哪裡走，但是你發現不管往哪走都不如現在的位置高。所以雖然在遠處有一個更高的峰，你也去不了。因為你追求的是最高，而你現在的位置已經是（你能看到的）最高了。

我猜測你理解的峰：

為什麼說我猜測呢？因為線性規劃里沒有什麼「峰」，原因是線性規劃的可行域是凸的，根本沒有鞍點，那也就不可能有峰了。

而你又問峰，所以我猜測你理解的是「頂點」。比如說是這個立方體的每個頂點。但他們實際上並非峰。

我們舉個例子。假設你現在站在最左邊的那個頂點（不好意思PS試用過期了，懶得畫圖了）。你的目標是去最高的位置。當你站在那個頂點時，會發現沿著你旁邊的線往上邁一步，你的位置就升高了。這說明你目前的位置不是最高，你還可以繼續往上走。

既然你還可以繼續走，那肯定不是「峰」了。除非你走到最頂端那個點，你會發現，不管往哪個方向走，都不如當前位置。那現在你就處於「峰」，唯一的峰，最好的峰。

綜合上面兩點，我們得出結論：

結論1：凸形可行域只有1個峰，只要達到那個峰，我們就達到了最優。（試想幾個凸形可行域，看是不是這樣）

結論2：至少有一個頂點是峰。

第二個結論什麼意思呢？當你把正方體像上圖中立起來，你很容易看到有一個頂點是峰。當你把它放平，整個平面都是最高的。這個時候你有無數個點是最高的（四個頂點以及他們構成的正方形內部）。這種情況下，最優點是4個頂點以及他們構成的面。結論2依然滿足。

3. 單純形法

單純形法，僅適用於線性規劃，線性規劃又是凸優化的一種。

因為結論2，我們可以有這樣一種優化的思路：既然至少有一個頂點是峰，我們求每個頂點的高度，找出其中最高的一個，肯定就是最優點。

行得通，但是結合結論1，還有個更簡單的方法：

先找到一個頂點，然後從這個頂點，沿著某條邊線，走到下一個頂點，直到最優。方向的選擇可以有很多種，最多使用的是比較短視的方法：沿著最陡峭的那一條，追求當前步上升最快。

假設我們現在在正方體的最低端。

第1步，3條路可以選，我們發現從右邊那條邊緣走提升最快，於是到達了最右端的頂點。

第2步，有3條路，左，右，下。我們發現往下是比當前位置低的，顯然不能選。比較一下左右，我們選左邊吧。於是到達下圖中最高頂點下方的點。

第3步，也是3條路，但只有一條路比你當前位置高，那就選它了。於是你就到達了最高的頂點。

第4步，三條路都不如現在的位置好。那你就到達最優點了。

你可以看到，在這個最優化的過程中，一旦發現沒有更好的路走，你就停了。在非凸優化中，你可不能這麼干，因為這樣你只能找到一個峰而已，也叫做局部最優。但凸優化里，只會有一個局部最優，所以它也就理所應當地成為全局最優。

綜上，

1. 單純形法是凸優化的演算法。

2. 凸優化中只有一個峰，該峰是全局最優。

3. 單純形法尋找路線優化目標函數，直至達到一個峰，而該峰就是全局最右。

嘿嘿，我覺得所有答案都答得對的。邏輯鏈一步一步是這樣的。

單純形法是用來解線性規劃的 -&> 線性規劃的定義域是單純形 -&> 單純形是凸的 -&> 定義域是凸的而且目標函數是線性的，那麼目標函數在整個定義域裡面只有一個峰 -&> 由於單純形法就是題主說的一步一步往上爬，那一定會爬到「那個」峰頂。

有興趣的看看下面寫的每一小步怎麼推吧。

什麼是凸，@zhong z講得很好了。

命題「定義域是凸的而且目標函數是線性的，那麼目標函數在整個定義域裡面只有一個峰」為什麼對？

因為假如定義域裡頭假如存在兩個峰，由於定義域是凸的，兩峰之間連線上所有的點也都在定義域內。由於目標函數是線性的，所以兩峰的連線直接就是這些點的函數值。於是假如有一個峰矮一點，我們就可以從這個峰沿著那根連線爬到更高的峰，換言之這個矮的峰壓根不是峰。矛盾。所以兩個峰一樣高。得到的最優值是同一個值。

還有，為什麼單純形是凸的呢？

單純形是什麼？數學上可以寫成一堆線性不等式限制出來的區域（等式約束是可以化成不等式約束的，例如一個帶等於號的限制條件就可以寫成一個帶大於等於和一個帶小於等於的限制條件）

那可以寫成一堆線性不等式限制條件的區域是什麼？慢慢來。先看一個。

一個線性不等式能限制出來的區域是什麼？如果全空間是一個平面，這個不等式就是給它切了一刀，只剩下一半的空間。它是凸的。再加一個線性不等式是什麼？就是再切一刀，剩下的還是凸的。切多少刀都是凸的，所以就是凸的了。你自己切切看？

Hope this helps

首先線性規劃里，極點（也就是你所謂的峰）的數目是有限的，其次每次用非基變數取代基變數的時候，目標函數是變得更優的（否則者有無窮個解），也即是說不會走倒路，前途有限，又不能往回走，你說丫是不是能終止？而且因為目標函數是更新一次極點就會變得更優一點，你說最後丫是不是最優解？

單純形解的是線性規劃，線性的目標不會是多峰的。

因為限制條件必須是凸集了吖。這個很多運籌學書里最開始就有講吧

單純形法適用於線性凸優化。凸就保證了要麼unbounded要麼只有一個極值

如果有兩座山峰，那麼可行域就不是凸邊形了（兩座「峰頂」之間的連線上必存在點不在可行域內），而單純形法僅適用於凸的可行域。當遇到兩個「山峰」時，應將其切割這兩個凸可行域，再分別用單純形法求解最優解，最後求出全局最優解。

這學期上運籌學，老師講的時候我想起了吳恩達的課程里的梯度下降法，貼兩張圖題主看看吧，比較直觀

非凸優化問題，從一個起點出發，找到了局部最優但可能不是全局最優

凸優化問題：隨便怎麼走最後找到的就是全局最優

而我們的線性規劃問題的性質保證了它只能是第二種情況，因為約束條件都是 $leq$ ,你在一個二維平面上劃的時候就會發現斜率始終是負的，你切不出一個凹進去的可行域。

這種問題為什麼也要發到知乎上問？看下教科書不就行了嗎？