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

New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming

Author

Listed:
  • Mohand Bentobache

    (University of Laghouat)

  • Mohamed Telli

    (University of Laghouat)

  • Abdelkader Mokhtari

    (University of Laghouat)

Abstract

In this work, we propose a new approach called “Successive Linear Programming Algorithm (SLPA)” for finding an approximate global minimizer of general nonconvex quadratic programs. This algorithm can be initialized by any extreme point of the convex polyhedron of the feasible domain. Furthermore, we generalize the simplex algorithm for finding a local minimizer of concave quadratic programs written in standard form. We prove a new necessary and sufficient condition for local optimality, then we describe the Revised Primal Simplex Algorithm (RPSA). Finally, we propose a hybrid local-global algorithm called “SLPLEX”, which combines RPSA with SLPA for solving general concave quadratic programs. In order to compare the proposed algorithms to the branch-and-bound algorithm of CPLEX12.8 and the branch-and-cut algorithm of Quadproga, we develop an implementation with MATLAB and we present numerical experiments on 139 nonconvex quadratic test problems.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:82:y:2022:i:4:d:10.1007_s10898-021-01108-w
    DOI: 10.1007/s10898-021-01108-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-021-01108-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-021-01108-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. Rentsen Enkhbat & Yadam Bazarsad, 2010. "General Quadratic Programming and Its Applications in Response Surface Analysis," Springer Optimization and Its Applications, in: Altannar Chinchuluun & Panos M. Pardalos & Rentsen Enkhbat & Ider Tseveendorj (ed.), Optimization and Optimal Control, pages 121-137, Springer.
    2. Tao Pham Dinh & Nam Nguyen Canh & Hoai Le Thi, 2010. "An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs," Journal of Global Optimization, Springer, vol. 48(4), pages 595-632, December.
    3. Nikolaos Ploskas & Nikolaos Samaras, 2017. "Linear Programming Using MATLAB®," Springer Optimization and Its Applications, Springer, number 978-3-319-65919-0, September.
    4. Moslem Zamani, 2019. "A new algorithm for concave quadratic programming," Journal of Global Optimization, Springer, vol. 75(3), pages 655-681, November.
    5. Hoang Tuy, 2016. "Convex Analysis and Global Optimization," Springer Optimization and Its Applications, Springer, edition 2, number 978-3-319-31484-6, September.
    6. Nikolaos Ploskas & Nikolaos Samaras, 2017. "Correction to: Linear Programming Using MATLAB®," Springer Optimization and Its Applications, in: Linear Programming Using MATLAB®, pages E1-E3, Springer.
    7. Marguerite Frank & Philip Wolfe, 1956. "An algorithm for quadratic programming," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 95-110, March.
    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. Jae Hyoung Lee & Nithirat Sisarat & Liguo Jiao, 2021. "Multi-objective convex polynomial optimization and semidefinite programming relaxations," Journal of Global Optimization, Springer, vol. 80(1), pages 117-138, May.
    2. Marianna E.-Nagy & Anita Varga, 2023. "A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation," 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. 31(3), pages 691-711, September.
    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. Sophia Voulgaropoulou & Nikolaos Samaras & Nikolaos Ploskas, 2022. "Predicting the Execution Time of the Primal and Dual Simplex Algorithms Using Artificial Neural Networks," Mathematics, MDPI, vol. 10(7), pages 1-21, March.
    5. Guillaume Sagnol & Edouard Pauwels, 2019. "An unexpected connection between Bayes A-optimal designs and the group lasso," Statistical Papers, Springer, vol. 60(2), pages 565-584, April.
    6. Abdelfettah Laouzai & Rachid Ouafi, 2022. "A prediction model for atmospheric pollution reduction from urban traffic," Environment and Planning B, , vol. 49(2), pages 566-584, February.
    7. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    8. Francesco Rinaldi & Damiano Zeffiro, 2023. "Avoiding bad steps in Frank-Wolfe variants," Computational Optimization and Applications, Springer, vol. 84(1), pages 225-264, January.
    9. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    10. Tiến-Sơn Phạm, 2019. "Optimality Conditions for Minimizers at Infinity in Polynomial Programming," Management Science, INFORMS, vol. 44(4), pages 1381-1395, November.
    11. Filippozzi, Rafaela & Gonçalves, Douglas S. & Santos, Luiz-Rafael, 2023. "First-order methods for the convex hull membership problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 17-33.
    12. Ke, Ginger Y. & Zhang, Huiwen & Bookbinder, James H., 2020. "A dual toll policy for maintaining risk equity in hazardous materials transportation with fuzzy incident rate," International Journal of Production Economics, Elsevier, vol. 227(C).
    13. Friesz, Terry L. & Tourreilles, Francisco A. & Han, Anthony Fu-Wha, 1979. "Multi-Criteria Optimization Methods in Transport Project Evaluation: The Case of Rural Roads in Developing Countries," Transportation Research Forum Proceedings 1970s 318817, Transportation Research Forum.
    14. Damian Clarke & Daniel Paila~nir & Susan Athey & Guido Imbens, 2023. "Synthetic Difference In Differences Estimation," Papers 2301.11859, arXiv.org, revised Feb 2023.
    15. Fabiana R. Oliveira & Orizon P. Ferreira & Gilson N. Silva, 2019. "Newton’s method with feasible inexact projections for solving constrained generalized equations," Computational Optimization and Applications, Springer, vol. 72(1), pages 159-177, January.
    16. Ali Fattahi & Sriram Dasu & Reza Ahmadi, 2019. "Mass Customization and “Forecasting Options’ Penetration Rates Problem”," Operations Research, INFORMS, vol. 67(4), pages 1120-1134, July.
    17. Pokojovy, Michael & Jobe, J. Marcus, 2022. "A robust deterministic affine-equivariant algorithm for multivariate location and scatter," Computational Statistics & Data Analysis, Elsevier, vol. 172(C).
    18. Wei-jie Cong & Le Wang & Hui Sun, 2020. "Rank-two update algorithm versus Frank–Wolfe algorithm with away steps for the weighted Euclidean one-center problem," Computational Optimization and Applications, Springer, vol. 75(1), pages 237-262, January.
    19. 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.
    20. Felipe Serrano & Robert Schwarz & Ambros Gleixner, 2020. "On the relation between the extended supporting hyperplane algorithm and Kelley’s cutting plane algorithm," Journal of Global Optimization, Springer, vol. 78(1), pages 161-179, September.

    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:82:y:2022:i:4:d:10.1007_s10898-021-01108-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.