Convex quartic problems: homogenized gradient method and preconditioning
(2024) , 29 pages
Files
CORE_DP_2024-26.pdf
Open Access - Adobe PDF
- 988.14 KB
Details
- Authors
- 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.
- Affiliations
Citations
Dragomir, R. A., & Nesterov, Y. (2024). Convex quartic problems: homogenized gradient method and preconditioning (LIDAM Discussion Paper CORE 2024/26). https://hdl.handle.net/2078.5/233880