IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v86y2023i3d10.1007_s10589-023-00505-z.html
   My bibliography  Save this article

Perturbation analysis of the euclidean distance matrix optimization problem and its numerical implications

Author

Listed:
  • Shaoyan Guo

    (Dalian University of Technology)

  • Hou-Duo Qi

    (The Hong Kong Polytechnic University)

  • Liwei Zhang

    (Dalian University of Technology)

Abstract

Euclidean distance matrices have lately received increasing attention in applications such as multidimensional scaling and molecular conformation from nuclear magnetic resonance data in computational chemistry. In this paper, we focus on the perturbation analysis of the Euclidean distance matrix optimization problem (EDMOP). Under Robinson’s constraint qualification, we establish a number of equivalent characterizations of strong regularity and strong stability at a locally optimal solution of EDMOP. Those results extend the corresponding characterizations in Semidefinite Programming and are tailored to the special structure in EDMOP. As an application, we demonstrate a numerical implication of the established results on an alternating direction method of multipliers (ADMM) to a stress minimization problem, which is an important instance of EDMOP. The implication is that the ADMM method converges to a strongly stable solution under reasonable assumptions.

Suggested Citation

  • Shaoyan Guo & Hou-Duo Qi & Liwei Zhang, 2023. "Perturbation analysis of the euclidean distance matrix optimization problem and its numerical implications," Computational Optimization and Applications, Springer, vol. 86(3), pages 1193-1227, December.
    • Handle: RePEc:spr:coopap:v:86:y:2023:i:3:d:10.1007_s10589-023-00505-z
    DOI: 10.1007/s10589-023-00505-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-023-00505-z
    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/s10589-023-00505-z?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. Norbert Gaffke & Rudolf Mathar, 1989. "A cyclic projection algorithm via duality," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 36(1), pages 29-54, December.
    2. Qian Zhang & Xinyuan Zhao & Chao Ding, 2021. "Matrix optimization based Euclidean embedding with outliers," Computational Optimization and Applications, Springer, vol. 79(2), pages 235-271, June.
    3. Stephen M. Robinson, 1980. "Strongly Regular Generalized Equations," Mathematics of Operations Research, INFORMS, vol. 5(1), pages 43-62, February.
    4. Defeng Sun & Jie Sun, 2002. "Semismooth Matrix-Valued Functions," Mathematics of Operations Research, INFORMS, vol. 27(1), pages 150-169, February.
    5. Defeng Sun, 2006. "The Strong Second-Order Sufficient Condition and Constraint Nondegeneracy in Nonlinear Semidefinite Programming and Their Implications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 761-776, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. William W. Hager & R. Tyrrell Rockafellar & Vladimir M. Veliov, 2023. "Preface to Asen L. Dontchev Memorial Special Issue," Computational Optimization and Applications, Springer, vol. 86(3), pages 795-800, December.

    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. Yong-Jin Liu & Li Wang, 2016. "Properties associated with the epigraph of the $$l_1$$ l 1 norm function of projection onto the nonnegative orthant," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(1), pages 205-221, August.
    2. Houduo Qi, 2009. "Local Duality of Nonlinear Semidefinite Programming," Mathematics of Operations Research, INFORMS, vol. 34(1), pages 124-141, February.
    3. Lingchen Kong & Levent Tunçel & Naihua Xiu, 2011. "Equivalent Conditions for Jacobian Nonsingularity in Linear Symmetric Cone Programming," Journal of Optimization Theory and Applications, Springer, vol. 148(2), pages 364-389, February.
    4. Defeng Sun, 2006. "The Strong Second-Order Sufficient Condition and Constraint Nondegeneracy in Nonlinear Semidefinite Programming and Their Implications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 761-776, November.
    5. Chengjin Li, 2014. "A New Approximation of the Matrix Rank Function and Its Application to Matrix Rank Minimization," Journal of Optimization Theory and Applications, Springer, vol. 163(2), pages 569-594, November.
    6. Shiwei Wang & Chao Ding, 2024. "Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming," Computational Optimization and Applications, Springer, vol. 87(1), pages 39-81, January.
    7. Qingna Li & Donghui Li & Houduo Qi, 2010. "Newton’s Method for Computing the Nearest Correlation Matrix with a Simple Upper Bound," Journal of Optimization Theory and Applications, Springer, vol. 147(3), pages 546-568, December.
    8. Jong-Shi Pang & Defeng Sun & Jie Sun, 2003. "Semismooth Homeomorphisms and Strong Stability of Semidefinite and Lorentz Complementarity Problems," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 39-63, February.
    9. Diethard Klatte & Bernd Kummer, 2013. "Aubin property and uniqueness of solutions in cone constrained optimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(3), pages 291-304, June.
    10. B. S. Mordukhovich & T. T. A. Nghia & R. T. Rockafellar, 2015. "Full Stability in Finite-Dimensional Optimization," Mathematics of Operations Research, INFORMS, vol. 40(1), pages 226-252, February.
    11. Shujun Bi & Le Han & Shaohua Pan, 2013. "Approximation of rank function and its application to the nearest low-rank correlation matrix," Journal of Global Optimization, Springer, vol. 57(4), pages 1113-1137, December.
    12. Jianzhong Zhang & Liwei Zhang & Xiantao Xiao, 2010. "A Perturbation approach for an inverse quadratic programming problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 72(3), pages 379-404, December.
    13. Liwei Zhang & Shaoyan Guo & Jia Wu & Shoulin Hao, 2013. "Nonsingularity in matrix conic optimization induced by spectral norm via a smoothing metric projector," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 78(3), pages 373-404, December.
    14. Defeng Sun & Jie Sun, 2008. "Löwner's Operator and Spectral Functions in Euclidean Jordan Algebras," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 421-445, May.
    15. M. Durea & R. Strugariu, 2011. "On parametric vector optimization via metric regularity of constraint systems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(3), pages 409-425, December.
    16. Liang Chen & Anping Liao, 2020. "On the Convergence Properties of a Second-Order Augmented Lagrangian Method for Nonlinear Programming Problems with Inequality Constraints," Journal of Optimization Theory and Applications, Springer, vol. 187(1), pages 248-265, October.
    17. Liwei Zhang & Shengzhe Gao & Saoyan Guo, 2019. "Statistical Inference of Second-Order Cone Programming," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(02), pages 1-17, April.
    18. Haoming Liu & Kangkang Deng & Haoyang Liu & Zaiwen Wen, 2023. "An Entropy-Regularized ADMM For Binary Quadratic Programming," Journal of Global Optimization, Springer, vol. 87(2), pages 447-479, November.
    19. Giorgio, 2019. "On Second-Order Optimality Conditions in Smooth Nonlinear Programming Problems," DEM Working Papers Series 171, University of Pavia, Department of Economics and Management.
    20. Francisco Aragón Artacho & Boris Mordukhovich, 2011. "Enhanced metric regularity and Lipschitzian properties of variational systems," Journal of Global Optimization, Springer, vol. 50(1), pages 145-167, May.

    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:coopap:v:86:y:2023:i:3:d:10.1007_s10589-023-00505-z. 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.