兩類二次約束二次優(yōu)化問題的SDP松弛分解算法研究.pdf

1、二次約束二次優(yōu)化問題在實(shí)際中具有廣泛的應(yīng)用，如信賴域子問題、變形最小方差問題、信號(hào)處理問題等。但此問題是一個(gè)NP-hard問題，目前尚沒有較好的求解算法。本文將在Strum和Zhang的工作基礎(chǔ)上，針對(duì)一般的二次約束二次優(yōu)化問題的分解算法進(jìn)行研究。
　　 本文主要做了如下幾個(gè)方面的工作：
　　 1.找到了一個(gè)存在負(fù)特征值的二次約束二次優(yōu)化問題實(shí)例，說明了我們研究的問題可能是非凸的，一般是一個(gè)復(fù)雜問題。
　　 2.

2、研究了一類特殊的二次約束二次優(yōu)化問題，此問題僅帶有一個(gè)二次約束。我們給出了一個(gè)簡(jiǎn)單的秩一分解算法來獲得該問題的精確解或近似解，并利用SEDUMI編程實(shí)現(xiàn)。同時(shí)給出了此算法的有效性理論證明，初步的數(shù)值實(shí)驗(yàn)結(jié)果也表明了該算法的有效性。
　　 3.我們將上述算法應(yīng)用到求解帶有兩個(gè)二次約束的二次優(yōu)化問題（常稱為兩球問題）中，初步的數(shù)值結(jié)果表明，該算法對(duì)求解兩球問題是無效的，有時(shí)會(huì)存在對(duì)偶間隙，因此兩球問題仍是公開問題。
　　 4