论文部分内容阅读
关于在l1范数约束下，非凸二次函数xTQx最大化问题:QPL1(Q): max xTQxs.t.‖x‖1≤1.(1)由于约束条件‖x‖1≤1的特殊结构导致问题异常难解.所以目前对该问题的处理方法一般是通过l1范数其它的表示形式把原问题等价变形，然后再对变形后的问题构建合适的凸配方松弛.由于对原问题处理的方法不同，则得到松弛的紧致性也有区别.目前问题QPL1(Q)的最紧致松弛是双非负松弛DNN(Q).本文在这个框架下，我们研究了双非负松弛DNN(Q)的复杂性，并对其进行相应的改进，进而推导出更紧致的松弛，得到更接近原问题最优值的上界. 本文的主要工作如下: 1.第二章在本章中我们首先讨论了，当原问题中的矩阵Q所有元素都大于等于0时，原问题QPL1(Q)的双非负松弛的表示形式.然后我们通过矩阵分块分解法得到与双非负松弛DNN(Q)等价的表示形式DNNNEw(Q).并且对双非负松弛新的表示形式进行简化处理，得到简便的双非负松弛DNN(Q).最后证明了对矩阵Q限制后，双非负松弛DNN(Q)与简便的松弛DNN(Q)的最优值相等. 2.第三章在本章中主要表述了四种思路对问题QPL1(Q)的双非负松弛DNN(Q)进行改进.这四种思路分别是:第一种思路是通过使用l1范数新的表示形式([25]);第二种是利用单纯形的性质改进问题QPL1(Q)的双非负松弛DNN(Q).第三种是对QPL1(Q)的双非负松弛DNN(Q)中的限制域进行线性添加;第四种是利用D.C方法的思想，把原问题的标准二次函数QPS(Q)分裂成两个问题，然后再分别对这两个问题进行处理，达到对双非负松弛进行紧致的效果.