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

Ravi Raushan (), Debdas Ghosh (), Yong Zhao () and Zhou Wei ()
Additional contact information
Ravi Raushan: Indian Institute of Technology (BHU)
Debdas Ghosh: Indian Institute of Technology (BHU)
Yong Zhao: Chongqing Jiaotong University
Zhou Wei: Hebei University

Journal of Optimization Theory and Applications, 2025, vol. 205, issue 1, No 14, 42 pages

Abstract: 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.

Keywords: Uncertain constrained linear optimization; Min-max approach; Inner polytope; Infeasible interior-point technique; 90C05; 90C47; 90C51; 90C70 (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02626-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:205:y:2025:i:1:d:10.1007_s10957-025-02626-3

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02626-3

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().