IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v89y2024i3d10.1007_s10898-023-01361-1.html
   My bibliography  Save this article

The appeals of quadratic majorization–minimization

Author

Listed:
  • Marc C. Robini

    (INSA Lyon)

  • Lihui Wang

    (Guizhou University)

  • Yuemin Zhu

    (INSA Lyon)

Abstract

Majorization–minimization (MM) is a versatile optimization technique that operates on surrogate functions satisfying tangency and domination conditions. Our focus is on differentiable optimization using inexact MM with quadratic surrogates, which amounts to approximately solving a sequence of symmetric positive definite systems. We begin by investigating the convergence properties of this process, from subconvergence to R-linear convergence, with emphasis on tame objectives. Then we provide a numerically stable implementation based on truncated conjugate gradient. Applications to multidimensional scaling and regularized inversion are discussed and illustrated through numerical experiments on graph layout and X-ray tomography. In the end, quadratic MM not only offers solid guarantees of convergence and stability, but is robust to the choice of its control parameters.

Suggested Citation

  • Marc C. Robini & Lihui Wang & Yuemin Zhu, 2024. "The appeals of quadratic majorization–minimization," Journal of Global Optimization, Springer, vol. 89(3), pages 509-558, July.
    • Handle: RePEc:spr:jglopt:v:89:y:2024:i:3:d:10.1007_s10898-023-01361-1
    DOI: 10.1007/s10898-023-01361-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-023-01361-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-023-01361-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Groenen, Patrick J. F. & van de Velden, Michel, 2016. "Multidimensional Scaling by Majorization: A Review," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 73(i08).
    2. Jérôme Bolte & Edouard Pauwels, 2016. "Majorization-Minimization Procedures and Convergence of SQP Methods for Semi-Algebraic and Tame Programs," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 442-465, May.
    3. Emilie Chouzenoux & Jean-Christophe Pesquet & Audrey Repetti, 2014. "Variable Metric Forward–Backward Algorithm for Minimizing the Sum of a Differentiable Function and a Convex Function," Journal of Optimization Theory and Applications, Springer, vol. 162(1), pages 107-132, July.
    4. Jan Leeuw, 1984. "Differentiability of Kruskal's stress at a local minimum," Psychometrika, Springer;The Psychometric Society, vol. 49(1), pages 111-113, March.
    5. Jan Leeuw, 1988. "Convergence of the majorization method for multidimensional scaling," Journal of Classification, Springer;The Classification Society, vol. 5(2), pages 163-180, September.
    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. Peter Ochs, 2018. "Local Convergence of the Heavy-Ball Method and iPiano for Non-convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 177(1), pages 153-180, April.
    2. Patrick Groenen & Rudolf Mathar & Willem Heiser, 1995. "The majorization approach to multidimensional scaling for Minkowski distances," Journal of Classification, Springer;The Classification Society, vol. 12(1), pages 3-19, March.
    3. Julius Žilinskas, 2012. "Parallel branch and bound for multidimensional scaling with city-block distances," Journal of Global Optimization, Springer, vol. 54(2), pages 261-274, October.
    4. Ching-pei Lee & Stephen J. Wright, 2019. "Inexact Successive quadratic approximation for regularized optimization," Computational Optimization and Applications, Springer, vol. 72(3), pages 641-674, April.
    5. de Leeuw, Jan & Mair, Patrick, 2009. "Multidimensional Scaling Using Majorization: SMACOF in R," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 31(i03).
    6. Wei Liu & Li Yang & Bo Yu, 2020. "A Lifting-Penalty Method for Quadratic Programming with a Quadratic Matrix Inequality Constraint," Mathematics, MDPI, vol. 8(2), pages 1-11, January.
    7. Sixuan Bai & Minghua Li & Chengwu Lu & Daoli Zhu & Sien Deng, 2022. "The Equivalence of Three Types of Error Bounds for Weakly and Approximately Convex Functions," Journal of Optimization Theory and Applications, Springer, vol. 194(1), pages 220-245, July.
    8. Noga Ram & Shoham Sabach, 2024. "A Globally Convergent Inertial First-Order Optimization Method for Multidimensional Scaling," Journal of Optimization Theory and Applications, Springer, vol. 202(2), pages 949-974, August.
    9. Emilie Chouzenoux & Jean-Baptiste Fest, 2022. "SABRINA: A Stochastic Subspace Majorization-Minimization Algorithm," Journal of Optimization Theory and Applications, Springer, vol. 195(3), pages 919-952, December.
    10. Linghao Zhang & Bo Pang & Haitao Tang & Hongjun Wang & Chongshou Li & Zhipeng Luo, 2022. "Pairwise Constraints Multidimensional Scaling for Discriminative Feature Learning," Mathematics, MDPI, vol. 10(21), pages 1-16, November.
    11. Radu Ioan Boţ & Ernö Robert Csetnek & Szilárd Csaba László, 2016. "An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(1), pages 3-25, February.
    12. Michael J. Greenacre & Patrick J. F. Groenen, 2016. "Weighted Euclidean Biplots," Journal of Classification, Springer;The Classification Society, vol. 33(3), pages 442-459, October.
    13. Francisco Facchinei & Vyacheslav Kungurtsev & Lorenzo Lampariello & Gesualdo Scutari, 2021. "Ghost Penalties in Nonconvex Constrained Optimization: Diminishing Stepsizes and Iteration Complexity," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 595-627, May.
    14. Radu Ioan Boţ & Ernö Robert Csetnek, 2016. "An Inertial Tseng’s Type Proximal Algorithm for Nonsmooth and Nonconvex Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 171(2), pages 600-616, November.
    15. J. C. De Los Reyes & E. Loayza & P. Merino, 2017. "Second-order orthant-based methods with enriched Hessian information for sparse $$\ell _1$$ ℓ 1 -optimization," Computational Optimization and Applications, Springer, vol. 67(2), pages 225-258, June.
    16. Kagie, M. & van Wezel, M.C. & Groenen, P.J.F., 2009. "Map Based Visualization of Product Catalogs," ERIM Report Series Research in Management ERS-2009-010-MKT, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    17. Groenen, P.J.F. & Borg, I., 2013. "The Past, Present, and Future of Multidimensional Scaling," Econometric Institute Research Papers EI 2013-07, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    18. Groenen, P.J.F. & van de Velden, M., 2004. "Multidimensional scaling," Econometric Institute Research Papers EI 2004-15, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    19. Robert Schneider, 1992. "A uniform approach to multidimensional scaling," Journal of Classification, Springer;The Classification Society, vol. 9(2), pages 257-273, December.
    20. Lawrence Hubert & Phipps Arabie & Matthew Hesson-Mcinnis, 1992. "Multidimensional scaling in the city-block metric: A combinatorial approach," Journal of Classification, Springer;The Classification Society, vol. 9(2), pages 211-236, December.

    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:spr:jglopt:v:89:y:2024:i:3:d:10.1007_s10898-023-01361-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.