A new algorithm for concave quadratic programming

Moslem Zamani ()
Additional contact information
Moslem Zamani: Ton Duc Thang University

Journal of Global Optimization, 2019, vol. 75, issue 3, No 4, 655-681

Abstract: 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.

Keywords: Non-convex quadratic programming; Duality; Semi-definite relaxation; Bound; Branch and cut method; Concave quadratic programming (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00787-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:75:y:2019:i:3:d:10.1007_s10898-019-00787-w

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00787-w

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().