Optimal Solutions And Solving Algorithms For The Indefinite Quadratic Programs

In this article, we disscuss the optimal solutions and solving algorithms for the indefinite quadratic programs . This paper mainly consists of three sections. In the first section, motivated by the trust region subproblem, we consider the indefinite quadratic minimization over a particular D.C. set, whose points are between two balls possessing the same core. We establish first the stability of the Lagrangian duality relative to the problem, namely, there is no duality gap. This elementary property is then used to derive both global optimality conditions in the problem and the solution sets, which can be described with the help of its dual solutions exactly as in convex programming. An example is given to illustrate the nature of the results. Meanwhile, it provides a solving method for the primal problem.In the second section, we propose another solving algorithm for the problem advanced in the first section. Thanks to the detailed descriptions of the structure of the solution sets in the first section, in the case when the smallest eigenvalue of the quadratic objective function is nonzero, we observe that the problem can be cast as two trust region subproblems. Due to the particular structure of the problem, we devise a D.C. algorithm to solve it, which is base on the D.C. decomposition of the objective function. It is quite simple and requires matrix-vector products only. Moreover it can converge to the global solution of the trust-region problem. Finally, we make the MATLAB code for experiment.In the third section, characterization of the optimal solutions of cone-constrained indefinite quadratic minimization is presented. When the matrix of the quadratic objective function is block diagonal and the one of the constrained function is non-singular, the Lagrange's method of multipliers is used to obtain the property that there is no duality gap between the optimal value of primal program and the one of the dual program if a common value of negative infinity is permitted. With the aid of the solution sets of the dual program, the ones of the primal program are described exactly. Finally, the results above are extended to the general symmetric matrices of the objective function and the constrained function.