IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v50y2025i1d10.1007_s10878-025-01339-7.html
   My bibliography  Save this article

Bivalent quadratic optimization with sum-of-square of quadratic penalties

Author

Listed:
  • Tongli Zhang

    (Nanjing Institute of Technology
    Beihang University)

  • Yong Xia

    (Beihang University)

Abstract

The problem of maximizing the sum-of-square of quadratic functions with bivalent variables, denoted by (P), arises from bivalent quadratic optimization with K quadratic disjunctive penalties. Though NP-hard in general, (P) is polynomially solvable when the input matrices can concatenate to a fixed-rank matrix. We present a nonconvex quadratic semidefinite programming (SDP) relaxation, which provides a 0.4-approximate solution for (P). We show that the quadratic SDP relaxation can be approximately and globally solved to a precision $$\epsilon $$ via solving at most $$O((Kn^3/\epsilon )^{K/2})$$ linear SDP subproblems.

Suggested Citation

  • Tongli Zhang & Yong Xia, 2025. "Bivalent quadratic optimization with sum-of-square of quadratic penalties," Journal of Combinatorial Optimization, Springer, vol. 50(1), pages 1-17, August.
    • Handle: RePEc:spr:jcomop:v:50:y:2025:i:1:d:10.1007_s10878-025-01339-7
    DOI: 10.1007/s10878-025-01339-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01339-7
    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/s10878-025-01339-7?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    2. Jiawang Nie, 2009. "Sum of squares method for sensor network localization," Computational Optimization and Applications, Springer, vol. 43(2), pages 151-179, June.
    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. Byron Tasseff & Tameem Albash & Zachary Morrell & Marc Vuffray & Andrey Y. Lokhov & Sidhant Misra & Carleton Coffrin, 2024. "On the emerging potential of quantum annealing hardware for combinatorial optimization," Journal of Heuristics, Springer, vol. 30(5), pages 325-358, December.
    2. Bahram Alidaee & Haibo Wang, 2017. "A note on heuristic approach based on UBQP formulation of the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 102-110, January.
    3. Chao Ding & Hou-Duo Qi, 2017. "Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation," Computational Optimization and Applications, Springer, vol. 66(1), pages 187-218, January.
    4. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    5. Aritra Sarkar & Zaid Al-Ars & Koen Bertels, 2021. "QuASeR: Quantum Accelerated de novo DNA sequence reconstruction," PLOS ONE, Public Library of Science, vol. 16(4), pages 1-23, April.
    6. Fred Glover & Gary Kochenberger & Rick Hennig & Yu Du, 2022. "Quantum bridge analytics I: a tutorial on formulating and using QUBO models," Annals of Operations Research, Springer, vol. 314(1), pages 141-183, July.
    7. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    8. Juan S. Borrero & Colin Gillen & Oleg A. Prokopyev, 2017. "Fractional 0–1 programming: applications and algorithms," Journal of Global Optimization, Springer, vol. 69(1), pages 255-282, September.
    9. Kristijan Cafuta, 2019. "Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(2), pages 397-413, June.
    10. Kevin Wils & Boyang Chen, 2023. "A Symbolic Approach to Discrete Structural Optimization Using Quantum Annealing," Mathematics, MDPI, vol. 11(16), pages 1-29, August.
    11. Qihao Wu & Jiangxue Han & Yimo Yan & Yong-Hong Kuo & Zuo-Jun Max Shen, 2025. "Reinforcement learning for healthcare operations management: methodological framework, recent developments, and future research directions," Health Care Management Science, Springer, vol. 28(2), pages 298-333, June.
    12. Yitian Qian & Shaohua Pan & Shujun Bi, 2023. "A matrix nonconvex relaxation approach to unconstrained binary polynomial programs," Computational Optimization and Applications, Springer, vol. 84(3), pages 875-919, April.
    13. Wu, Zhiyou & Tian, Jing & Quan, Jing & Ugon, Julien, 2014. "Optimality conditions and optimization methods for quartic polynomial optimization," Applied Mathematics and Computation, Elsevier, vol. 232(C), pages 968-982.
    14. Petra Maria Bartmeyer & Christiano Lyra, 2025. "On the benefits of a new continuous reformulation for QUBO problems," Annals of Operations Research, Springer, vol. 351(1), pages 653-665, August.
    15. Ajagekar, Akshay & You, Fengqi, 2022. "Quantum computing and quantum artificial intelligence for renewable and sustainable energy: A emerging prospect towards climate neutrality," Renewable and Sustainable Energy Reviews, Elsevier, vol. 165(C).
    16. Fred Glover & Gary Kochenberger & Yu Du, 2019. "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models," 4OR, Springer, vol. 17(4), pages 335-371, December.
    17. Martin Vesely, 2023. "Finding the Optimal Currency Composition of Foreign Exchange Reserves with a Quantum Computer," Papers 2303.01909, arXiv.org.
    18. Fred Glover & Jin-Kao Hao, 2016. "f-Flip strategies for unconstrained binary quadratic programming," Annals of Operations Research, Springer, vol. 238(1), pages 651-657, March.
    19. João Gouveia & Ting Pong, 2012. "Comparing SOS and SDP relaxations of sensor network localization," Computational Optimization and Applications, Springer, vol. 52(3), pages 609-627, July.
    20. Juan Cota-Ruiz & Rafael Gonzalez-Landaeta & Jose David Diaz-Roman & Boris Mederos-Madrazo & Ernesto Sifuentes, 2019. "A weighted and distributed algorithm for multi-hop localization," International Journal of Distributed Sensor Networks, , vol. 15(7), pages 15501477198, June.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    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:spr:jcomop:v:50:y:2025:i:1:d:10.1007_s10878-025-01339-7. 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.