Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
Author
Abstract
Suggested Citation
DOI: 10.1007/s10898-021-01071-6
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- NESTEROV, Yu. & WOLKOWICZ, Henry & YE, Yinyu, 2000. "Semidefinite programming relaxations of nonconvex quadratic optimization," LIDAM Reprints CORE 1471, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- 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.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Yuzhou Qiu & E. Alper Yıldırım, 2024. "On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints," Journal of Global Optimization, Springer, vol. 90(2), pages 293-322, October.
- Godai Azuma & Mituhiro Fukuda & Sunyoung Kim & Makoto Yamashita, 2023. "Exact SDP relaxations for quadratic programs with bipartite graph structures," Journal of Global Optimization, Springer, vol. 86(3), pages 671-691, July.
- Godai Azuma & Sunyoung Kim & Makoto Yamashita, 2025. "Rank-one matrix completion via high-rank matrices in sum-of-squares relaxations," Journal of Global Optimization, Springer, vol. 92(2), pages 321-343, June.
- Cheng Lu & Jitao Ma & Zhibin Deng & Wenxun Xing, 2024. "A graphic structure based branch-and-bound algorithm for complex quadratic optimization and applications to magnitude least-square problem," Journal of Global Optimization, Springer, vol. 88(1), pages 115-137, January.
- Bo Zhang & YueLin Gao & Xia Liu & XiaoLi Huang, 2023. "Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems," Journal of Global Optimization, Springer, vol. 86(1), pages 61-92, May.
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.- 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.
- de Klerk, E., 2006. "The Complexity of Optimizing over a Simplex, Hypercube or Sphere : A Short Survey," Discussion Paper 2006-85, Tilburg University, Center for Economic Research.
- 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.
- 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.
- 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.
- 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.
- Etienne Klerk, 2008. "The complexity of optimizing over a simplex, hypercube or sphere: a short survey," 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. 16(2), pages 111-125, June.
- 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.
- 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.
- Yichuan Ding & Dongdong Ge & Henry Wolkowicz, 2011. "On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming," Mathematics of Operations Research, INFORMS, vol. 36(1), pages 88-104, February.
- Jos F. Sturm & Shuzhong Zhang, 2003. "On Cones of Nonnegative Quadratic Functions," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 246-267, May.
- 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.
- de Klerk, E., 2006. "The Complexity of Optimizing over a Simplex, Hypercube or Sphere : A Short Survey," Other publications TiSEM 88640b6d-5240-472d-8669-4, Tilburg University, School of Economics and Management.
- V. Jeyakumar & Guoyin Li, 2011. "Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems," Journal of Global Optimization, Springer, vol. 49(1), pages 1-14, January.
- 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.
- 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.
- Chuangchuang Sun, 2023. "A Customized ADMM Approach for Large-Scale Nonconvex Semidefinite Programming," Mathematics, MDPI, vol. 11(21), pages 1-27, October.
- 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.
- 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.
- Yichuan Ding & Henry Wolkowicz, 2009. "A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 1008-1022, November.
More about this item
Keywords
Quadratically constrained quadratic programs; Exact semidefinite relaxations; Forest graph; The rank of aggregated sparsity matrix;All these keywords.
Statistics
Access and download statisticsCorrections
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:82:y:2022:i:2:d:10.1007_s10898-021-01071-6. 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.