Title :
On mixed-integer random convex programs
Author :
Calafiore, Giuseppe C. ; Lyons, Daniel ; Fagiano, Lorenzo
Author_Institution :
Dipt. di Autom. e Inf., Politec. di Torino, Torino, Italy
Abstract :
We consider a class of mixed-integer optimization problems subject to N randomly drawn convex constraints. We provide explicit bounds on the tails of the probability that the optimal solution found under these N constraints will become infeasible for the next random constraint. First, we study constraint sets in general mixed-integer optimization problems, whose continuous counterpart is convex. We prove that the number of support constraints (i.e., constraints whose removal strictly improve the optimal objective) is bounded by a number depending geometrically on the dimension of the decision vector. Next, we use these results to show that the tails of the violation probability are bounded by a binomial distribution. Finally, we apply these bounds to an example of robust truss topology design. The findings in this paper are a first step towards an extension of previous results on continuous random convex programs to the case of problems with mixed-integer decision variables that naturally occur in many real-world applications.
Keywords :
convex programming; integer programming; probability; binomial distribution; convex constraints; general mixed integer optimization problems; mixed integer random convex programs; optimal solution; probability; Convex functions; Optimization; Random variables; Robustness; Silicon; Uncertainty; Vectors;
Conference_Titel :
Decision and Control (CDC), 2012 IEEE 51st Annual Conference on
Conference_Location :
Maui, HI
Print_ISBN :
978-1-4673-2065-8
Electronic_ISBN :
0743-1546
DOI :
10.1109/CDC.2012.6426905