Applications Of Polynomial Optimization Methods In Quadratic Programming Problems

The polynomial optimization problem(POP) is commonly seen in science andengineering. With a polynomial objective and constraints, it includes common opti-mization problems like linear programming(LP), quadratic programming(QP), whichare of great importance in optimization. Recently, Lasserre developed a new methodto achieve optimal values of polynomial optimization problems[1]. Based on severalrepresentation theorems in number theory, he constructed a series of semidefinite pro-gramming(SDP) relaxation problems, whose optimal values approximate the optimumof the original problem. The method transforms a POP into SDP problems. The formalmaybe NP-hard, while the latters are polynomial solvable. What’s more, the trans-formation is uniform for all kinds of POPs, which makes it widely applicable. Theobjective and constraints in QP are quadratic functions. QP has important applicationsin a broad range of subject areas, including support vector machine, graph theory, sup-ply chain management, etc. As a subclass of POP, QP problems can be solved by anymethod of POP directly. Diferent from classical methods, Lasserre’s approach mayhave performance better than those old methods. This motivates us to use POP methodsolve several QP problems practically. In currently avaliable literature about POP, onlytheoretical results are given, no actual numerical results. This paper’s work fill the gap.Numerical experiments show that the POP method is unsatisfactory in computa-tions, though it is elegant in theory. Despite it provides objective value more accuratethan other methods, it sufers from low computational efcient heavily. As a result,only problems of small size can be solved.In this paper, we use Lasserre’s POP method, along with some control method,to solve several QP problems. First we describe this POP method in details, then wepresent numerical experiments. Finally, we analysis the result and draw conclusions.