Department of
Applied
Mathematics

New bounds for quadratic programming

Moslem Zamani

University of Tehran

Abstract

In this talk, we present a new dual for quadratic programs, in which, the dual variables are affine functions. As 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 investigate the relationship between this bound and the well-known bounds in the literature. Thanks to the new bound, we propose a branch and cut algorithm for concave quadratic programs.

In the same line, we propose two types of bounds for quadratically constrained quadratic programs, quadratic and cubic bounds. We show that most semi-definite relaxations can be obtained as the dual of a quadratic bound.