Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

DOI10.1007/S101070100215MaRDI QIDQ5935708zbMATH OpenFDO

Authors E. Alper Yildirim, Michael J. Todd

Publication date 26 June 2001

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S101070100215

zbMATH Keywords

cost parametersinterior-point methodlinear programmingperturbationssemidefinite programming

Mathematics Subject Classification ID

Linear programming (90C05) Semidefinite programming (90C22) Sensitivity, stability, parametric optimization (90C31) Interior-point methods (90C51)

Review text

The authors analyze perturbations of the right-hand side and the cost parameters in linear programming (LP) and semidefinite programming (SDP) problems. They obtain tight bounds on the perturbations so that the result of a single interior-point iteration would yield feasible solutions to the perturbed problem and its dual. For the (LP) case where the solution is unique and nondegenerate, they also show that the bounds arising from the interior-point method asymptotically coincide with the bounds that keep the current basis optimal (after symmetrization with respect to the origin). In the (SDP) case the bounds are obtained by using the general family of R. D. C. Monteiro and Y. Zhang search directions as well as by using three specific search directions.

Recommendations

• An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming
• An interior-point approach to sensitivity analysis in degenerate linear programs
• Approaches to sensitivity analysis in linear programming
• Matrix Sensitivity Analysis from an Interior Solution of a Linear Program
• Analyse de sensibilité pour les problèmes linéaires en variables 0-1
• Sensitivity analysis in linear semi-infinite programming via partitions
• Sensitivity analysis in convex programming
• ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING
• Sensitivity analysis for non-linear programs with linear constraints
• Local sensitivity analysis for linear programs based on semismooth equations

Cited in

(17)

• Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension
• A sensitivity result for semidefinite programs.
• An \(\varepsilon\)-sensitivity analysis in the primal-dual interior point method
• Perturbation analysis of singular semidefinite programs and its applications to control problems
• Two optimal value functions in parametric conic linear programming
• An -sensitivity analysis for semidefinite programming
• Phase recovery, MaxCut and complex semidefinite programming
• Sensitivity analysis in bilevel linear programming
• An interior-point approach to sensitivity analysis in degenerate linear programs
• Maximum divert for planetary landing using convex optimization
• scientific article; zbMATH DE number 764459 (Why is no real title available?)
• Matrix Sensitivity Analysis from an Interior Solution of a Linear Program
• Some observations on the perturbation of the vectors b and c in a linear programming problem.
• Parametric analysis of semidefinite optimization
• An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming
• On sensitivity of central solutions in semidefinite programming
• Post-optimality analysis of the optimal solution of a degenerate linear program using a pivoting algorithm

This page was built for publication: Sensitivity analysis in linear programming and semidefinite programming using interior-point methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5935708)