使用MATLAB解決全局優化算法的非凸優化

Question

我有一個簡單的無約束非凸優化問題。由於這些類型的問題具有多個局部最小值，因此我正在尋找可產生獨特/全局最小值的全局優化算法。在互聯網上，我遇到了全局優化算法，如遺傳算法，模擬退火等，但爲了求解簡單的一個變量無約束的非凸優化問題，我認爲使用這些高級算法似乎不是一個好主意。任何人都可以推薦一個簡單的全局算法來解決這種簡單的變量無約束非凸優化問題嗎？我非常感謝這方面的想法。

Answer 1

由於這是一個一維問題，事情更容易。 一個簡單的最速下降過程可以使用如下。 假設搜索的時間間隔是a<x<b。

從最小化你的函數f（x）開始SD。你恢復第一個最小Xm1。你應該使用一個好的步驟，不要太大。 通過加上一個正的小常數Xm1 +ε來改變這一點。然後最大化f或最小化-f，從這一點開始。你得到f的最大值，你用ε來扭曲它，並從那裏開始最小化，等等。

Answer 2

「由於這些類型的問題有多個局部最小值」。這是不正確的，真實的情況是這樣的：

• 也許你有一個極小

• 也許你有無限的一組局部miminums

• ，或者你可能有局部極小的數量有限

• 也許最小不能達到

• 也許PROBL EM是無限低於

另外一番景象是真的有正確的方法，其真正解決問題（數字和他們慢），但有調用方法的俚語是不是功能所必要的發現minumum值也稱爲「解決」。

---

1. 事實上M 1 N〜M表示任何有限n和任意無限集合M.因此，事實上，你的問題有一個維度是什麼。從理論的角度來看，從集合M中抽取1000000個參數仍然是一個難題。

2. 如果有趣如何近似求解與在域已知精度的ε-問題 - 然後分裂你域變換到1/espsilon區域，樣本值（evalute功能）在中間點，並選擇最小

3. 方法，該方法我下面將描述精確的方法和其他方法：粒子估計，序列凸編程，替代方向，粒子羣，Neidler-Mead單純形法，mutlistart梯度/次梯度下降法或任何下降算法，如牛頓法或座標下降法，它們分別爲所有對於非凸問題都沒有保證，如果函數是非凸的，它們中的一些甚至不能應用。

---

如果您在與函數值的一些精度真正解決有趣的話，我將介紹以下方法，它被稱爲分支定界並真正找到最低，你描述的算法我不這麼認爲，他們解決問題（以強烈的責任感）：

分支限界的基本思想 - 分區域爲凸集，提高低/上限，你的情況是間隔。

你應該有一個例行找到上限最優的（最小）值：您可以在例如做只是通過抽樣子域取最小值或使用從隨機點開始的局部最優化方法。

但你也應該通過一些原則上下限：

• 整型變量的凸鬆弛，使他們真正的變量

• 使用拉格朗日雙功能

• 使用Lipshitc上不變功能等

這是一個複雜的步驟。

如果這兩個值接近 - 我們在其他情況下partion完成或細化分區。

獲取有關上限和下限子子問題的信息，然後採取分鐘。上限和最小值。兒童的下限。如果孩子返回更低的下限，則可以由父母升級。

---

參考文獻：

更偉大的解釋請看： EE364B，第18講，教授。斯坦福大學斯蒂芬博伊德。它可以在YouTube和iTunes大學上使用。如果你是新來的這個領域，我建議你看看Stephen P. Boyd的EE263，EE364A，EE364B課程。你會愛上它