Optimization Online


A new dual for quadratic programming and its applications

moslem Zamani (moslemzamani***at***ut.ac.ir)

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 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: Nonconvex quadratic programming , Duality, Semi-definite relaxation, Branch and bound method, Concave quadratic programming

Category 1: Global Optimization

Citation: Ton Duc Thang University, 19 Nguyen Huu Tho St, Tan Phong Ward, Dist. 7, Ho Chi Minh City, Vietnam, Agust 2018.

Download: [PDF]

Entry Submitted: 08/03/2018
Entry Accepted: 08/04/2018
Entry Last Modified: 01/28/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society