Title: Augmented lagrangian two-stage algorithm for LP and SCQP,
Abstract: In this paper, we consider a framework of projected gradient iterations for
linear programming (LP) and an augmented lagrangian two-stage algorithm for
strongly convex quadratic programming (SCQP). Based on the framework of
projected gradient, LP problem is transformed to a finite number of SCQP
problems. Furthermore, we give an estimate of the number of the SCQP problems.
We use augmented lagrangian method (ALM) to solve SCQP and each augmented
lagrangian subproblem is solved by a two-stage algorithm exactly, which ensures
the superlinear convergence of ALM for SCQP. The two-stage algorithm consists
of the accelerated proximal gradient algorithm as the first stage algorithm
which provides an approximate solution, and a simplified parametric active-set
method as the second stage algorithm which gives an exact solution. Moreover,
we improve the parametric active-set method by introducing a sorting technique
to update the cholesky factorization. Finally, the numerical experiments on
randomly generated and real-world test problems indicate that our algorithm is
effective, especially for random problems.