Wada, Takayuki (Kobe Univ.), Fujisaki, Yasumasa (Kobe Univ.)

Efficient Randomized Algorithms for Robust Feasibility Problems

Scheduled for presentation during the Regular Session "Convex Optimization I" (ThP12), Thursday, July 27, 2006, 16:10−16:35, Room 104b

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on May 19, 2024

Abstract

An efficient randomized algorithm is presented for 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. The proposed algorithm is a modified version of the stochastic ellipsoid method, where an ellipsoid which describes a candidate of the solution set can be updated many times for one random sample of the parameter, while at most one update is allowed in the original algorithm. This feature leads to reduction of the total number of random samples necessary for convergence, which is extensively demonstrated through numerical examples.