Semidefinite Relaxations of Robust Binary Least Squares Under Ellipsoidal Uncertainty Sets
2011 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 59, no 11, 5169-5180 p.Article in journal (Refereed) Published
The problem of finding the least squares solution to a system of equations Hs = y is considered, when 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.
Place, publisher, year, edition, pages
IEEE , 2011. Vol. 59, no 11, 5169-5180 p.
Binary least squares, duality, robust optimization, semideﬁnite relaxation
IdentifiersURN: urn:nbn:se:kth:diva-46473DOI: 10.1109/TSP.2011.2162507ISI: 000297113500005ScopusID: 2-s2.0-80054057863OAI: oai:DiVA.org:kth-46473DiVA: diva2:453751
FunderEU, European Research Council, 228044
QC 201111032011-11-032011-11-032011-12-12Bibliographically approved