Tight sampling and discarding bounds for scenario programs with an arbitrary number of removed samples

Conference item

The so-called scenario approach offers an efficient framework to address uncertain optimisation problems with uncertainty represented by means of scenarios. The sampling-and-discarding approach within the scenario approach literature allows the decision maker to trade feasibility to performance. We focus on a removal scheme composed by a cascade of scenario programs that removes at each stage a superset of the support set associated to the optimal solution of each of these programs. This particular removal scheme yields a scenario solution with tight guarantees on the probability of constraint violation; however, existing analysis restricts the number of discarded scenarios to be a multiple of the dimension of the optimisation problem. Motivated by this fact, this paper presents pathways to extend the theoretical analysis of this removal scheme. We first provide an extension for a restricted class of scenarios programs for which tight bounds can be obtained, and then we provide a conservative bound on the probability of constraint violation that is valid for any scenario program and an arbitrary number of removed scenarios, which is, however, not tight.

Authors: Romao, L; Margellos, K; Papachristodoulou, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Journal of Machine Learning Research
• Series: Proceedings of Machine Learning Research
• Series number: 144
• Publication date: 2021-05-29
• Acceptance date: 2021-03-15
• Event title: 3rd Annual Learning for Dynamics & Control Conference (L4DC)
• Event location: Virtual event
• Event website: https://l4dc.ethz.ch/
• Event start date: 2021-06-07
• Event end date: 2021-06-08
• ISSN: 2640-3498
• Language: English
• Keywords: FFR