Optimization Online


SDP-based Branch-and-Bound for Non-convex Quadratic Integer Optimization

C. Buchheim(christoph.buchheim***at***math.tu-dortmund.de)
M. Montenegro(mmontene***at***mathematik.tu-dortmund.de)
A. Wiegele(angelika.wiegele***at***aau.at)

Abstract: Semidefinite programming (SDP) relaxations have been intensively used for solving discrete quadratic optimization problems, in particular in the binary case. For the general non-convex integer case with box constraints, the branch-and-bound algorithm Q-MIST has been proposed [11], which is based on an extension of the well-known SDP-relaxation for max-cut. For solving the resulting SDPs, Q-MIST uses an off-the-shelf interior point algorithm. In this paper, we present a tailored coordinate ascent algorithm for solving the dual problems of these SDPs. Building on related ideas of Dong [15], it exploits the particular structure of the SDPs, most importantly a small rank of the constraint matrices. The latter allows both an exact line search and a fast incremental update of the inverse matrices involved, so that the entire algorithm can be implemented to run in quadratic time per iteration. Moreover, we describe how to extend this approach to a certain two-dimensional coordinate update. Finally, we explain how to include arbitrary linear constraints into this framework, and evaluate our algorithm experimentally.

Keywords: Quadratic integer programming, semidefinite programming, coordinate-wise optimization

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 06/23/2017
Entry Accepted: 06/23/2017
Entry Last Modified: 06/23/2017

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