Robust Solutions to l1, l2, and l-infinity Uncertain Linear Approximation Problems Using Convex Optimization

H. Hindi and S. Boyd

Proceedings of the American Control Conference, 6:3487-3491, June 1998.

We present minimax and stochastic formulations of some linear approximation problems with uncertain data in R^n equipped with the Euclidean (l2), Absolute-sum (l1) or Chebyshev (l-infinity) norms. We then show that these problems can be solved using convex optimization. Our results parallel and extend the work of El-Ghaoui and Lebret on robust least squares, and the work of Ben-Tal and Nemirovski on robust conic convex optimization problems. The theory presented here is useful for desensitizing solutions to ill-conditioned problems, or for computing solutions that guarantee a certain performance in the presence of uncertainty in the data.