Optimization problems represented by Conic Programming.pdf

1、最近20年來凸優(yōu)化問題的進(jìn)展集中于凸錐優(yōu)化問題方面.凸錐優(yōu)化問題最具代表性的三類問題是：線性規(guī)劃問題,二階錐規(guī)劃問題以及半定規(guī)劃問題。凸錐優(yōu)化問題是一種特殊的凸優(yōu)化問題,它有很好的理論性質(zhì),也有高效可靠的求解算法,例如內(nèi)點(diǎn)算法.許多現(xiàn)實(shí)中的應(yīng)用問題都可以通過凸錐優(yōu)化問題來求解,例如自動(dòng)化控制系統(tǒng),信號(hào)處理等等；凸錐優(yōu)化問題也可以應(yīng)用于組合優(yōu)化及其他一些NP困難問題,比如圖的最大割問題,無線傳感器網(wǎng)絡(luò)中的定位問題。將問題松弛化為凸錐優(yōu)化問

2、題,就可以得到原問題的好的近似最優(yōu)解。因此將一個(gè)(非)凸優(yōu)化問題等價(jià)的轉(zhuǎn)化,或適當(dāng)?shù)乃沙诨癁楹线m的凸錐優(yōu)化問題是很有意義的。 在本文中我們首先討論如何將某一類凸問題轉(zhuǎn)化為二階錐規(guī)劃問題或半定規(guī)劃問題,例如,求解一個(gè)對(duì)稱矩陣的k個(gè)最大特征值的和的問題；我們還將討論如何將某些數(shù)據(jù)擾動(dòng)的優(yōu)化問題轉(zhuǎn)化為確定的二階錐規(guī)劃問題或者半定規(guī)劃問題,例如,求解系數(shù)在一個(gè)矩形區(qū)域內(nèi)擾動(dòng)的最小p-范數(shù)問題(p=1,2,∞);最后討論半定規(guī)劃問題的一個(gè)