Some Researching On Maximizing Nonconvex Quadratic Functions Over The L₁-Ball

Conside the optimization problem of maximizing a quadratic from over the l1-Ball: The nature of the norm structure makes this problem extremely hard to analyze,and as a consequence, the same difficulties are encountered when trying to built suitable approximations for this problem by some tractable convex counterpart formulation. So the method on this problem is to convert the original problem. There are two kinds transformation of ideas:One is directly convert the problem equivalently; Another is that represent the original problem by l1 deformation of other forms. Then built suitable approximations for this problem by some tractable convex counterpart formulations. The relaxations of the original problem are good or bad, in which the best relaxation is the double nonnegative relaxation. Based on the structure, we study and improve the complexity of the double nonnegative relaxation.The main job of this paper can be divided into the following two aspects:In the second chapter, we study the complexity of the double nonnegative relaxation, and get a new relaxation DNN(Q) by changing the form of the double nonnegative relaxation. In the last, we discuss if certain conditions of the matrix are restricted to the original problem, how the double nonnegative relaxation of the original problem QPL1(Q) will change. And we show that the optimal value of DNN(Q) is equal to the optimal value of new relaxation of the DNN(Q).In the third chapter, we propose four ideas to further improve the double nonnegative re-laxation of the QPL1(Q). These four ideas can be summarized as follows First, by using the new representation l1 norm to get a new double nonnegative relaxation. Second, improving the double nonnegative relaxation via the nature of the simplex. Third, improving the double non-negative relaxation via adding linear cuts. Fourth, we split the standard quadratic model(QP5)of QPL1(Q) into two problems. Then we further extend the class of decompositions by relaxing the vertex optimality condition on one of the two quadratic forms to the condition of vertex or edge optimality.