Set estimation via ellipsoidal approximations

In most estimation and design problems, there exists more than one solution that satisfies all constraints. In this paper, we address the problem of estimating the complete set of feasible solutions. Multiple feasible solutions are frequently encountered in signal restoration, image reconstruction, array processing, system identification and filter design. An estimate of the size of the feasibility set can be utilized to quantitatively evaluate inclusion and effectiveness of added constraints. Further, set estimation can be used to determine a null feasibility set. We compute ellipsoidal approximations to the set of feasible solutions using a new ellipsoid algorithm and the method of analytic centers. Both algorithms admit multiple convex constraint sets with ease. Also, the algorithms provide a solution which is guaranteed to be in the interior of the feasibility set