一范數(shù)約束下非凸二次函數(shù)最大化問(wèn)題的研究.pdf

1、關(guān)于在l1范數(shù)約束下，非凸二次函數(shù)xTQx最大化問(wèn)題:QPL1(Q): max xTQxs.t.‖x‖1≤1.(1)由于約束條件‖x‖1≤1的特殊結(jié)構(gòu)導(dǎo)致問(wèn)題異常難解.所以目前對(duì)該問(wèn)題的處理方法一般是通過(guò)l1范數(shù)其它的表示形式把原問(wèn)題等價(jià)變形，然后再對(duì)變形后的問(wèn)題構(gòu)建合適的凸配方松弛.由于對(duì)原問(wèn)題處理的方法不同，則得到松弛的緊致性也有區(qū)別.目前問(wèn)題QPL1(Q)的最緊致松弛是雙非負(fù)松弛DNN(Q').本文在這個(gè)框架下，我們研究了雙非負(fù)松

2、弛DNN(Q')的復(fù)雜性，并對(duì)其進(jìn)行相應(yīng)的改進(jìn)，進(jìn)而推導(dǎo)出更緊致的松弛，得到更接近原問(wèn)題最優(yōu)值的上界.
　　本文的主要工作如下:
　　1.第二章在本章中我們首先討論了，當(dāng)原問(wèn)題中的矩陣Q所有元素都大于等于0時(shí)，原問(wèn)題QPL1(Q)的雙非負(fù)松弛的表示形式.然后我們通過(guò)矩陣分塊分解法得到與雙非負(fù)松弛DNN(Q')等價(jià)的表示形式DNNNEw(Q').并且對(duì)雙非負(fù)松弛新的表示形式進(jìn)行簡(jiǎn)化處理，得到簡(jiǎn)便的雙非負(fù)松弛DNN'(Q).最后

3、證明了對(duì)矩陣Q限制后，雙非負(fù)松弛DNN(Q')與簡(jiǎn)便的松弛DNN'(Q)的最優(yōu)值相等.
　　2.第三章在本章中主要表述了四種思路對(duì)問(wèn)題QPL1(Q)的雙非負(fù)松弛DNN(Q')進(jìn)行改進(jìn).這四種思路分別是:第一種思路是通過(guò)使用l1范數(shù)新的表示形式([25]);第二種是利用單純形的性質(zhì)改進(jìn)問(wèn)題QPL1(Q)的雙非負(fù)松弛DNN(Q').第三種是對(duì)QPL1(Q)的雙非負(fù)松弛DNN(Q')中的限制域進(jìn)行線(xiàn)性添加;第四種是利用D.C方法的思想，