IDEAS home Printed from https://ideas.repec.org/p/aeg/wpaper/2009-13.html
   My bibliography  Save this paper

An unconstrained approach for solving low rank SDP relaxations of {-1,1} quadratic problems

Author

Listed:
  • Luigi Grippo

    (Sapienza Universita' di Roma - Dipartimento di Informatica e Sistemistica, Roma, Italy.)

  • Laura Palagi

    (Sapienza Universita' di Roma - Dipartimento di Informatica e Sistemistica, Roma, Italy.)

  • Mauro Piacentini

    (Sapienza Universita' di Roma - Dipartimento di Informatica e Sistemistica, Roma, Italy.)

  • Veronica Piccialli

    (Universita' di Tor Vergata - Dipartimento di Ingegneria dell'Impresa - via del Politecnico, 1-00133 Roma, Italy)

Abstract

We consider low-rank semidefinite programming (LRSDP) relaxations of ±1 quadratic problems that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an effcient and globally convergent algorithm for finding critical points of the LRSDP problem. Finally, we test our code on an extended set of instances of the Max-Cut problem and we report comparisons with other existing codes.

Suggested Citation

  • Luigi Grippo & Laura Palagi & Mauro Piacentini & Veronica Piccialli, 2009. "An unconstrained approach for solving low rank SDP relaxations of {-1,1} quadratic problems," DIS Technical Reports 2009-13, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    • Handle: RePEc:aeg:wpaper:2009-13
    as

    Download full text from publisher

    File URL: http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/wpaper/2009-13.pdf
    File Function: First version, 2009
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Gábor Pataki, 1998. "On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues," Mathematics of Operations Research, INFORMS, vol. 23(2), pages 339-358, May.
    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. Ting Pong & Henry Wolkowicz, 2014. "The generalized trust region subproblem," Computational Optimization and Applications, Springer, vol. 58(2), pages 273-322, June.
    2. Godai Azuma & Mituhiro Fukuda & Sunyoung Kim & Makoto Yamashita, 2022. "Exact SDP relaxations of quadratically constrained quadratic programs with forest structures," Journal of Global Optimization, Springer, vol. 82(2), pages 243-262, February.
    3. Xinzhen Zhang & Chen Ling & Liqun Qi, 2011. "Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints," Journal of Global Optimization, Springer, vol. 49(2), pages 293-311, February.
    4. Bomze, Immanuel M. & Gabl, Markus, 2023. "Optimization under uncertainty and risk: Quadratic and copositive approaches," European Journal of Operational Research, Elsevier, vol. 310(2), pages 449-476.
    5. Yanjun Wang & Ruizhi Shi & Jianming Shi, 2015. "Duality and robust duality for special nonconvex homogeneous quadratic programming under certainty and uncertainty environment," Journal of Global Optimization, Springer, vol. 62(4), pages 643-659, August.
    6. Stefan Sremac & Fei Wang & Henry Wolkowicz & Lucas Pettersson, 2019. "Noisy Euclidean distance matrix completion with a single missing node," Journal of Global Optimization, Springer, vol. 75(4), pages 973-1002, December.
    7. Madeleine Udell & Stephen Boyd, 2016. "Bounding duality gap for separable problems with linear constraints," Computational Optimization and Applications, Springer, vol. 64(2), pages 355-378, June.
    8. Anthony Man-Cho So & Yinyu Ye & Jiawei Zhang, 2008. "A Unified Theorem on SDP Rank Reduction," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 910-920, November.
    9. Immanuel Bomze & Markus Gabl, 2021. "Interplay of non-convex quadratically constrained problems with adjustable robust optimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(1), pages 115-151, February.
    10. Samuel Burer & Moshe Dror, 2012. "Newsvendor games: convex optimization of centralized inventory operations," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(3), pages 707-728, October.
    11. Jos F. Sturm & Shuzhong Zhang, 2003. "On Cones of Nonnegative Quadratic Functions," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 246-267, May.
    12. Im, Haesol & Wolkowicz, Henry, 2023. "Revisiting degeneracy, strict feasibility, stability, in linear programming," European Journal of Operational Research, Elsevier, vol. 310(2), pages 495-510.
    13. Boris Defourny & Ilya O. Ryzhov & Warren B. Powell, 2015. "Optimal Information Blending with Measurements in the L 2 Sphere," Mathematics of Operations Research, INFORMS, vol. 40(4), pages 1060-1088, October.
    14. Yongwei Huang & Shuzhong Zhang, 2007. "Complex Matrix Decomposition and Quadratic Programming," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 758-768, August.
    15. Wenbao Ai & Yongwei Huang & Shuzhong Zhang, 2008. "On the Low Rank Solutions for Linear Matrix Inequalities," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 965-975, November.
    16. Zohrizadeh, Fariba & Josz, Cedric & Jin, Ming & Madani, Ramtin & Lavaei, Javad & Sojoudi, Somayeh, 2020. "A survey on conic relaxations of optimal power flow problem," European Journal of Operational Research, Elsevier, vol. 287(2), pages 391-409.
    17. Chuangchuang Sun, 2023. "A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming," Mathematics, MDPI, vol. 11(21), pages 1-27, October.
    18. Ming Huang & Yue Lu & Li Ping Pang & Zun Quan Xia, 2017. "A space decomposition scheme for maximum eigenvalue functions and its applications," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 85(3), pages 453-490, June.
    19. A. Beck, 2009. "Convexity Properties Associated with Nonconvex Quadratic Matrix Functions and Applications to Quadratic Programming," Journal of Optimization Theory and Applications, Springer, vol. 142(1), pages 1-29, July.
    20. Donald Goldfarb & Cun Mu & John Wright & Chaoxu Zhou, 2017. "Using negative curvature in solving nonlinear programs," Computational Optimization and Applications, Springer, vol. 68(3), pages 479-502, 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:aeg:wpaper:2009-13. 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: Antonietta Angelica Zucconi (email available below). General contact details of provider: https://edirc.repec.org/data/dirosit.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.