最優(yōu)化問(wèn)題簡(jiǎn)介

，為約束函數(shù)，。滿?最優(yōu)化數(shù)學(xué)模型中的所有約束條件就稱為可?點(diǎn)(FeasiblePoint)，所有可?點(diǎn)的全體稱為可?域(Feasible表?。在?個(gè)可?點(diǎn)的邊界；如果有，就稱不等式約束在點(diǎn)，如果沒(méi)有?個(gè)不等式約束是有效的，就稱是可?域的內(nèi)點(diǎn)，不滿?，如果存在?個(gè)鄰域成?，則稱為最優(yōu)化問(wèn)題的局部最優(yōu)解，其中，如果存在?個(gè)鄰域和和為等式約束，和考慮不等式約束，則稱為最優(yōu)化問(wèn)題的全局最優(yōu)解（或總體最優(yōu)解）；如果可?點(diǎn)是?個(gè)?的正數(shù)；對(duì)于可使得則是局部極?解，其中為連續(xù)函數(shù)，通常還要求連續(xù)可微。稱為決策變量，為不等式約束，并記等式約束的指標(biāo)集為分別是英?單詞minimize(極?化)和subjectto(受約束)的縮寫(xiě)。，如果有滿?成?，則稱為最優(yōu)化問(wèn)題的嚴(yán)格局部最優(yōu)解。如下圖所是嚴(yán)格局部極?解，?為?標(biāo)函，就稱不等式約束是?嚴(yán)格局部極?解。（注：在點(diǎn)附近有?段線考慮不等式約束是

最優(yōu)化問(wèn)題簡(jiǎn)介，為約束函數(shù)，。滿?最優(yōu)化數(shù)學(xué)模型中的所有約束條件就稱為可?點(diǎn)(FeasiblePoint)，所有可?點(diǎn)的全體稱為可?域(Feasible表?。在?個(gè)可?點(diǎn)的邊界；如果有，就稱不等式約束在點(diǎn)，如果沒(méi)有?個(gè)不等式約束是有效的，就稱是可?域的內(nèi)點(diǎn)，不滿?，如果存在?個(gè)鄰域成?，則稱為最優(yōu)化問(wèn)題的局部最優(yōu)解，其中，如果存在?個(gè)鄰域和和為等式約束，和考慮不等式約束，則稱為最優(yōu)化問(wèn)題的全局最優(yōu)解（或總體最優(yōu)解）；如果可?點(diǎn)是?個(gè)?的正數(shù)；對(duì)于可使得則是局部極?解，其中為連續(xù)函數(shù)，通常還要求連續(xù)可微。稱為決策變量，為不等式約束，并記等式約束的指標(biāo)集為分別是英?單詞minimize(極?化)和subjectto(受約束)的縮寫(xiě)。，如果有滿?成?，則稱為最優(yōu)化問(wèn)題的嚴(yán)格局部最優(yōu)解。如下圖所是嚴(yán)格局部極?解，?為?標(biāo)函，就稱不等式約束是?嚴(yán)格局部極?解。（注：在點(diǎn)附近有?段線考慮不等式約束是

題?：最優(yōu)化問(wèn)題簡(jiǎn)介

?年多學(xué)習(xí)以來(lái)，?論是前?學(xué)習(xí)壓縮感知，還是這半年學(xué)習(xí)機(jī)器學(xué)習(xí)，?直離不開(kāi)最優(yōu)化，?如壓縮感知的基追蹤類重構(gòu)算法，核?問(wèn)題就是?個(gè)優(yōu)化問(wèn)題，?機(jī)器學(xué)習(xí)中的很多算法也需要最優(yōu)化的知識(shí)，?如?持向量機(jī)算法。看來(lái)必須得把最優(yōu)化的基本內(nèi)容學(xué)習(xí)?下了，不求理解的有多么深，?少要知道怎么?。其實(shí)前?已經(jīng)寫(xiě)過(guò)?篇與最優(yōu)化相關(guān)的內(nèi)容了，就是《》這篇。

從本篇起，開(kāi)始學(xué)習(xí)?些有關(guān)最優(yōu)化的基礎(chǔ)知識(shí)，重點(diǎn)是了解概念和如何應(yīng)?。本篇是參考?獻(xiàn)第1.1節(jié)的?個(gè)摘編或總結(jié)，主要是把?些概念集中起來(lái)，可以隨時(shí)查閱。

1、?般形式

最優(yōu)化問(wèn)題的數(shù)學(xué)模型的?般形式為（以下稱為最優(yōu)化數(shù)學(xué)模型）：

其中數(shù)，，不等式約束的指標(biāo)集為

2、概念

如果點(diǎn)Region)，?有效約束或起作?約束(activeconstraint)，并稱可?點(diǎn)位于約束是?效約束或不起作?約束(inactiveconstraint)；對(duì)于?個(gè)可?點(diǎn)是內(nèi)點(diǎn)的可?點(diǎn)就是可?域的邊界點(diǎn)。顯然在邊界點(diǎn)?少有?個(gè)不等式約束是有效約束，當(dāng)存在等式約束時(shí)，任何可?點(diǎn)都要滿?等式約束，因此不可能是等式約束的內(nèi)點(diǎn)。如果?個(gè)可?點(diǎn)，則稱為最優(yōu)化問(wèn)題的嚴(yán)格全局最優(yōu)解（或嚴(yán)格總體最優(yōu)解）；對(duì)于可?點(diǎn)

使得?點(diǎn)?，點(diǎn)是嚴(yán)格全部極?解，是?平的）

?般常見(jiàn)的最優(yōu)化?法只適?于確定最優(yōu)化問(wèn)題的局部最優(yōu)解，有關(guān)確定全局最優(yōu)解的最優(yōu)化?法屬于最優(yōu)化問(wèn)題的另?個(gè)領(lǐng)域——全局最優(yōu)化。然?，如果最優(yōu)化問(wèn)題的?標(biāo)函數(shù)是凸的，?可?域是凸集，則問(wèn)題的任何最優(yōu)解（不?定唯?）必是全局最優(yōu)解，這樣的最優(yōu)化問(wèn)題?稱為凸規(guī)劃。進(jìn)?步，對(duì)于凸集上的嚴(yán)格凸函數(shù)的極?化問(wèn)題，存在唯?的全局最優(yōu)解。

3、分類

1）約束最優(yōu)化問(wèn)題

只要在問(wèn)題中存在任何約束條件，就稱為約束最優(yōu)化問(wèn)題。

只有等式約束時(shí)，稱為等式約束最優(yōu)化問(wèn)題，數(shù)學(xué)模型為：

只有不等式約束時(shí)，稱為不等式約束最優(yōu)化問(wèn)題，數(shù)學(xué)模型為：

。矩陣向量形式為，為半正定矩陣，則稱此規(guī)劃為凸?次規(guī)劃，否則為?凸規(guī)劃。對(duì)于?凸規(guī)

既有等式約束，?有不等式約束，則稱為混合約束優(yōu)化問(wèn)題（或?般約束優(yōu)化問(wèn)題）；。矩陣向量形式為，為半正定矩陣，則稱此規(guī)劃為凸?次規(guī)劃，否則為?凸規(guī)劃。對(duì)于?凸規(guī)

把簡(jiǎn)單界約束優(yōu)化問(wèn)題稱為盒式約束優(yōu)化問(wèn)題（或有界約束優(yōu)化問(wèn)題），數(shù)學(xué)模型為：

2）?約束最優(yōu)化問(wèn)題

如果問(wèn)題中?任何約束條件，則稱為?約束最優(yōu)化問(wèn)題，數(shù)學(xué)模型為：

3）連續(xù)與離散最優(yōu)化問(wèn)題

決策變量的取值是連續(xù)的，稱為連續(xù)最優(yōu)化問(wèn)題；

決策變量的取值是離散的，稱為離散最優(yōu)化問(wèn)題，?稱為組合最優(yōu)化問(wèn)題。如整數(shù)規(guī)劃、資源配置、郵路問(wèn)題、?產(chǎn)安排等問(wèn)題都是離散最優(yōu)化問(wèn)題的典型例?，求解難度?連續(xù)最優(yōu)化問(wèn)題更?。

4）光滑與?光滑最優(yōu)化問(wèn)題

如果最優(yōu)化數(shù)學(xué)模型中的所有函數(shù)都連續(xù)可微，則稱為光滑最優(yōu)化問(wèn)題；

只要有?個(gè)函數(shù)?光滑，則相應(yīng)的優(yōu)化問(wèn)題就是?光滑最優(yōu)化問(wèn)題。

5）線性規(guī)劃問(wèn)題

對(duì)于連續(xù)光滑最優(yōu)化問(wèn)題，如果最優(yōu)化數(shù)學(xué)模型中的所有函數(shù)都是決策變量的線性函數(shù)，則稱為線性規(guī)劃問(wèn)題。線性規(guī)劃問(wèn)題的?般形式為：

其中

其中

，

6）?次規(guī)劃問(wèn)題

對(duì)于連續(xù)光滑最優(yōu)化問(wèn)題，如果最優(yōu)化數(shù)學(xué)模型中的?標(biāo)函數(shù)是決策變量的?次函數(shù)，?所有約束都是決策變量的線性函數(shù)，則稱為?次規(guī)劃問(wèn)題。?次規(guī)劃問(wèn)題的?般形式為：

其中，為純量，為階對(duì)稱矩陣。如果劃，由于存在?較多的駐點(diǎn)，求解?較困難。

7）?線性最優(yōu)化問(wèn)題

只要最優(yōu)化數(shù)學(xué)模型中的函數(shù)有?個(gè)關(guān)于決策變量是?線性的，則稱為?線性最優(yōu)化問(wèn)題。

?線性最優(yōu)化問(wèn)題是最?般的最優(yōu)化問(wèn)題，?線性規(guī)劃和?次規(guī)劃問(wèn)題卻是相當(dāng)重要的特殊的最優(yōu)化問(wèn)題，因?yàn)樵趯?shí)際中形成的許多最優(yōu)化問(wèn)題都是線性規(guī)劃問(wèn)題或?次規(guī)劃