凸優(yōu)化-概述

參考教材《凸優(yōu)化》，參考視頻2011中科大凌青《最優(yōu)化理論》

一.數(shù)學(xué)優(yōu)化

1.定義

數(shù)學(xué)優(yōu)化問(wèn)題或者說(shuō)是優(yōu)化問(wèn)題可以寫(xiě)成如下形式：
$\begin{array}{ll}{\text { minimize }} & {f_{0}(x)} \\ {\text { subject to }} & {f_{i}(x) \leqslant b_{i}, \quad i=1, \cdots, m}\end{array}$
- 優(yōu)化變量： $x=\left(x_{1}, \cdots, x_{n}\right)$
- 目標(biāo)函數(shù)： $f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$
- 約束函數(shù)： $f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}, \quad i=1, \cdots, m$
- 可行解z： $f_{1}(z) \leqslant b_{1}, \cdots, f_{m}(z) \leqslant b_{m}$
- 最優(yōu)解 $x^*$ : $f_{0}(z) \geqslant f_{0}\left(x^{*}\right)$ ,可行解域內(nèi)的最小值欲险。

2.應(yīng)用

投資組合優(yōu)化
器件尺寸
數(shù)據(jù)擬合：圖像處理
嵌入式優(yōu)化

3.求解最優(yōu)化問(wèn)題

最優(yōu)化問(wèn)題不同算法的有效性取決于諸多不同因素矾利，如目標(biāo)函數(shù)與約束函數(shù)倡鲸、優(yōu)化問(wèn)題所含變量與約束個(gè)數(shù)以及一些特殊結(jié)構(gòu)如稀疏矩陣

二.最小二和線性規(guī)劃

1.最小二乘

定義：最小二乘問(wèn)題是這樣一類(lèi)問(wèn)題等龙，它沒(méi)有約束條件（m=0）,目標(biāo)函數(shù)是若干項(xiàng)平方和甸箱，每一項(xiàng)具有形式 $a_{i}^{T} x-b_{i}$ 闽坡，其具體形式表示如下：
$\quad f_{0}(x)=\|A x-b\|_{2}^{2}=\sum_{i=1}^{k}\left(a_{i}^{T} x-b_{i}\right)$
其中A是k*n矩陣栽惶， $a_{i}^{T}$ 是A的行向量， $x \in \mathbf{R}^{n}$ 是優(yōu)化變量无午。

求解：
使用：
- 加權(quán)最小二乘
- 正則化

2.線性規(guī)劃

定義：線性規(guī)劃及其目標(biāo)函數(shù)都是線性的（ $f_{i}(\alpha x+\beta y)=\alpha f_{i}(x)+\beta f_{i}(y)$ ）媒役，線性規(guī)劃可以表述為 $\begin{array}{ll}{\text { minimize }} & {c^{T} x} \\ {\text { subject to }} & {a_{i}^{T} x \leqslant b_{i}, \quad i=1, \cdots, m}\end{array}$ 其中， $c, a_{1}, \cdots, a_{m} \in \mathbf{R}^{n}, b_{1}, \cdots, b_{m} \in \mathbf{R}$ 是問(wèn)題參數(shù)宪迟。
求解：
- 單純型法
- 內(nèi)點(diǎn)法
使用：
- 逼近問(wèn)題

三.凸優(yōu)化

定義：凸優(yōu)化具有以下形式
$\begin{array}{ll}{\text { minimize }} & {f_{0}(x)} \\ {\text { subject to }} & {f_{i}(x) \leqslant b_{i}, \quad i=1, \cdots, m}\end{array}$
其中 $f_{0}, \cdots, f_{m} : \mathbf{R}^{n} \rightarrow \mathbf{R}$ 為凸函數(shù)酣衷。所謂凸函數(shù)即對(duì)任意的 $x, y \in \mathbf{R}^{n}, \alpha, \beta \in \mathbf{R}$ 且 $\alpha+\beta=1, \alpha \geqslant 0, \beta \geqslant 0$ 這些函數(shù)滿足 $f_{i}(\alpha x+\beta y) \leqslant \alpha f_{i}(x)+\beta f_{i}(y)$ 。
- 線性規(guī)劃是一種特殊的凸優(yōu)化問(wèn)題次泽，
求解：
使用：

四.非線性規(guī)劃

五.優(yōu)化問(wèn)題分類(lèi)

凸優(yōu)化和非凸優(yōu)化（本質(zhì)）
線性規(guī)劃和非線性規(guī)劃
光滑優(yōu)化和非光滑優(yōu)化
可行域連續(xù)和離散
單目標(biāo)優(yōu)化和多優(yōu)目標(biāo)化問(wèn)題

五.本課程的主要內(nèi)容

凸集穿仪、凸函數(shù)、凸優(yōu)化
凸優(yōu)化的理論
凸優(yōu)化的算法

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末意荤，一起剝皮案震驚了整個(gè)濱河市啊片，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌玖像，老刑警劉巖紫谷，帶你破解...
沈念sama閱讀 221,820評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異捐寥，居然都是意外死亡笤昨，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,648評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)握恳，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)瞒窒，“玉大人，你說(shuō)我怎么就攤上這事乡洼〕绮茫” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 168,324評(píng)論 0贊 360
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵束昵，是天一觀的道長(zhǎng)拔稳。經(jīng)常有香客問(wèn)我，道長(zhǎng)妻怎，這世上最難降的妖魔是什么壳炎？我笑而不...
開(kāi)封第一講書(shū)人閱讀 59,714評(píng)論 1贊 297
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮，結(jié)果婚禮上匿辩，老公的妹妹穿的比我還像新娘腰耙。我一直安慰自己，他們只是感情好铲球，可當(dāng)我...
茶點(diǎn)故事閱讀 68,724評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布挺庞。她就那樣靜靜地躺著，像睡著了一般稼病。火紅的嫁衣襯著肌膚如雪选侨。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 52,328評(píng)論 1贊 310
城市分裂傳說(shuō)
那天然走，我揣著相機(jī)與錄音援制，去河邊找鬼。笑死芍瑞，一個(gè)胖子當(dāng)著我的面吹牛晨仑，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播拆檬，決...
沈念sama閱讀 40,897評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼洪己，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了竟贯？” 一聲冷哼從身側(cè)響起答捕，我...
開(kāi)封第一講書(shū)人閱讀 39,804評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎屑那，沒(méi)想到半個(gè)月后拱镐，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,345評(píng)論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡持际，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,431評(píng)論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年痢站，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片选酗。...
茶點(diǎn)故事閱讀 40,561評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖岳枷，靈堂內(nèi)的尸體忽然破棺而出芒填，到底是詐尸還是另有隱情，我是刑警寧澤空繁，帶...
沈念sama閱讀 36,238評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布殿衰，位于F島的核電站，受9級(jí)特大地震影響盛泡，放射性物質(zhì)發(fā)生泄漏闷祥。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,928評(píng)論 3贊 334
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望凯砍。院中可真熱鬧箱硕，春花似錦、人聲如沸悟衩。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 32,417評(píng)論 0贊 24
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)座泳。三九已至惠昔，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間挑势，已是汗流浹背镇防。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,528評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留潮饱，地道東北人来氧。一個(gè)月前我還...
沈念sama閱讀 48,983評(píng)論 3贊 376
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像饼齿，于是被迫代替她去往敵國(guó)和親饲漾。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,573評(píng)論 2贊 359