Advanced

Improved spectral relaxation methods for binary quadratic optimization problems

Olsson, Carl LU ; Eriksson, Anders P LU and Kahl, Fredrik LU (2008) In Computer Vision and Image Understanding 112(1). p.3-13
Abstract
in this paper, we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems-segmentation, clustering, subgraph matching to name a few-it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective function. On the other hand, the Computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations-better (lower) bounds... (More)
in this paper, we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems-segmentation, clustering, subgraph matching to name a few-it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective function. On the other hand, the Computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations-better (lower) bounds than traditional spectral methods and considerably faster execution times than SDP. The first method is based on spectral subgradients and can be applied to large scale SDPs with binary decision variables and the second one is based on the trust region problem. Both algorithms have been applied to several large scale vision problems with good performance. (C) 2008 Elsevier Inc. All rights reserved. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Discrete optimization, Binary restoration, Semidefinite programming, Trust region problem, Subgraph matching, Image partitioning, Quadratic binary optimization, Spectral relaxation
in
Computer Vision and Image Understanding
volume
112
issue
1
pages
3 - 13
publisher
Elsevier
external identifiers
  • wos:000260090900002
  • scopus:52949152378
ISSN
1077-3142
DOI
10.1016/j.cviu.2008.05.010
language
English
LU publication?
yes
id
8fe0d291-c925-4448-80ff-9586d078cc0e (old id 1284968)
date added to LUP
2009-02-06 16:12:38
date last changed
2017-10-08 03:33:31
@article{8fe0d291-c925-4448-80ff-9586d078cc0e,
  abstract     = {in this paper, we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems-segmentation, clustering, subgraph matching to name a few-it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective function. On the other hand, the Computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations-better (lower) bounds than traditional spectral methods and considerably faster execution times than SDP. The first method is based on spectral subgradients and can be applied to large scale SDPs with binary decision variables and the second one is based on the trust region problem. Both algorithms have been applied to several large scale vision problems with good performance. (C) 2008 Elsevier Inc. All rights reserved.},
  author       = {Olsson, Carl and Eriksson, Anders P and Kahl, Fredrik},
  issn         = {1077-3142},
  keyword      = {Discrete optimization,Binary restoration,Semidefinite programming,Trust region problem,Subgraph matching,Image partitioning,Quadratic binary optimization,Spectral relaxation},
  language     = {eng},
  number       = {1},
  pages        = {3--13},
  publisher    = {Elsevier},
  series       = {Computer Vision and Image Understanding},
  title        = {Improved spectral relaxation methods for binary quadratic optimization problems},
  url          = {http://dx.doi.org/10.1016/j.cviu.2008.05.010},
  volume       = {112},
  year         = {2008},
}