最優化問題的簡潔介紹是什麼？

11-25

因為有人問我，為什麼學習機器學習必須要看最優化的書。我沒有想到最合適的解答。
從百度百科抄了一段，但是總覺得沒講到核心問題。

最優化方法（也稱做運籌學方法）是近幾十年形成的，它主要運用數學方法研究各種系統的優化途徑及方案，為決策者提供科學決策的依據。最優化方法的主要研究對象是各種有組織系統的管理問題及其生產經營活動。最優化方法的目的在於針對所研究的系統，求得一個合理運用人力、物力和財力的最佳方案，發揮和提高系統的效能及效益，最終達到系統的最優目標。實踐表明，隨著科學技術的日益進步和生產經營的日益發展，最優化方法已成為現代管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經濟管理、工程建設、國防等各個領域，發揮著越來越重要的作用。本章將介紹最優化方法的研究對象、特點，以及最優化方法模型的建立和模型的分析、求解、應用。主要是線性規劃問題的模型、求解（線性規劃問題的單純形解法）及其應用――運輸問題；以及動態規劃的模型、求解、應用――資源分配問題。

最優化，就是：
1. 構造一個合適的目標函數，使得這個目標函數取到極值的解就是你所要求的東西；
2. 找到一個能讓這個目標函數取到極值的解的方法。
下面通過兩個例子進行解釋。

一、圖像去噪
假設你手頭有一張照片《沙塵暴下依然堅持工作的攝像師》：

你打算讓計算機幫你去個噪，把圖像變清晰。你對計算機說：

你看，計算機的回復往往是「你丫能不能說機話！」這是因為計算機是無法進行抽象思維的，它不懂重建、去噪、清晰這些複雜的概念，它唯一會的東西就是加減乘除這樣的基本運算，你只能使用正確的計算機語句讓它去執行對應的基本運算，因此就需要首先把去噪問題轉化成一個數學問題，一個函數的求解問題。比如可以試著這樣想，去噪，就是要把圖像變平滑，於是你對計算機說：給爺來張圖片，無比光滑。計算機的回答是：

真的是好光滑，但是且慢！攝像師哪去了？你是想光滑圖像，但是也需要保留圖像中的有用細節。這就說明你設計的目標不合理。一個好的去噪的目標，應該兼顧兩個要求：與原始圖像盡量接近，並且盡量光滑。一個合適的目標可以是：尋找一幅圖像A，讓下面這個目標函數J最小：

J(A) = (A與原始圖像盡量接近) + r * (A盡量平滑)

我們要尋找的，就是能讓目標函數J最小的圖像A，能夠兼顧相似和平滑兩個要求。因子r用來權衡二者的重要程度。當r取0時，我們得到的最優目標圖像就是原始圖像自己！因為我們的目標只是相似，而原始圖像自己和自己最像，但是這樣就沒有任何平滑效果；當r取無窮大的時候，為了讓整個目標函數J不至於無窮大，我們必須保證A無比平滑，這樣就得到上面那張過度平滑，與原始圖像毫不相似的無意義圖片。因此，為了兼顧兩個目標，我們需要把r的值取得不大不小。

有了一個合適的目標函數，下面就需要構造一種獲得它的極小值的演算法。在圖像去噪領域有一大堆演算法：卷積去噪、中值去噪、雙邊濾波、偏微分方程、小波去噪、隨機場去噪......它們的作用或多或少都是相同的——求上面那個混合目標函數的最小值。計算機運算獲得的去噪圖像是：

從這個成功去噪的例子中我們可以看出：合理的目標函數是最優化第一個需要精心考慮的問題，需要直覺和理性；而如何求解目標函數，則是一個數學演算法問題。二者都是數學家們和工程師們大顯身手的地方。

二、機器學習
題主困惑機器學習和最優化之間為什麼聯繫緊密，是因為對機器學習這個領域不太了解，實際上研究最優化方法最多的人都在這個領域。機器學習的目的，就是為了讓計算機代替人來發現數據之間隱藏的關係。

之所以要使用計算機，是因為數據量太大，遠遠超過人腦的處理能力。比如我們需要從一堆人臉圖片里給每個人標上正確的名字，一幅32像素見方的人臉圖像有1024顆像素點，你能想像出一百萬張這樣的照片和1萬個人名字之間的關係是什麼樣嗎。再比如給你1萬個患者的DNA序列，每個患者的序列由百萬級的鹼基對構成，你能找到這些天文數字量級的序列和是否患某種疾病之間的聯繫嗎？

答案是不能！所以研究者退而求其次，建立很多學習模型，這些模型輸入是一個樣本的數據（頭像圖片、一個人的DNA序列），輸出是樣本的標籤（人名、是否患病）。模型里有大量可以調整的參數，這些參數通過訓練，能夠學習到數據和標籤之間人類無法直接理解的、複雜的關係。科學家期望當模型訓練完成後，再拿來一個樣本，餵給這個訓練好的機器，它能夠吐出一個標籤，這個標籤恰好就是樣本對應的那個正確的標籤。

目前人們已經研究出一大堆學習模型：神經網路、支持向量機、AdaBoost、隨機森林、隱馬爾科夫鏈、卷積神經網路等等。它們的結構差異很大，但是共同點都是擁有一大堆參數，就等著你餵給它數據供它學習。這些模型的學習也需要一個目標函數：讓模型的分類錯誤率盡量小。為了達到目的，模型的訓練往往首先給參數賦上隨機初值，然後用各種下降法來尋找能讓分類錯誤率更小的參數設置，梯度下降、牛頓法、共軛梯度法和Levenberg—Marquard法都是常見的方法。

隨著研究的深入，問題也越來越多，比如下降法往往只能保證找到目標函數的局部最小值，找不到全局最小值，怎麼辦呢？答案是不一味下降、也適當爬爬山，說不定能跳出小水溝（局部極小值）找到真正的深井（全局極小值），這種演算法叫模擬退火。也可以增大搜索範圍，讓一群螞蟻（蟻群演算法）或者鳥兒（粒子群演算法）一齊搜索，或者讓參數巧妙地隨機改變（遺傳演算法）。

那麼多模型，到底該選哪個？研究者又發現了一個定理「天下沒有免費的午餐」定理，意思是沒有一個模型能一直比其他模型好，對於不同類型的數據，必須要通過實驗才能發現哪種學習模型更適合。機器學習領域也就成了學界灌水嚴重的領域之一——換模型、調參數就能發文章哎。

下面說到了調參數，問題又來了，到底是參數多了好還是少了好？參數少了模型太笨學不到數據內的複雜關係，參數多了模型太精明又可能會把數據中的隨機雜訊當作某種關係進行認真學習（過擬合）。最後大家一致認為，確定模型的複雜度時，要保證模型能力足夠強，能夠學會數據之間的關係，能力又不能太強，以至於耍小聰明亂學習。這種選擇模型的思想被稱為奧卡姆剃刀：選擇有能力的模型中最簡單的那個。此外，訓練模型的目標並不是為了使訓練樣本能夠被盡量正確分類，更需要對未知新樣本有好的分類效果，這樣模型才有實用價值，這種能力被稱為泛化能力。除了奧卡姆剃刀原理外，訓練時引入隨機性的模型比確定的模型（比如BP神經網路）具有更好的泛化能力。

模型的更新也是問題。如果引入了新數據，全部模型都需要重新訓練是一筆很大的開銷，在線學習模型採用來一個樣本學一點的模式，能夠不斷自我更新；半監督學習利用少量帶標籤的樣本訓練一個原始模型，然後利用大量無標籤數據再學習。

咱們來看看一些經典的學習模型能做成啥樣。首先隨便畫點散點圖，紅色和白色是兩類不同的數據，分類器需要對整個空間做分割，讓平均分類錯誤率盡量小。你可以先想想如果讓你來分要如何劃分。

首先是神經網路，使用了6個神經元把空間分成了奇怪的形狀：

如果神經元數目變成10個，學到的模式將會十分怪異，說明模型過於複雜了：

下面是支持向量機的分類結果，這是這幾十年機器學習最重要的成果之一，它的發明是基於結構最小化準則，通俗地講就是把目標函數設為：
J=模型分類正確率 + r * 模型複雜度
使得模型能夠自動選擇分類效果好，並且盡量簡單的參數。

接下來是隨機樹，它把空間劃分為一系列矩形區域（葉子），所有的葉子區域由一顆樹形結構從根節點不斷劃分而成，隨機的意思是樹的生長每次劃分第一維還是第二維是隨機的：

支持向量機對於小樣本數據和非線性結構數據的分類有十分優秀的表現：

在機器學習領域，還有很多重要問題被不斷討論，優秀的模型也不斷在湧現。這個領域的開山模型是神經元，由其組成的多層神經網路由於訓練速度慢、分類效果不佳，在支持向量機出現後很快就失去了熱度。大家卯著勁研究怎麼面對訓練樣本不足的窘境，PCA和核方法大行其道，前者致力於減少數據維數，後者致力於從低維數據中學習高維結構。但是近幾年隨著卷積神經網路的流行，神經網路又煥發出了第二春，研究者發現只要樣本量足夠大（百萬級甚至億級樣本量），網路參數足夠多（百萬級參數），加上巧妙的防過擬合技術，利用現代並行計算帶來的強大計算能力，神經網路能夠學得和人類的判別能力一樣好。機器學習領域發展了幾十年，似乎又回到了出發的地方。

優化問題的核心有三部分，決策（Decision），目標（Objective）和約束（Constraint）。

優化的目的是在選取一個（或一些決策），在滿足一定約束情況下，儘可能達到某一目標。在去思考優化問題時，最好的順尋就是問以下問題：

1、我要做的決策是什麼？

2、我要達到的目標是什麼？

3、我的決策有什麼約束？

優化問題的寫法也是依照這個順序：

事實上，所有的決策問題，小到我們生活中的每一個選擇，大到國家的戰略，都可以分解為這樣的三部分（包括所有的機器學習問題）。因此優化的思想可以說是在人們的生活中無處不在，也是世間萬物的一種基本規律。數學家歐拉早在18世紀就說過：

Nothing at all takes place in the universe in which some rule of maximum or minimum does not appear. – L. Euler, 1707-1783

在實際中，搞清楚實際問題的這三部分分別是什麼，並且用合理的方式去表達是最解決問題中最終要的一步。完成了這一步（所謂的建模）通常已經完成了解決問題的絕大部分。後面就需要用到優化的演算法。這兩部分也是學習運籌優化的核心。

最優化問題最抽象的說就是

在一定的約束條件下，求一個函數的最大（小）值。

要理解的其實只有兩個概念，函數和約束條件。甚至函數這個概念已經包含了對約束條件的考慮。

所謂函數，簡單理解的話，可以當做一個機器，你給它一個輸入，它就給你一個輸出，它是一個對應。你通過調節輸入，達到最好的輸出。它是現實狀況的數學語言表達。例如我們要最小化總費用，我們知道單價，我們可以決定數量，於是我們得到的數學表達：總費用=單價乘以數量。我們通過調整數量來最小的總費用。

至於約束條件，它有很多種，例如等式的約束，不等式的約束，微分方程的約束，概率的約束，等等等等。他們也是對我們現實狀況中的約束的數學表達。

不同的約束配上不同的目標函數就會得到一個不同的問題。例如目標函數和約束都是線性的，這個最優化問題就叫線性規劃，如果約束是個常微分方程，就叫最優控制。等等等等。

這些問題有的好解，有的不好，所以其實數學建模在這裡頭的作用很大。對於一個現實問題，建立一個簡單好解又能較好地描述現實情況的模型，是一種藝術。這是數學界甚至科學界追求的美的原則：simple and elegant.

謝邀，但是我本科最優化這門課掛了。。
所以算是工作後自學成才。其實這個東西挺好理解的：

更新：機器學習為什麼要學習最優化呢？

因為機器學習其實本質是機器進化，通過演算法的方式進化出最適應需求（最優化函數）的「模式」。進化的過程和演算法就是最優化的核心研究課題，所以剛好這個數學工具能為機器學習提供很好的幫助。
－－－－－－－－－－－－－－－－－－－－－－－－－－

嚴格定義是對某個定義域為Q，值域為某個有序集R（一般研究R＝實數的情形）的函數f，求x屬於Q使得f(x)最小（大）。

這樣的問題就是最優化問題。

這個東西和機器學習有什麼關係呢？機器學習中Q一般是一個函數構成的空間，比如希爾伯特空間。

然後比如你要學習出一個函數，函數q你希望輸入是128*128的圖像像素矩陣，輸出是判斷圖像是否代表一個美女。

然後你要制定一個標準，這個標準可以衡量q這個函數的質量，比如q輸出和實際情況相比的誤差什麼的，不展開討論，總之這個標準可以定義為一個函數，叫做v。v(q)越大，函數質量越高，越接近你想要的結果

那麼從數學上，你這個問題就轉變成了在Q這個空間內尋找v(q)的最大值這個最優化問題。

當然世紀上，因為Q這個空間的結構可能非常扯淡，因而這個問題基本不可能有解析解。所以要用數值方法：
如各種解析搜索方法：梯度下降、牛頓
隨機搜索方法：蟻群、進化、退火

還有就是設法取一個Q的性質比較好的子集。比如所有從128*128的圖像像素矩陣到0/1這個函數空間性質太差了。那麼比如說：
限定使用決策樹？
限定使用SVM
限定使用logistic
限定使用神經網路

不定時更新。

在機器學習領域有個普遍的觀點：所有機器學習的問題最後都轉換為了最優化問題。

擬合一些數據點，你可以選擇 $y=ax+b$ 擬合，你也可以選擇 $y=ax^2+bx+c$ 擬合，你甚至可以選擇更高維的曲線擬合，那麼選擇哪個？ -- 最優化問題
兩堆數據點，你想在中間畫一條直線，將其分開，實際上這樣的直線很多，選擇哪一個？最優化問題。

任何一個機器學習問題，我們提一個模型來描述問題很簡單，所有可能的模型組成了假設空間。
那麼機器學習最後都轉化到在假設空間中找到最優解。求最優解的策略很多，選擇經驗風險最小化或結構風險最小化，最後都還是最優化問題。

當然機器學習的內容肯定不止於此，數據、模型、演算法都有很多內容值得探索。

求一個函數的最小（大）值。

最優化就是對於有n個參量和一個評價函數的問題，轉換為對n+1維空間內的n維圖形求一個方向上（評價函數）最遠點問題。

首先，從數學上說，所有問題的所有限制都可以轉化為參數和約束條件。其次，多個評價函數組成的評價體系最終都可以用一個評價函數來描述（也許不直觀但是可行）。

比方說一個參數一個函數的最優化問題其實就是二維平面上一條曲線的最值點問題；兩個函數就是三維空間的一個曲面的最值問題。

線性規劃等非遍歷演算法的核心都是通過已知條件將問題降維的過程。遍歷型演算法都是走遍每一個可能的取值點求值然後比較，取最值的過程（當然存在一些優化）。運籌學範疇的最優化問題本質都是如此，只是提出各種常見條件下的簡化計算的方法。

機器學習的核心仍是輸入一系列參數，輸出一個結果，只不過它實際使用的參數除了顯式輸入之外還有學習過程中帶來的參數積累，本質仍是最優化過程。

比如想從廣州去杭州，怎樣最快又最經濟（目標函數）？你有很多種方法，可以坐火車，飛機，汽車(很多種解，而且可以對這些解進行組合)，但總是有個組合最讓你滿意（最優解），最符合你的期望。怎麼去求解這個最優解，由此產生的一系列方法。

少花錢多幹事

先吐個槽: 最高票答案用圖像去噪等實例來說明, 說得挺好的. 但是其他大部分答案真是不敢恭維, 實在忍不住我也來說幾句吧.

一句話來說 (其實 @滴水說得挺準確了), 最優化問題就是 "在一定的約束條件下, 求目標函數的最優值".

最一般的優化問題, 可以寫成下面的形式:

$egin{array}{cl} minlimits_{xin mathbb{R}^n} f(x) \ extrm{s.t.} c_i(x)=0, quad i=1,ldots,m_e \ c_i(x) leq 0, quad i=m_e+1,ldots,m end{array}$

其中, $x$ 是變數, $f(x)$ 是目標函數, $c_i(x)$ 是等式和不等式約束 (這也是一般的優化問題需要明確的三個要素: 變數, 目標函數, 約束條件).
當然, 等式也可以上界下界相等的不等式來表示, 所以, 也有人只用不等式約束來表示一般的最優化問題. 另外, 有些問題的變數可以在整個空間取, 也就變成了無約束的問題.

ps: 一般來說, 我們都可以將目標函數及約束用數學公式表達出來 (這就是建模), 但對於某些特別的"黑箱"問題, 可能我們並不知道它們的具體形式, 一般會假設, 給定一個輸入, 會產生一個輸出. 無導數優化方法 (derivative-free optimization, DFO) 就是一類用來解決此類問題的演算法.

pps: 上面是關於優化"問題"的簡單介紹, 而優化演算法, 實在太多, 但跟問題無關, 在此不介紹了.

Maximumize utility while minimizing loss,try not break any constraints or model assumptions. If you can"t, use a numerical method, run a few scenarios and be prepared for surprises.

搜索目標的方法或問題的集合。

最優化，這個詞可以理解成最優化問題，也可以理解成最優化方法。我一般都理解成優化問題及求解的方法。關於優化的學科個人就學過幾門：最優化演算法、運籌學、計算智能、最優控制、數學分析里也有。

就優化問題而言，除了形式直接的優化問題，方程和方程組也可以轉換成優化問題。從應用來看，常見到的有圖像去噪和路徑搜索。問題分類的話，就看角度了，可分凸和非凸、離散和連續、無約束和帶約束。

就優化方法而言，以前看一篇論文，有個搜索方法的圖譜，其實也就是優化方法，分兩大類：隨機的方法、微積分的方法。隨機的比如遺傳演算法，微積分的比如梯度法。

以優化方法中的下降方法（梯度法和牛頓法等）為例談談我的認識。實際上就是我們要到一個地方去，但這個地方我們也不知道，於是，離這個地方的遠近通過指標來衡量（停止條件），問題知道了，然後我們從一個起點出發（迭代初值），出發前就先要確定邁步子的方向（下降方向）和步子的大小（迭代步長），走完一步檢查一下是不是到了，整個過程就是如此的反覆…… 這類優化方法主體就是討論這些走路各個要素的方法。

這些內容在我的一篇博客總結裡面有提到，從數學的角度來總結的。

Nothing takes place in the world whose meaning is not that of some maximum or minimum. ---- L. Euler
最優化學科研究的是將問題轉化為maximum或minimum的方法

用更少的話獲取更多的贊

正好這學期有一門數學系開的Optimierung的課就來說些隨便說說。

優化一般分為連續優化和離散優化。

1. 連續優化
首先，連續優化就是大部分答案提到的那種，研究對象是一個函數 $f in R^n ightarrow R$ ,和一系列的限制函數 $g_i leq 0, h_j =0$ 構成的子空間 $M$ 。基本所有連續優化問題都能表示成這樣的形式。

連續優化的問題又分為存在代數解的和不存在代數解的。拿你在搞的機器學習舉例，有些連續問題是存在代數解的，即可以直接求出來，比如MAP和Maximal Likelihood可以直接用拉格朗日求出來，因為這種問題符合拉格朗日的必要條件 $Df(ar{x})=0, D^2f(ar{x})$ 是正定矩陣。除了直接套用拉格朗日求極值，機器學習中用的最多的是KKT條件來把問題轉化到對偶問題上，比如SVM。

還有一類問題不能直接求出代數解，只有數值解，也就是通過反覆迭代得到一個近似解，這部分內容基本就是數值分析在極值問題上的擴展，比如機器學習中的神經網路，EM演算法，都是解決不能一步求出極值問題。

2. 離散優化
可以看成是數學系學的可計算與複雜度理論，也有一些組合數學上的bound。東西比較雜，就不細說了，反正也和機器學習基本不沾邊（除了少量可計算學習理論的東西會用）。

一句話總結，如果搞機器學習不會優化，就不知道那些機器學習模型的目標函數是怎麼轉化到一個學習演算法上的；遇到新的模型變種，也不知道該怎麼求解。

最高票已經回答了什麼叫「最優化」問題。。。我回答一下「為什麼學習機器學習必須要看最優化的書」。。。
1. 機器學習目的是學一個函數f
2. 方法是構造一類函數
3. 然後挑出最好的一個
第二個問題是建模的問題，第三個問題是最優化。解決一個機器學習的問題，要做的就是解決這兩個問題。這就是最優化問題和機器學習的關係。

stephen boyd在convex optimization的課程里說世界上基本所有的問題都可以通過構建並求解最優化的問題解決。
比如說，系統的優化，為什麼好多國產手機配置那麼牛，但是用戶在使用的時候卻覺得特別的卡頓？
為什麼有的車開起來那麼舒服？
為什麼有的路基本不怎麼堵.雖然道不寬，車還多？
為什麼好多商場的布局那麼合理，就比如說你總能找到一個服務人員幫你解決問題。
這些都可以用最優化模型來建模並解決，
以手機硬體的參數設定來說。電池容量，屏幕解析度的大小，處理器的頻率，這些屬性並不是說越大越好的，而是要進行權衡才能達到系統的最優，所謂的最優可能是流暢性，待機的時長，等方面。
汽車的調教，信號燈的時間設置，這些也是最優化的研究內容。

既然是一句話，那就簡單點：

基於對過去的擬合所得到的最優化解，在未來一定不是最優的。因為未來只要與過去不同，哪怕是一絲最微小的不同，都會讓這個解不再是最優解。

未來會一成不變嗎？

作者：趙越
鏈接：https://zhuanlan.zhihu.com/p/25829403
來源：知乎
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

之前我有個論斷：人生沒有全局最優解，因為人生是凹凸不平的！（給文科僧們科普一下，因為只有凸函數的局部最優才是全局最優，這是凸優化里的一個基本結論）

今天在思考華為CodeCraft演算法題中有一個新的想法，可以擴充我之前的那句話。

在建模中最優化的演算法中，它們的解往往有兩種，局部最優解和全局最優解。顧名思義，局部最優解做到的是每一步的解最優，但它最終結果不一定是理論最優；全局最優解滿足最終結果最優。

世界上有兩種人最容易取得成功，一種是一開始就有堅定的目標及為目標不屈不饒奮鬥的人，但這種人乃是稀有人種不是每個人可以做到的；還有一種是把每一步都做到最好，爭取每走一步都是局部最優解，最後走到一個豁然開朗的境地的人（計算機演算法中稱呼為貪婪演算法）。

很多時候人不能肯定自己將來能做什麼，以及成為什麼樣的人，並將以什麼方式去為之奮鬥，但我們能做到的是走好人生中的每一步。因此，局部最優解也許就是人生中的最佳選擇。

注意這裡的詞用的是也許……因為更加嚴格的數學推導確實只能用也許。但是凸優化中有幾個假設是，在求解的過程中環境是不會隨時變化的，可是我們的人生比這個問題複雜的多，我們的環境是隨時變化的。想一次性求出全局最優解幾乎是不能的。這個時候，我們普通人能做的就是求好每一個局部最優解，這樣隨著環境變化和個人的成長。也許當你的人生走到終點時，這一系列的局部最優解便就是屬於你自己的全局最優解~

求一個函數的最小值的問題