A Fast Algorithm for Linearly Constrained Quadratic Programming Problems with Lower and Upper Bounds

摘要

There are many applications related to linearly constrained quadratic programs subjected to upper and lower bounds. Lower bounds and upper bounds are treated as different constraints by common quadratic programming algorithms. These traditional treatments significantly increase the computation of quadratic programming problems. We employ pivoting algorithm to solve quadratic programming models. The algorithm can convert the quadratic programming with upper and lower bounds into quadratic programming with upper or lower bounds equivalently by making full use of the Karush-Kuhn-Tucker (KKT) conditions of the problem and decrease the computation. The algorithm can further decrease calculation to obtain solution of quadratic programming problems by solving a smaller linear inequality system which is the linear part of KKT conditions for the quadratic programming problems and is equivalent to the KKT conditions while maintaining complementarity conditions of the KKT conditions to hold.