Convex quartic problems: homogenized gradient method and preconditioning

Radu-Alexandru Dragomir and Yurii Nesterov ()
Additional contact information
Radu-Alexandru Dragomir: EPFL
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

No 2024026, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We consider a convex minimization problem for which the objective is the sum of a homogeneous polynomial of degree four and a linear term. Such task arises as a subproblem in algorithms for quadratic inverse problems with a difference-of-convex structure. We design a first-order method called Homogenized Gradient, along with an accelerated version, which enjoy fast convergence rates of respectively O(κ2/K2) and O(κ2/K4) in relative accuracy, where K is the iteration counter. The constant κ is the quartic condition number of the problem. Then, we show that for a certain class of problems, it is possible to compute a preconditioner n, where n is the problem dimension. To establish this, we study the more general problem of finding the best quadratic approximation of an lp norm composed with a quadratic map. Our construction involves a generalization of the so-called Lewis weights.

Pages: 29
Date: 2024-10-10
References: Add references at CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2024026

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().