Robust sensitivity analysis of the optimal value of linear programming. (2nd November 2017)

• Record Type: Journal Article
• Authors: Xu, Guanglin; Burer, Samuel
• Is Part Of: Optimization methods and software. Volume 32:Number 6(2017)
• Page Start: 1187
• Page End: 1205
• Publication Date: 2017-11-02
• Subjects: sensitivity analysis -- minimax problem -- non-convex quadratic programming -- semidefinite programming -- copositive programming -- uncertainty set; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1256400
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We propose a framework for sensitivity analysis (SA) of linear programs (LPs) in minimization form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modelled in a compact, convex, and tractable uncertainty set. This framework unifies and extends multiple approaches for LP SA in the literature and has close ties to worst-case linear optimization and two-stage adaptive optimization. We define the minimum (best-case) and maximum (worst-case) LP optimal values, and, over the uncertainty set, and we discuss issues of finiteness, attainment, and computational complexity. While and are difficult to compute in general, we prove that they equal the optimal values of two separate, but related, copositive programs. We then develop tight, tractable conic relaxations to provide lower and upper bounds on and, respectively. We also develop techniques to assess the quality of the bounds, and we validate our approach computationally on several examples from—and inspired by—the literature. We find that the bounds on and are very strong in practice and, in particular, are at least as strong as known results for specific cases from the literature.