Completely positive and copositive program modelling for quadratic optimization problems. (1st February 2021)

• Record Type: Journal Article
• Authors: Nguyen, D. V.
• Is Part Of: Optimization. Volume 70:Number 2(2021)
• Page Start: 361
• Page End: 385
• Publication Date: 2021-02-01
• Subjects: Mixed-integer quadratic programming -- completely positive and copositive programs -- quadratic multidimensional knapsack problems; 90-00 -- 90C20 Quadratic programming -- 90C26Nonconvex programming -- global optimization; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1712392
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: In the present article, we discuss a general concept of lifting a non-convex quadratic optimization problem into a convex program with matrix variables, and then apply it to construct two kinds of equivalent lifted problems, which are completely positive programs (linear programs with completely positive matrix variables) for a class of quadratic optimization problem with linear inequality and mixed binary constraints. The duals of the resulting completely positive programs, which are copositive programs, are constructed. It is shown that, under some conditions, the dual problems are strictly feasible, such that strong duality holds and existing numerical methods for both primal and dual problems can be applied.