Stochastic Ellipsoid Methods with Multiple Cuts

Robust control systems synthesis is generally recast as a class of robust feasibility problems which is to find a solution satisfying a set of parameter-dependent convex constraints for all possible parameter values. For this class of the problems, a stochastic ellipsoid method with multiple cuts each of which corresponds to each of the constraint is proposed, where a new update rule is presented for constructing a smaller ellipsoid which contains the intersection of a previous ellipsoid and half spaces determined by given multiple subgradients. Moreover, we show an explicit relation between the volume of the ellipsoid updated by the original method and that of the proposed method. A quantitative analysis of the volume of the updated ellipsoid is also provided, which leads to a further modification of the algorithm for achieving fast convergence.