Algorithm For Two Positive Definite Quadratic Programming Problems With Special Structure

Quadratic optimization comprises one of the most important area in nonlinear programming. Numerous problems in real world applications can be expressed as quadratic programming problems. Moreover, many algorithms for nonlinear programming take the quadratic problems as their subproblems. So, the research on quadratic oprimization has a great significance.In chapter 1, we gave a brief overview of quadratic programming problems, including their practical application and some important properties. Then, we introduced some important techniques for solving positive definite quadratic programming.In chapter 2, we presented a method for solving positive definite quadratic programming with coupled-block structure. The primal problem is split into two parts: a master problem and several subproblems. With the information communication between these two parts, we can finally get the optimal solution of the primal problem. This algorithm is a generalization of Dantzig-Wolfe decomposition method.In chapter 3, we presented a dual method for solving positive definite quadratic programming with box constraints. We tried to find the active constraints of the dual problem. In each iteration, a quadratic subproblem with equality constraints is to be solved firstly, if the optimal conditions is not satisfied, we need to add a constraint into the subproblem or remove one from it. After a limited number of iterations, we can get the optimal solution of the primal problem.We concluded the thesis with chapter 4 by proposing two positive definite quadratic problems for further research.