  


Chanceconstrained optimization via randomization: feasibility and optimality
M.C. Campi(marco.campiing.unibs.it) Abstract: In this paper we study the link between a semiinfinite chanceconstrained optimization problem and its randomized version, i.e. the problem obtained by sampling a finite number of its constraints. Extending previous results on the feasibility of randomized convex programs, we establish here the feasibility of the solution obtained after the elimination of a portion of the sampled constraints. Constraints removal allows one to improve the cost function at the price of a decreased feasibility. The cost improvement can be inspected directly from the optimization result, while the theory here developed permits to keep control on the other side of the coin, the feasibility of the obtained solution. In this way, trading feasibility for performance through a samplinganddiscarding approach is put on solid mathematical grounds by the results of this paper. The feasibility result obtained in this paper applies to all chanceconstrained optimization problems with convex constraints, and has the distinctive feature that it holds true irrespective of the algorithm used for constraints removal. One can thus e.g. use a greedy algorithm  which is computationally lowdemanding  and the corresponding feasibility remains guaranteed. We further prove in this paper that if constraints removal is optimally done  i.e. one deletes those constraints leading to the largest possible cost improvement  a precise optimality link to the original semiinfinite chanceconstrained problem in addition holds. Keywords: Chanceconstrained optimization, Convex optimization, Randomized methods Category 1: Stochastic Programming Category 2: Infinite Dimensional Optimization (Semiinfinite Programming ) Category 3: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: preprint, Dept. of Electrical Engineering University of Brescia, via Branze 38, 25123 Brescia, Italy. Download: [PDF] Entry Submitted: 09/22/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  