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

A new algorithm for concave quadratic programming

Author

Listed:
  • Moslem Zamani

    (Ton Duc Thang University
    Ton Duc Thang University)

Abstract

The main outcomes of the paper are divided into two parts. First, we present a new dual for quadratic programs, in which, the dual variables are affine functions, and we prove strong duality. Since the new dual is intractable, we consider a modified version by restricting the feasible set. This leads to a new bound for quadratic programs. We demonstrate that the dual of the bound is a semi-definite relaxation of quadratic programs. In addition, we probe the relationship between this bound and the well-known bounds in the literature. In the second part, thanks to the new bound, we propose a branch and cut algorithm for concave quadratic programs. We establish that the algorithm enjoys global convergence. The effectiveness of the method is illustrated for numerical problem instances.

Suggested Citation

  • Moslem Zamani, 2019. "A new algorithm for concave quadratic programming," Journal of Global Optimization, Springer, vol. 75(3), pages 655-681, November.
    • Handle: RePEc:spr:jglopt:v:75:y:2019:i:3:d:10.1007_s10898-019-00787-w
    DOI: 10.1007/s10898-019-00787-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00787-w
    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-00787-w?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. T. D. Chuong & V. Jeyakumar, 2018. "Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers," Journal of Global Optimization, Springer, vol. 72(4), pages 655-678, December.
    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. Monique Laurent & Zhao Sun, 2014. "Handelman’s hierarchy for the maximum stable set problem," Journal of Global Optimization, Springer, vol. 60(3), pages 393-423, November.
    4. M. Dür & R. Horst, 1997. "Lagrange Duality and Partitioning Techniques in Nonconvex Global Optimization," Journal of Optimization Theory and Applications, Springer, vol. 95(2), pages 347-369, November.
    5. X. Zheng & X. Sun & D. Li & Y. Xu, 2012. "On zero duality gap in nonconvex quadratic programming problems," Journal of Global Optimization, Springer, vol. 52(2), pages 229-242, February.
    6. Jean B. Lasserre & Kim-Chuan Toh & Shouguang Yang, 2017. "A bounded degree SOS hierarchy for polynomial optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(1), pages 87-117, March.
    7. Julia Sponsel & Stefan Bundfuss & Mirjam Dür, 2012. "An improved algorithm to test copositivity," Journal of Global Optimization, Springer, vol. 52(3), pages 537-551, March.
    8. Hoang Tuy, 2016. "Convex Analysis and Global Optimization," Springer Optimization and Its Applications, Springer, edition 2, number 978-3-319-31484-6, June.
    9. 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).
    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. Arabmaldar, Aliasghar & Sahoo, Biresh K. & Ghiyasi, Mojtaba, 2023. "A generalized robust data envelopment analysis model based on directional distance function," European Journal of Operational Research, Elsevier, vol. 311(2), pages 617-632.
    2. Mohand Bentobache & Mohamed Telli & Abdelkader Mokhtari, 2022. "New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming," Journal of Global Optimization, Springer, vol. 82(4), pages 659-689, April.
    3. Moslem Zamani, 2023. "New bounds for nonconvex quadratically constrained quadratic programming," Journal of Global Optimization, Springer, vol. 85(3), pages 595-613, March.
    4. Hatami-Marbini, Adel & Arabmaldar, Aliasghar, 2021. "Robustness of Farrell cost efficiency measurement under data perturbations: Evidence from a US manufacturing application," European Journal of Operational Research, Elsevier, vol. 295(2), pages 604-620.

    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. 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.
    2. T. D. Chuong & V. Jeyakumar & G. Li, 2019. "A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs," Journal of Global Optimization, Springer, vol. 75(4), pages 885-919, December.
    3. 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.
    4. 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.
    5. 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.
    6. N. V. Thoai, 2000. "Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 331-354, November.
    7. Xiaolong Kuang & Bissan Ghaddar & Joe Naoum-Sawaya & Luis F. Zuluaga, 2019. "Alternative SDP and SOCP approximations for polynomial optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(2), pages 153-175, June.
    8. Campos, Juan S. & Misener, Ruth & Parpas, Panos, 2019. "A multilevel analysis of the Lasserre hierarchy," European Journal of Operational Research, Elsevier, vol. 277(1), pages 32-41.
    9. Immanuel M. Bomze & Vaithilingam Jeyakumar & Guoyin Li, 2018. "Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations," Journal of Global Optimization, Springer, vol. 71(3), pages 551-569, July.
    10. Mohammadreza Safi & Seyed Saeed Nabavi & Richard J. Caron, 2021. "A modified simplex partition algorithm to test copositivity," Journal of Global Optimization, Springer, vol. 81(3), pages 645-658, November.
    11. Welington Oliveira, 2019. "Proximal bundle methods for nonsmooth DC programming," Journal of Global Optimization, Springer, vol. 75(2), pages 523-563, October.
    12. 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.
    13. Peiping Shen & Kaimin Wang & Ting Lu, 2020. "Outer space branch and bound algorithm for solving linear multiplicative programming problems," Journal of Global Optimization, Springer, vol. 78(3), pages 453-482, November.
    14. W. Ackooij & S. Demassey & P. Javal & H. Morais & W. Oliveira & B. Swaminathan, 2021. "A bundle method for nonsmooth DC programming with application to chance-constrained problems," Computational Optimization and Applications, Springer, vol. 78(2), pages 451-490, March.
    15. Haibin Chen & Zheng-Hai Huang & Liqun Qi, 2017. "Copositivity Detection of Tensors: Theory and Algorithm," Journal of Optimization Theory and Applications, Springer, vol. 174(3), pages 746-761, September.
    16. Eric Gautier & Christiern Rose, 2022. "Fast, Robust Inference for Linear Instrumental Variables Models using Self-Normalized Moments," Papers 2211.02249, arXiv.org, revised Nov 2022.
    17. 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.
    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. Takahito Kuno, 2022. "A revision of the rectangular algorithm for a class of DC optimization problems," Journal of Global Optimization, Springer, vol. 83(2), pages 187-200, June.
    20. 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.

    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:3:d:10.1007_s10898-019-00787-w. 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.