Optimization Online


Robust Sensitivity Analysis of the Optimal Value of Linear Programming

Guanglin Xu (guanglin-xu***at***uiowa.edu)
Samuel Burer (samuel-burer***at***uiowa.edu)

Abstract: We propose a framework for sensitivity analysis of linear programs (LPs) in minimiza- tion form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modeled in a compact, convex uncertainty set. This framework unifies and extends multiple approaches for LP sensitivity analysis 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, attainability, 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.

Keywords: Sensitivity analysis, minimax problem, nonconvex quadratic programming, semidefinite programming, copositive programming, uncertainty set.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Robust Optimization

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Department of Management Sciences, University of Iowa, Iowa City, IA, 52242-1994, USA, September 2015

Download: [PDF]

Entry Submitted: 09/15/2015
Entry Accepted: 09/15/2015
Entry Last Modified: 11/07/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society