Robust solutions to least-squares problems with uncertain data. (English) Zbl 0891.65039

El Ghaoui, Laurent; Lebret, Hervé

SIAM J. Matrix Anal. Appl. 18, No. 4, 1035-1064 (1997).

Least-squares problems are studied where the coefficient matrices are unknown but bounded. The worse-case residual error is minimized. The exact value of the optimal worst-case residuals is computed using convex, second-order cone programming or semidefinite programming. A consequence is that the minimizing vector can be computed in polynomial time.

Reviewer: H.Hollatz (Magdeburg)

MSC:

65F20	Numerical solutions to overdetermined systems, pseudoinverses
65Y20	Complexity and performance of numerical algorithms

Keywords:

least-squares problems; uncertainty; robustness; semidefinite programming; ill-conditioned problem; regularization; robust interpolation