這篇關(guān)于最優(yōu)化的文章是最近學(xué)習(xí)的一個總結(jié)，放在簡書上，方便以后查閱，如果幫助了其他讀者，也算一件好事。

一、前言

現(xiàn)實生活中，當我們面臨抉擇（有幾個備選方案可選），我們總是會希望可以做出最優(yōu)選擇，所以可以對所面臨的問題進行建模，也就是根據(jù)需要考慮的因素，得到一個代價函數(shù)（損失函數(shù)）或者收益函數(shù)，然后求解該優(yōu)化問題，尋找函數(shù)的最值點，得到最優(yōu)選擇。

例如種地問題，問：種x畝的玉米和y畝的小麥可以獲得最大收益，x和y均未知，且滿足一定約束條件，調(diào)整x和y，使得目標函數(shù)達到最大，也就得到了最優(yōu)選擇。

大部分的機器學(xué)習(xí)算法都可以歸結(jié)為最優(yōu)化問題，例如logistic回歸和神經(jīng)網(wǎng)絡(luò)，都是調(diào)整模型參數(shù)，使得損失函數(shù)最小，得到參數(shù)的最優(yōu)值；SVM中，調(diào)整模型參數(shù)，使得劃分超平面距離兩個類邊緣的間隔最大，即得到模型的最優(yōu)解。

二、從最優(yōu)化到凸優(yōu)化

一般情況下求解一個函數(shù)的最值并不容易，因為容易陷入局部極值，所以一般的最優(yōu)化問題直接窮舉遍歷（解空間比較小）或者使用啟發(fā)式搜索（解空間很大，NP問題）。而凸優(yōu)化問題（convex optimization）則可以高效地求解最值，基于目標函數(shù)的“凸”性，它的局部最優(yōu)解即為全局最優(yōu)解。

一旦一個問題轉(zhuǎn)化為凸優(yōu)化問題，那么這個問題就得到了解決，因為凸優(yōu)化已經(jīng)被研究透了。

三、凸優(yōu)化的定義：

（1）凸集（convex sets）：集合中任意兩點的連線都在這個集合中。

（2）凸函數(shù)（convex functions）：函數(shù)曲線任意兩點的連線都在函數(shù)上方。

（3）凸優(yōu)化：調(diào)整優(yōu)化變量使得目標函數(shù)（是一個凸函數(shù)）最小，優(yōu)化變量屬于凸集，或者說優(yōu)化變量需要滿足一定的不等式約束和等式約束。

四、凸優(yōu)化問題分類：

（1）線性規(guī)劃（LP, linear programming）：目標函數(shù)和不等式約束都是線性函數(shù)。

（2）二次規(guī)劃（QP, quadratic programming）：目標函數(shù)是凸二次函數(shù)，不等式約束是線性函數(shù)。

（3）二次約束二次規(guī)劃（QCQP, quadratically constrained quadratic programming）：目標函數(shù)和不等式約束都是凸二次函數(shù)。

五、凸優(yōu)化問題求解的一般方法：

根據(jù)凸函數(shù)的性質(zhì)，只要一直沿著可以使目標函數(shù)變小的方向搜索，就可以找到最小值，所以可以使用梯度下降的方法。

要更新某一個優(yōu)化變量，只需對這個優(yōu)化變量求偏導(dǎo)，然后計算它處于當前值的導(dǎo)數(shù)，即梯度，也就是目標函數(shù)在此處的變化率，然后乘上步長，即得到修正量，然后根據(jù)負梯度方向更新這個優(yōu)化變量即可。

六、求解線性規(guī)劃：

先畫出可行域，然后將頂點代入目標函數(shù)，求得最大值或最小值即可。

這是因為，目標函數(shù)是線性函數(shù)，所以只要x或y增大，目標函數(shù)都會增大，所以可能的最優(yōu)解一定在可行域的邊界上。沿著邊界，x或y會增大，直到遇到拐點（也就是可行域的頂點），遇到拐點之后，x或y可能會減小，所以最優(yōu)解只可能是幾個交點之一。

轉(zhuǎn)載請注明如下內(nèi)容：

文章來自簡書，作者：就是楊宗

原文鏈接：http://www.itdecent.cn/p/b47daa391e2d