Fast Alternating Direction Method Of Multipliers For Quadratic Programs With Applications

Quadratic programming,which has a wide range of applications in fields such as operations research and economics,is a very important type of nonlinear programming problems.Designing algorithms for quadratic programming is not only to solve the problem itself,but also to better solve general nonlinear programming problem,because many optimization algorithms have quadratic sub-problems.Aiming at different types of quadratic programming problems,this thesis makes full use of the structure of the constraints to propose a more efficient alternating direction method of multipliers.In Chapter 1,we first introduce the background and recent advances status of quadratic programming problems.In Chapter 2,we summarize some basic symbols,definitions and theorems that will be used in this thesis,and give the relevant properties of some specific quadratic programming problems.In Chapter 3,we consider a kind of convex quadratic programming problem with mixed constraints including equality,inequality and non-negative constraints simultaneously.By introducing new variables to eliminate inequalities,the problem is equivalently transformed into a separable optimization model,and a new alternating direction method of multipliers is proposed.Compared to the traditional alternating direction method of multipliers whose sub-problem is an augmented system of linear equations,the scale of each sub-problem of the proposed method is the same as the original problem.Moreover,all sub-problems have explicit expressions.Theoretically,the global convergence of the new method is proved.Through a series of numerical experiments,the results show that the proposed method works well for solving large-scale quadratic programming problems.In Chapter 4,we consider the application of quadratic programming in the detection of copositive matrices.Since the detection of copositive matrix is an NP-hard problem,we transform the simplex-constrained standard quadratic programming model into two different forms of optimization models with special structures,which can be solved by the alternating direction method of multipliers.The first way is to separate the simplex constraint and the quadratic objective function by introducing variables,so that each subproblem is easy to be solved.The second way is to transform the quadratic objective function into a bilinear objective function by introducing variables,and separate the constraints,so that each sub-problem has a closed form solution.Both methods effectively overcome the computational difficulties caused by the nonconvexity problem of the original quadratic programming.Numerical results show that the method in this paper is effective for detecting the copositivity of matrices.Finally,we summarize the main contribution of the full thesis and make a prospect for the further work to be done in the future.