A Method for Uncertain Linear Optimization Problems Through Polytopic Approximation of the Uncertainty Set

Abstract

In this work, we propose a globally convergent iterative method to solve uncertain constrained linear optimization problems. Due to the nondeterministic nature of such a problem, we use the min-max approach to convert the given problem into a deterministic one. We show that the robust feasible sets of the problem corresponding to the uncertainty set and the convex hull of the uncertainty set are identical. This result helps to reduce the number of inequality constraints of the problem drastically; often, this result reduces the semi-infinite programming problem of the min-max robust counterpart into a problem with a finite number of constraints. Following this, we provide a necessary and sufficient condition for the boundedness of the robust feasible set of the problem. Moreover, we explicitly identify the robust feasible set of the problem for polytopic and ellipsoidal uncertainty sets. We present an algorithm to construct an inner polytope of the convex hull of a general uncertainty set under a certain assumption. This algorithm provides a point-wise inner polytopic approximation of the convex hull with arbitrarily small precision. We employ this inner polytopic approximation corresponding to the uncertainty set and the infeasible interior-point technique to derive an iterative approach to solve general uncertain constrained linear optimization problems. Global convergence for the proposed method is reported. Numerical experiments illustrate the practical behaviour of the proposed method on discrete, star-shaped, disc-shaped, and ellipsoidal uncertainty sets. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.