一范數約束下非凸二次函數最大化問題的研究.pdf

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

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

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