Reference : Robust binary least squares: Relaxations and algorithms
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Engineering, computing & technology : Computer science
Robust binary least squares: Relaxations and algorithms
Tsakonas, Efthymios [> >]
Jaldén, Joakim [> >]
Ottersten, Björn mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on
Proceedings IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP)
22-27 May 2011
Czech Republic
[en] Finding the least squares (LS) solution s to a system of linear equations Hs = y where H, y are given and s is a vector of binary variables, is a well known NP-hard problem. In this paper, we consider binary LS problems under the assumption that the coefficient matrix H is also unknown, and lies in a given uncertainty ellipsoid. We show that the corresponding worst-case robust optimization problem, although NP-hard, is still amenable to semidefinite relaxation (SDR)-based approximations. However, the relaxation step is not obvious, and requires a certain problem reformulation to be efficient. The proposed relaxation is motivated using Lagrangian duality and simulations suggest that it performs well, offering a robust alternative over the traditional SDR approaches for binary LS problems.

File(s) associated to this reference

Fulltext file(s):

Limited access
Robust binary least squares Relaxations and algorithms.pdfPublisher postprint192.54 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.