Optimization problems represented by Conic Programming.pdf

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

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