  In this paper, a proximal augmented Lagrangian homotopy (PAL-Hom) method for
solving convex quadratic programming problems is proposed. This method takes
the proximal augmented Lagrangian method as the outer iteration. To solve the
proximal augmented Lagrangian subproblems, a homotopy method is presented as
the inner iteration. The homotopy method tracks the piecewise-linear solution
path of a parametric quadratic programming problem whose start problem takes an
approximate solution as its solution and the target problem is the subproblem
to be solved. To improve the performance of the homotopy method, the
accelerated proximal gradient method is used to obtain a fairly good
approximate solution that implies a good prediction of the optimal active set.
Moreover, a sorting technique for the Cholesky factor update as well as an
$\varepsilon$-relaxation technique for checking primal-dual feasibility and
correcting the active sets are presented to improve the efficiency and
robustness of the homotopy method. Simultaneously, a proximal-point-based
AL-Hom method which is shown to converge in finite number of steps, is applied
to linear programming. Numerical experiments on randomly generated problems and
the problems from the CUTEr and Netlib test collections, support vector
machines (SVMs) and contact problems of elasticity demonstrate that PAL-Hom is
faster than the active-set methods and the parametric active set methods and is
competitive to the interior-point methods and the specialized algorithms
designed for specific models (e.g., sequential minimal optimization (SMO)
method for SVMs).
