Robust sensitivity analysis of the optimal value of linear programming

Guanglin Xu, Samuel Burer

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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, P- and P+, over the uncertainty set, and we discuss issues of finiteness, attainment, and computational complexity. While P- and P_+ 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 P- and P+, 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 P- and P+ are very strong in practice and, in particular, are at least as strong as known results for specific cases from the literature.

Original languageEnglish (US)
Pages (from-to)1187-1205
Number of pages19
JournalOptimization Methods and Software
Volume32
Issue number6
DOIs
StatePublished - Nov 2 2017

Bibliographical note

Funding Information:
The first author acknowledges the financial support of the AFRL Mathematical Modeling and Optimization Institute, where he visited in Summer 2015. The second author acknowledges the financial support of Karthik Natarajan (Singapore University of Technology and Design) and Chung Piaw Teo (National University of Singapore), whom he visited in Fall 2014. The authors are in debt to two anonymous referees for many helpful suggestions that have improved the paper significantly and also wish to thank Qie He, Ankur Mani, and Kurt Anstreicher for helpful discussions regarding the continuity of the function in Section 2.3. This research has benefitted from their many insightful comments.

Publisher Copyright:
© 2016 Informa UK Limited, trading as Taylor & Francis Group.

Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

Keywords

  • copositive programming
  • minimax problem
  • non-convex quadratic programming
  • semidefinite programming
  • sensitivity analysis
  • uncertainty set

Fingerprint Dive into the research topics of 'Robust sensitivity analysis of the optimal value of linear programming'. Together they form a unique fingerprint.

Cite this