IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v75y2019i2d10.1007_s10898-019-00793-y.html
   My bibliography  Save this article

Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming

Author

Listed:
  • Rujun Jiang

    (Fudan University)

  • Duan Li

    (City University of Hong Kong)

Abstract

In this paper, we present new convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. While recent research has focused on strengthening convex relaxations of QCQP using the reformulation-linearization technique (RLT), the state-of-the-art methods lose their effectiveness when dealing with (multiple) nonconvex quadratic constraints in QCQP, except for direct lifting and linearization. In this research, we decompose and relax each nonconvex constraint to two second order cone (SOC) constraints and then linearize the products of the SOC constraints and linear constraints to construct some new effective valid constraints. Moreover, we extend the reach of the RLT-like techniques for almost all different types of constraint-pairs (including valid inequalities by linearizing the product of a pair of SOC constraints, and the Hadamard product or the Kronecker product of two respective valid linear matrix inequalities), examine dominance relationships among different valid inequalities, and explore almost all possibilities of gaining benefits from generating valid constraints. We also successfully demonstrate that applying RLT-like techniques to additional redundant linear constraints could reduce the relaxation gap significantly. We demonstrate the efficiency of our results with numerical experiments.

Suggested Citation

  • Rujun Jiang & Duan Li, 2019. "Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming," Journal of Global Optimization, Springer, vol. 75(2), pages 461-494, October.
  • Handle: RePEc:spr:jglopt:v:75:y:2019:i:2:d:10.1007_s10898-019-00793-y
    DOI: 10.1007/s10898-019-00793-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00793-y
    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-019-00793-y?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. X. Cui & X. Zheng & S. Zhu & X. Sun, 2013. "Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems," Journal of Global Optimization, Springer, vol. 56(4), pages 1409-1423, August.
    2. Jos F. Sturm & Shuzhong Zhang, 2003. "On Cones of Nonnegative Quadratic Functions," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 246-267, May.
    3. Lars Mathiesen, 1985. "Computational Experience in Solving Equilibrium Models by a Sequence of Linear Complementarity Problems," Operations Research, INFORMS, vol. 33(6), pages 1225-1250, December.
    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. Jianzhe Zhen & Ahmadreza Marandi & Danique de Moor & Dick den Hertog & Lieven Vandenberghe, 2022. "Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2410-2427, September.

    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. Shinji Yamada & Akiko Takeda, 2018. "Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization," Journal of Global Optimization, Springer, vol. 71(2), pages 313-339, June.
    2. W. Chung & J. Fuller & Y. Wu, 2003. "A New Demand-Supply Decomposition Method for a Class of Economic Equilibrium Models," Computational Economics, Springer;Society for Computational Economics, vol. 21(3), pages 231-243, June.
    3. Ben-Tal, A. & den Hertog, D., 2011. "Immunizing Conic Quadratic Optimization Problems Against Implementation Errors," Discussion Paper 2011-060, Tilburg University, Center for Economic Research.
    4. Oscar Bajo-Rubio & Antonio G. Gómez-Plana, 2015. "Alternative strategies to reduce public deficits: Taxes vs. spending," Journal of Applied Economics, Universidad del CEMA, vol. 18, pages 45-70, May.
    5. Dimitris Bertsimas & Ryan Cory-Wright, 2022. "A Scalable Algorithm for Sparse Portfolio Selection," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1489-1511, May.
    6. Massol, Olivier & Rifaat, Omer, 2018. "Phasing out the U.S. Federal Helium Reserve: Policy insights from a world helium model," Resource and Energy Economics, Elsevier, vol. 54(C), pages 186-211.
    7. Tapia-Ahumada, Karen & Octaviano, Claudia & Rausch, Sebastian & Pérez-Arriaga, Ignacio, 2015. "Modeling intermittent renewable electricity technologies in general equilibrium models," Economic Modelling, Elsevier, vol. 51(C), pages 242-262.
    8. Zhi-Long Dong & Fengmin Xu & Yu-Hong Dai, 2020. "Fast algorithms for sparse portfolio selection considering industries and investment styles," Journal of Global Optimization, Springer, vol. 78(4), pages 763-789, December.
    9. Roy Boyd & Kerry Krutilla, 1992. "Controlling acid deposition: A general equilibrium assessment," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 2(3), pages 307-322, May.
    10. 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.
    11. Kat, Bora & Paltsev, Sergey & Yuan, Mei, 2018. "Turkish energy sector development and the Paris Agreement goals: A CGE model assessment," Energy Policy, Elsevier, vol. 122(C), pages 84-96.
    12. 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.
    13. Becker, Jonathon M., 2023. "Tradable performance standards in a dynamic context," Resource and Energy Economics, Elsevier, vol. 73(C).
    14. Baas, Timo & Brücker, Herbert, 2012. "The macroeconomic consequences of migration diversion: Evidence for Germany and the UK," Structural Change and Economic Dynamics, Elsevier, vol. 23(2), pages 180-194.
    15. Immanuel Bomze & Werner Schachinger & Gabriele Uchida, 2012. "Think co(mpletely)positive ! Matrix properties, examples and a clustered bibliography on copositive optimization," Journal of Global Optimization, Springer, vol. 52(3), pages 423-445, March.
    16. Xi He & Edward J. Balistreri & Gyu Hyun Kim & Wendong Zhang, 2022. "A general equilibrium assessment of COVID-19's labor productivity impacts on china's regional economies," Journal of Productivity Analysis, Springer, vol. 58(2), pages 129-150, December.
    17. Xingmei Li & Yaxian Wang & Qingyou Yan & Xinchao Zhao, 2019. "Uncertain mean-variance model for dynamic project portfolio selection problem with divisibility," Fuzzy Optimization and Decision Making, Springer, vol. 18(1), pages 37-56, March.
    18. Cheng Lu & Zhibin Deng & Jing Zhou & Xiaoling Guo, 2019. "A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming," Journal of Global Optimization, Springer, vol. 73(2), pages 371-388, February.
    19. Jing Zhou & Shu-Cherng Fang & Wenxun Xing, 2017. "Conic approximation to quadratic optimization with linear complementarity constraints," Computational Optimization and Applications, Springer, vol. 66(1), pages 97-122, January.
    20. Rodríguez, Miguel & Robaina, Margarita & Teotónio, Carla, 2019. "Sectoral effects of a Green Tax Reform in Portugal," Renewable and Sustainable Energy Reviews, Elsevier, vol. 104(C), pages 408-418.

    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:75:y:2019:i:2:d:10.1007_s10898-019-00793-y. 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.