Quadratic Programming (QP) problem is a natural generalization of well-known Linear Programming (LP) problem. QP problem is formulated as a problem to minimize a linear objective function subject to a system of linear equalities and inequalities.
The continuation method is a powerful tool for solving a system of nonlinear equations. In the continuation method, the continuation parameter β is introduced into the original problem P and a parameterized problem P(β) is constructed. Assuming that the optimal solution to P(β), for β=0, can be trivially or easily found, and that the optimal solution to P(β), for β=1, will be the desired solution to the original problem P, a trajectory of the solution to P(β) is followed by increasing the value of β from 0 to 1.
In this paper, based on the continuation method, a path following method called the capacity method is constructed for solving QP problem. The basic idea of the capacity method is to follow a trajectory of Kuhn-Tucker point when the value of β is increased from 0 to 1. It is shown that the trajectory is expressed as a piecewise-linear function of β. Therefore the optimal solution can be found very efficiently by following the piecewise-linear trajectory.
In this paper, firstly, the assumption that the right-hand-side vector of the constraint equations must be positive, which restricts the applicability of the capacity method, is dropped and a method for transforming any QP problem to the standard form of the capacity method is presented. Secondly, the basis matrix of QP is factorized by using an LDL^T factorization, and the factorization is efficiently updated by using matrix modification techniques. Then the proposed method is applied to some test problems, and numerical results indicate the effectiveness of the method.