Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Random Convex Programs

Random convex programs (RCPs) are convex optimization problems subject to a finite number N of random constraints. The optimal objective value J^* of an RCP is thus a random variable. We study the probability with which J^* is no longer optimal if a further random constraint is added to the problem (violation probability, V^*). It turns out that this probability rapidly concentrates near zero, as N increases.

We first develop a theory for RCPs, leading to explicit bounds on the upper tail probability of V^*. Then, we extend the setup to the case of RCPs with r a-posteriori violated constraints (RCPVs): a paradigm that permits to improve the optimal objective value while maintaining the violation probability under control. Explicit and non-asymptotic bounds are derived also in this case: the upper tail probability of V^* is upper bounded by a multiple of a Beta distribution, irrespective of the distribution on the random constraints. Further, the relation between RCPVs and chance-constrained problems (CCP) is discussed, showing that the optimal objective J^* of an RCPV with generic constraint removal rule provides, with arbitrarily high probability, an upper bound on the optimal objective of a corresponding CCP. Moreover, whenever an optimal constraint removal rule is used in the RCPVs, then appropriate choices of N,r exist such that J^* approximates arbitrarily well the objective of the CCP.

Type of Seminar:
Optimization and Applications Seminar
Prof. Giuseppe Calafiore
Dipartimento di Automatica e Informatica, Politecnico di Torino, Italy
Apr 04, 2011   16:30

HG G 19.1, Rämistrasse 101
Contact Person:

John Lygeros
File Download:

Request a copy of this publication.
Biographical Sketch:
Giuseppe Calafiore received the ``Laurea" degree in Electrical Engineering from Politecnico di Torino in 1993, and the Ph.D. in Information and System Theory from Politecnico di Torino in 1997. He currently serves as Associate Professor at the ``Dipartimento di Automatica e Informatica,'' Politecnico di Torino, Italy. Dr. Calafiore held visiting positions at Information Systems Laboratory, Stanford University, in 1995, at Ecole Nationale Supérieure de Techniques Avenceés (ENSTA), Paris, in 1998, at the University of California at Berkeley, in 1999, 2003 and 2007. In 2010 he was a visiting Senior Fellow at the Institute of Pure and Applied Mathematics, UCLA. Dr. Calafiore is Associate Editor for the IEEE Transactions on Automation Science and Engineering, for the IEEE Transactions on Systems, Man, and Cybernetics, and for the Journal Européen des Systèmes Automatisés. His research interests are in the field of analysis and control of uncertain systems, convex optimization, probabilistic algorithms and risk management. He is the recipient of the 2008 IEEE Axelby Award. He is coauthor of 6 books and over 120 publications on international journals and conference proceedings.