Numerically tractable radius of robust feasibility

Finding exact formulas for the radius of robust feasibility of uncertain linear programs (with a compact and convex uncertainty set) is significant for diverse applications. This radius provides a value for the maximal “size” of uncertainty set under which robust feasibility of the uncertain linear program can be guaranteed. By considering spectrahedral uncertainty sets is possible to obtain numerically tractable radius formulas for commonly used uncertainty sets of robust optimization, such as ellipsoids, balls, polytopes, and boxes. In these cases, the radius of robust feasibility can be found by solving a linearly constrained convex quadratic program or a minimax linear program. This paper considers the radius of robust feasibility following Chuong and Jeyakumar (2017), Jiawei Chen et al. (2020), and Goberna et al. (2015, 2016, 2022) and the references therein. A parametric linear program in the face of data uncertainty in both the objective and the constraints, denoted by PLU, can be captured by a family of uncertain linear programs, i.e., for each parameter α ∈ R+ , we have an uncertain linear program, denoted by (PLUα). The robust counterpart of (PLUα) is denoted by (PLRα), where the uncertain constraints are enforced for all possible parameter realizations within the corresponding uncertainty sets. The program PLUα is said to be robust feasible if the robust program PLRα is feasible, i.e., {x ∈ Rn : ajx − bj ≤ 0, ∀(aj, bj) ∈ Ujα , j=1,..., p} dif ∅. Throughout this paper, the uncertainty sets Ujα, j=1,..., p, are given by Ujα := (āj, b̄j ) + αZ, j=1,..., p, where (āj , b̄j ) ⊂ Rn+1, j=1,..., p, are fixed and Z ⊂ Rn+1 is a convex and compact set such that 0n ∈ intZ. We also assume that the nominal program (PLU0) is feasible, i.e., {x ∈ Rn : ājx − b̄j ≤ 0, j=1,..., p} dif ∅. The notion of the radius of robust feasibility for the parametric uncertain linear program PLU is defined as follows ρ := sup{α ∈ R+ : (PLRα) is feasible}. The radius α provides a value for the maximal “size” of the uncertainty set under which robust feasibility of our uncertain program is guaranteed. This article studies and proposes numerically tractable radius formulas for spectrahedral uncertainty sets, such as ellipsoids, balls, polytopes, and boxes, with applications for scalar and multiobjective linear integer problems, including robust goal programming with integer variables.