Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Large-scale binary quadratic optimization using semidefinite relaxation and applications
Author: Wang, P.
Shen, C.
Van Den Hengel, A.
Torr, P.
Citation: IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017; 39(3):470-485
Publisher: IEEE
Issue Date: 2017
ISSN: 0162-8828
Statement of
Peng Wang, Chunhua Shen, Anton van den Hengel and Philip H.S. Torr
Abstract: In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.
Keywords: Binary quadratic optimization; semidefinite programming; Markov random fields
Rights: © 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See for more information
RMID: 0030068876
DOI: 10.1109/TPAMI.2016.2541146
Grant ID:
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.