Reference : Semidefinite Relaxations of Robust Binary Least Squares under Ellipsoidal Uncertainty Sets
Scientific journals : Article
Engineering, computing & technology : Computer science
Engineering, computing & technology : Electrical & electronics engineering
http://hdl.handle.net/10993/7590
Semidefinite Relaxations of Robust Binary Least Squares under Ellipsoidal Uncertainty Sets
English
Tsakonas, Efthymios [> >]
Jaldén, Joakim [> >]
Ottersten, Björn mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Nov-2011
IEEE Transactions on Signal Processing
IEEE
59
11
5169-5180
Yes
International
1053-587X
[en] The problem of finding the least squares solution s to a system of equations Hs = y is considered, when s is a vector of binary variables and the coefficient matrix H is unknown but of bounded uncertainty. Similar to previous approaches to robust binary least squares, we explore the potential of a min-max design with the aim to provide solutions that are less sensitive to the uncertainty in H. We concentrate on the important case of ellipsoidal uncertainty, i.e., the matrix H is assumed to be a deterministic unknown quantity which lies in a given uncertainty ellipsoid. The resulting problem is NP-hard, yet amenable to convex approximation techniques: Starting from a convenient reformulation of the original problem, we propose an approximation algorithm based on semidefinite relaxation that explicitly accounts for the ellipsoidal uncertainty in the coefficient matrix. Next, we show that it is possible to construct a tighter relaxation by suitably changing the description of the feasible region of the problem, and formulate an approximation algorithm that performs better in practice. Interestingly, both relaxations are derived as Lagrange bidual problems corresponding to the two equivalent problem reformulations. The strength of the proposed tightened relaxation is demonstrated by pertinent simulations.
Others
http://hdl.handle.net/10993/7590
10.1109/TSP.2011.2162507

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
Semidefinite Relaxations of Robust Binary Least Squares under Ellipsoidal Uncertainty Sets.pdfPublisher postprint2.39 MBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.