Publication:
Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis

Placeholder

School / College / Institute

Program

KU Authors

Co-Authors

Publication Date

Language

Embargo Status

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

Every quadratic programming problem with a mix of continuous and binary variables can be equivalently reformulated as a completely positive optimization problem, that is, 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. In particular, our results imply that polyhedral inner approximations are equivalent to a finite discretization of the feasible region of the original completely positive optimization problem. 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 as well as general mixed binary quadratic programs with a bounded feasible region.

Source

Publisher

Taylor & Francis Ltd

Subject

Computer science, Software engineering, Operations research, Management science, Mathematics, applied mathematics

Citation

Has Part

Source

Optimization Methods & Software

Book Series Title

Edition

DOI

10.1080/10556788.2016.1245732

item.page.datauri

Link

Rights

Copyrights Note

Endorsement

Review

Supplemented By

Referenced By

0

Views

0

Downloads

View PlumX Details