English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The conjugate gradient (CG) method is an efficient iterative method forsolving large-scale strongly convex quadratic programming (QP). In this paperwe propose some generalized CG (GCG) methods for solving the$\ell_1$-regularized (possibly not strongly) convex QP that terminate at anoptimal solution in a finite number of iterations. At each iteration, ourmethods first identify a face of an orthant and then either perform an exactline search along the direction of the negative projected minimum-normsubgradient of the objective function or execute a CG subroutine that conductsa sequence of CG iterations until a CG iterate crosses the boundary of thisface or an approximate minimizer of over this face or a subface is found. Wedetermine which type of step should be taken by comparing the magnitude of somecomponents of the minimum-norm subgradient of the objective function to that ofits rest components. Our analysis on finite convergence of these methods makesuse of an error bound result and some key properties of the aforementionedexact line search and the CG subroutine. We also show that the proposed methodsare capable of finding an approximate solution of the problem by allowing someinexactness on the execution of the CG subroutine. The overall arithmeticoperation cost of our GCG methods for finding an $\epsilon$-optimal solutiondepends on $\epsilon$ in $O(\log(1/\epsilon))$, which is superior to theaccelerated proximal gradient method [2,23] that depends on $\epsilon$ in$O(1/\sqrt{\epsilon})$. In addition, our GCG methods can be extendedstraightforwardly to solve box-constrained convex QP with finite convergence.Numerical results demonstrate that our methods are very favorable for solvingill-conditioned problems.

Generalized Conjugate Gradient Methods for $\ell_1$ Regularized Convex Quadratic Programming with Finite Convergence