On the road between robust optimization and the scenario approach for chance constrained optimization problems

K. Margellos, P. J. Goulart and J. Lygeros

IEEE Transactions on Automatic Control, vol. 59, no. 8, pp. 2258-2263, August 2014.
BibTeX  URL  Preprint 

@article{MGL:2014,
  author = {K. Margellos and P. J. Goulart and J. Lygeros},
  title = {On the road between robust optimization and the scenario approach for chance constrained optimization problems},
  journal = {IEEE Transactions on Automatic Control},
  year = {2014},
  volume = {59},
  number = {8},
  pages = {2258-2263},
  url = {http://dx.doi.org/10.1109/TAC.2014.2303232},
  doi = {10.1109/TAC.2014.2303232}
}

We propose a new method for solving chance constrained optimization problems that lies between robust optimization and scenario-based methods. Our method does not require prior knowledge of the underlying probability distribution as in robust optimization methods, nor is it based entirely on randomization as in the scenario approach. It instead involves solving a robust optimization problem with bounded uncertainty, where the uncertainty bounds are randomized and are computed using the scenario approach. To guarantee that the resulting robust problem is solvable we impose certain assumptions on the dependency of the constraint functions with respect to the uncertainty and show that tractability is ensured for a wide class of systems. Our results lead immediately to guidelines under which the proposed methodology or the scenario approach is preferable in terms of providing less conservative guarantees or reducing the computational cost.