Generalized Conjugate Gradient Methods for $\ell_1$ Regularized Convex
  Quadratic Programming with Finite Convergence
  The conjugate gradient (CG) method is an efficient iterative method for
solving large-scale strongly convex quadratic programming (QP). In this paper
we propose some generalized CG (GCG) methods for solving the
$\ell_1$-regularized (possibly not strongly) convex QP that terminate at an
optimal solution in a finite number of iterations. At each iteration, our
methods first identify a face of an orthant and then either perform an exact
line search along the direction of the negative projected minimum-norm
subgradient of the objective function or execute a CG subroutine that conducts
a sequence of CG iterations until a CG iterate crosses the boundary of this
face or an approximate minimizer of over this face or a subface is found. We
determine which type of step should be taken by comparing the magnitude of some
components of the minimum-norm subgradient of the objective function to that of
its rest components. Our analysis on finite convergence of these methods makes
use of an error bound result and some key properties of the aforementioned
exact line search and the CG subroutine. We also show that the proposed methods
are capable of finding an approximate solution of the problem by allowing some
inexactness on the execution of the CG subroutine. The overall arithmetic
operation cost of our GCG methods for finding an $\epsilon$-optimal solution
depends on $\epsilon$ in $O(\log(1/\epsilon))$, which is superior to the
accelerated proximal gradient method [2,23] that depends on $\epsilon$ in
$O(1/\sqrt{\epsilon})$. In addition, our GCG methods can be extended
straightforwardly to solve box-constrained convex QP with finite convergence.
Numerical results demonstrate that our methods are very favorable for solving
ill-conditioned problems.
