Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/106148
Citations | ||
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 1939-3539 |
Statement of Responsibility: | 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 http://www.ieee.org/publications_standards/publications/rights/index.html for more information |
DOI: | 10.1109/TPAMI.2016.2541146 |
Grant ID: | http://purl.org/au-research/grants/arc/FT120100969 |
Published version: | http://dx.doi.org/10.1109/tpami.2016.2541146 |
Appears in Collections: | Aurora harvest 8 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.