優(yōu)化方法及其應(yīng)用北交大課件

優(yōu)化方法及其應(yīng)用數(shù)學(xué)與系統(tǒng)科學(xué)研究院人人網(wǎng)：袁亞湘提綱引子：優(yōu)化是什么？幾個(gè)簡單優(yōu)化方法介紹若干優(yōu)化問題舉例

1)生產(chǎn)、運(yùn)輸、調(diào)度問題（線性規(guī)劃）2)壓縮感知、Netflix問題（稀疏優(yōu)化，L1）

3)分類問題、機(jī)器學(xué)習(xí)（二次規(guī)劃）

4)蛋白質(zhì)折疊

、無線定位問題（半定規(guī)劃）5)傳染病模型（微分方程約束的優(yōu)化）什么是優(yōu)化？田忌賽馬

齊威王田忌齊威王田忌上A>BA>F中C>DC<B下E>FE<D3:01:2中國郵遞員問題旅行商問題

（13173點(diǎn)）優(yōu)化問題的數(shù)學(xué)形式

非線性規(guī)劃（優(yōu)化）問題

minimizef(x)subjecttoci(x)=0,i=1,2,…,me

ci(x)≥0,i=me+1,…,m幾個(gè)簡單優(yōu)化方法華羅庚（1910－1985）華羅庚在大慶油田講優(yōu)選法華羅庚在礦山推廣優(yōu)選法華羅庚在工廠、車間[0,1]上求f(x)的極大值[a,b]上的連續(xù)函數(shù)f(x)是單峰的（只有一個(gè)最大值點(diǎn)）,求解maxf(x)

任取a<c<d<b,如果f(c)<f(d),則我們只需在[c,b]上求maxf(x)

如何選取c,d?最優(yōu)的c,d1）max[b-c,d-a]達(dá)到最小

c≈d=(a+b)/2!2)除了c,d之外還可以求若干次函數(shù)值?

一次c=1/3,d=2/3

兩次c=2/5,d=3/5?

達(dá).芬奇與黃金分割黃金分割法：給出[0，1]：

X=0.382Y=0.618新區(qū)間：

[0,0.618]or[0.382,1]

最速下降法αk使f(x＋αd)達(dá)到最?。ň_搜索）A.Cauchy,ComptesRendusdeL’AcadmiadesSciences25(1847)536-538Cauchy（1789－1859）最速下降法收斂速度

假定f(x)是二次凸函數(shù)收斂速度：

最速下降法應(yīng)用于f(x,y)=100x2+y2Barzilai&BorweinMethod

方向

(最速下降－最好方向)

步長

(上一次的精確搜索步長)

最好的d+上一步最好的α

最好J.M.Borwein(1951-

擬牛頓法牛頓:擬牛頓:如何選取B？

如何“擬”牛頓？擬牛頓方程：Davidon(1959),FletcherandPowell(1963):

N.Trefethen:Whoinventedthegreatnumericalalgorithms?半定規(guī)劃（SDP）Semi-DefiniteProgramming(SDP)min<C,X>s.t.<A,X>=b

X≥0

<C,X>=TraceCTX

非凸問題（松弛）凸問題whenX=xxT

xTCx=<C,X>內(nèi)點(diǎn)法(Karmarkar,1984)xk>0Log罰函數(shù)方法牛頓法中心路徑

實(shí)際問題的優(yōu)化建模生產(chǎn)問題有m種原材料，可生產(chǎn)n種產(chǎn)品。如何安排生產(chǎn)計(jì)劃使產(chǎn)值最多？

maximizec1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

≤b1…….am1x1+am2x2+…+amnxn≤bmx1

≥0,…xn≥0

調(diào)度問題航空（飛機(jī)調(diào)度，空乘人員調(diào)度）軌道交通（車次安排，車頭調(diào)度）城市交通（紅綠燈控制）突發(fā)事件后時(shí)間表的恢復(fù)（例子：“9.11”后美國航空運(yùn)輸恢復(fù)）美國電網(wǎng)優(yōu)化壓縮感知（CompressiveSensing)盡可能少的存貯，盡可能清晰的圖像求解

Ax=b，x∈Rn

A∈Rm×n,b∈Rm.m<<n.要求：x盡量多的分量為零!D.L.Donoho(IEETransIT,2006)壓縮感知minimize||x||0s.t.Ax=bNP-hard!non-convex,discontinuousminimize||x||1s.t.Ax=bconvexproblem,continuous壓縮感知——

L1優(yōu)化Netflix百萬美元獎(jiǎng)電影評(píng)價(jià)電影打分Netflix問題從1998年10月到2005年12月搜集數(shù)據(jù)（請客戶給電影打分）480,189用戶17,770電影100,480,507分?jǐn)?shù)（1到5）問題：如何填補(bǔ)沒有打分的數(shù)據(jù)？矩陣完整化(MatrixCompletion)

給出矩陣A中的一些元素：

Aij

((i,j)inS)

求A的其他元素(例子：DVD出租）

數(shù)學(xué)問題：

minimizeRank(X)s.t.Xij=Aij(i.j)inS松弛問題min||X||*s.t.Xij=Aij(i.j)inS

where||X||*isthenuclearnorm分類問題（機(jī)器學(xué)習(xí)）支撐向量機(jī)（VSM）蛋白質(zhì)結(jié)構(gòu)問題已知若干原子（分子）之間的距離，如何確定它們在空間的位置？蛋白質(zhì)結(jié)構(gòu)問題（距離幾何）

設(shè)S是一集合，給出dij,(i,j)∈S

求解xi

使得：

||xi–xj||2=dij,(i,j)∈S無線網(wǎng)絡(luò)定位問題Ad-hocwirelesssensornetwork.已知若干ak的位置，如何利用部分距離

dij和zik

確定所有未知點(diǎn)xi在空間的位置？設(shè)S1,

S2是兩集合，求解

||xi–xj||2=dij,(i,j)∈S1||xi–ak||2=zik,(i,k)∈S2傳感定位問題－優(yōu)化建模優(yōu)化模型：（Biswas&Ye,2004)SDP（凸）松弛xTBx---二次函數(shù)（非凸）取X=xxTT則有xTBx=<B,X>---ConvexonX

其中<A,B>=trace(ATB)UncertaintyConstraintsUncertaintyconstraints:Pr(ci(x,u)<0)>1-εBertsimas,D.,Brown,D.,andCaramanis,C.TheoryandApplicationsofRobustOptimizationSIAMReview,53(2011),pp.464-501傳染病研究在時(shí)間t1t2,…tn

得到測量數(shù)據(jù)

y1,y2,…yn(d維向量）希望找到解x(t):x(ti)近似yix(t)滿足某一模型

dij和zik

確定所有未知點(diǎn)xi在空間的位置？

微分方程約束的優(yōu)化問題向量β是優(yōu)化變量LeonhardEuler(1707-1783)

由于宇宙組成是最完美也是最聰明造物主之產(chǎn)物，宇宙間萬物無不遵循某種最大或最小準(zhǔn)則

———?dú)W拉

Für,dadasGewebedesUnive