Identification of Supporting Hyperplanes in Scenario Optimisation Problems with Random Linear Constraints

Uncertain optimisation problems often require satisfaction of possibly infinite constraints, corresponding to each realisation of the uncertain phenomena influencing the problem setup. To find an approximate solution to such problems, randomised approaches such as the scenario approach can be employed where only a finite sample of these constraints are looked at. However, to have a strong probabilistic guarantee on the feasibility of the scenario solution for the original problem, we still need a large number of constraints. This leads to intractability of the scenario problems as well. In this paper we propose a method to remove redundant constraints in the scenario problem, prior to solving the problem itself. We consider a specific class of scenario problems with linear inequality constraints subject to one additive and one multiplicative uncertain parameter. The proposed method exploits the system structure to identify the supporting constraints and it is based on rigorous theoretical footings. The working of the method is also illustrated with the help of a numerical problem.