IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2024026.html

Convex quartic problems: homogenized gradient method and preconditioning

Author

Listed:
  • Dragomir, Radu-Alexandru

    (EPFL)

  • Nesterov, Yurii

    (Université catholique de Louvain, LIDAM/CORE, Belgium)

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.

Suggested Citation

  • Dragomir, Radu-Alexandru & Nesterov, Yurii, 2024. "Convex quartic problems: homogenized gradient method and preconditioning," LIDAM Discussion Papers CORE 2024026, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2024026
    as

    Download full text from publisher

    File URL: https://dial.uclouvain.be/pr/boreal/en/object/boreal%3A292771/datastream/PDF_01/view
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Le An & Pham Tao, 2005. "The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems," Annals of Operations Research, Springer, vol. 133(1), pages 23-46, January.
    2. ANSTREICHER, Kurt M., 1999. "Ellipsoidal approximations of convex sets based on the volumetric barrier," LIDAM Reprints CORE 1393, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Da Kuang & Sangwoon Yun & Haesun Park, 2015. "SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering," Journal of Global Optimization, Springer, vol. 62(3), pages 545-574, July.
    4. NESTEROV Yurii,, 2020. "Superfast second-order methods for unconstrained convex optimization," LIDAM Discussion Papers CORE 2020007, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Filip Hanzely & Peter Richtárik & Lin Xiao, 2021. "Accelerated Bregman proximal gradient methods for relatively smooth convex optimization," Computational Optimization and Applications, Springer, vol. 79(2), pages 405-440, June.
    6. Leonid G. Khachiyan, 1996. "Rounding of Polytopes in the Real Number Model of Computation," Mathematics of Operations Research, INFORMS, vol. 21(2), pages 307-320, May.
    7. Heinz H. Bauschke & Jérôme Bolte & Marc Teboulle, 2017. "A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 330-348, May.
    8. K. M. Anstreicher, 1999. "Ellipsoidal Approximations of Convex Sets Based on the Volumetric Barrier," Mathematics of Operations Research, INFORMS, vol. 24(1), pages 193-203, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sanjay Mehrotra & Zhifeng Li, 2011. "Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices," Journal of Global Optimization, Springer, vol. 49(4), pages 623-649, April.
    2. Renbo Zhao, 2026. "New Analysis of an Away-Step Frank–Wolfe Method for Minimizing Log-Homogeneous Barriers," Mathematics of Operations Research, INFORMS, vol. 51(1), pages 35-59, January.
    3. Yin Liu & Sam Davanloo Tajbakhsh, 2023. "Stochastic Composition Optimization of Functions Without Lipschitz Continuous Gradient," Journal of Optimization Theory and Applications, Springer, vol. 198(1), pages 239-289, July.
    4. Radu-Alexandru Dragomir & Alexandre d’Aspremont & Jérôme Bolte, 2021. "Quartic First-Order Methods for Low-Rank Minimization," Journal of Optimization Theory and Applications, Springer, vol. 189(2), pages 341-363, May.
    5. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization," Computational Optimization and Applications, Springer, vol. 79(3), pages 681-715, July.
    6. Abbaszadehpeivasti, Hadi, 2024. "Performance analysis of optimization methods for machine learning," Other publications TiSEM 3050a62d-1a1f-494e-99ef-7, Tilburg University, School of Economics and Management.
    7. Kurt M. Anstreicher, 2000. "The Volumetric Barrier for Semidefinite Programming," Mathematics of Operations Research, INFORMS, vol. 25(3), pages 365-380, August.
    8. Shota Takahashi & Akiko Takeda, 2025. "Approximate bregman proximal gradient algorithm for relatively smooth nonconvex optimization," Computational Optimization and Applications, Springer, vol. 90(1), pages 227-256, January.
    9. Ziyuan Wang & Andreas Themelis & Hongjia Ou & Xianfu Wang, 2024. "A Mirror Inertial Forward–Reflected–Backward Splitting: Convergence Analysis Beyond Convexity and Lipschitz Smoothness," Journal of Optimization Theory and Applications, Springer, vol. 203(2), pages 1127-1159, November.
    10. Matthew K. Tam & Daniel J. Uteda, 2023. "Bregman-Golden Ratio Algorithms for Variational Inequalities," Journal of Optimization Theory and Applications, Springer, vol. 199(3), pages 993-1021, December.
    11. Shota Takahashi & Mituhiro Fukuda & Mirai Tanaka, 2022. "New Bregman proximal type algorithms for solving DC optimization problems," Computational Optimization and Applications, Springer, vol. 83(3), pages 893-931, December.
    12. Laura Girometti & Martin Huska & Alessandro Lanza & Serena Morigi, 2024. "Convex Predictor–Nonconvex Corrector Optimization Strategy with Application to Signal Decomposition," Journal of Optimization Theory and Applications, Springer, vol. 202(3), pages 1286-1325, September.
    13. Rundong Du & Barry Drake & Haesun Park, 2019. "Hybrid clustering based on content and connection structure using joint nonnegative matrix factorization," Journal of Global Optimization, Springer, vol. 74(4), pages 861-877, August.
    14. J. X. Cruz Neto & P. R. Oliveira & A. Soubeyran & J. C. O. Souza, 2020. "A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem," Annals of Operations Research, Springer, vol. 289(2), pages 313-339, June.
    15. M. Bierlaire & M. Thémans & N. Zufferey, 2010. "A Heuristic for Nonlinear Global Optimization," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 59-70, February.
    16. HyungSeon Oh, 2021. "Distributed optimal power flow," PLOS ONE, Public Library of Science, vol. 16(6), pages 1-27, June.
    17. Zehui Jia & Jieru Huang & Xingju Cai, 2021. "Proximal-like incremental aggregated gradient method with Bregman distance in weakly convex optimization problems," Journal of Global Optimization, Springer, vol. 80(4), pages 841-864, August.
    18. Bai, Jushan & Liao, Yuan, 2016. "Efficient estimation of approximate factor models via penalized maximum likelihood," Journal of Econometrics, Elsevier, vol. 191(1), pages 1-18.
    19. William Haskell & J. Shanthikumar & Z. Shen, 2013. "Optimization with a class of multivariate integral stochastic order constraints," Annals of Operations Research, Springer, vol. 206(1), pages 147-162, July.
    20. Selin Ahipaşaoğlu, 2015. "Fast algorithms for the minimum volume estimator," Journal of Global Optimization, Springer, vol. 62(2), pages 351-370, June.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2024026. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.