Optimization Online


Inner Approximations of Completely Positive Reformulations of Mixed Binary Quadratic Programs: A Unified Analysis

E. Alper Yildirim (alperyildirim***at***ku.edu.tr)

Abstract: Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, i.e., a linear optimization problem over the convex but computationally intractable cone of completely positive matrices. In this paper, we focus on general inner approximations of the cone of completely positive matrices on instances of completely positive optimization problems that arise from the reformulation of mixed binary quadratic programming problems. We provide a characterization of the feasibility of such an inner approximation as well as the optimal value of a feasible inner approximation. For polyhedral inner approximations, our characterization implies that computing an optimal solution of the corresponding inner approximation reduces to an optimization problem over a finite set. Our characterization yields, as a byproduct, an upper bound on the gap between the optimal value of an inner approximation and that of the original instance. We discuss the implications of this error bound for standard and box-constrained quadratic programs.

Keywords: Completely positive cone, mixed binary quadratic optimization problems, inner approximations, polyhedral approximations

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

Citation: Optimization Methods and Software, to appear.

Download: [PDF]

Entry Submitted: 08/25/2015
Entry Accepted: 08/25/2015
Entry Last Modified: 10/06/2016

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