Some perturbation theory for linear programming

DOI10.1007/BF01581690zbMath0818.90073OpenAlexW2065114871MaRDI QIDQ1334953

Publication date: 26 September 1994

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

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

zbMATH Keywords

real normed spaces data perturbations sensitivity of the optimal value solution characteristics

Mathematics Subject Classification ID

Linear programming (90C05) Programming in abstract spaces (90C48)

Related Items

An SOS1-based approach for solving MPECs with a natural gas market application, Average-case complexity without the black swans, Non-parametric tests of productive efficiency with errors-in-variables, A geometrical stability condition for compressed sensing, Extreme points of well-posed polytopes, Projection-based local and global Lipschitz moduli of the optimal value in linear programming, OBSERVATIONS ON INFEASIBILITY DETECTORS FOR CLASSIFYING CONIC CONVEX PROGRAMS, On verified numerical computations in convex programming, Status determination by interior-point methods for convex optimization problems in domain-driven form, On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems, On homogeneous and self-dual algorithms for LCP, Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems, Distance to ill-posedness in linear optimization via the Fenchel-Legendre conjugate, On the complexity of solving feasible systems of linear inequalities specified with approximate data, Sufficient conditions for total ill-posedness in linear semi-infinite optimization, On the complexity of linear programming under finite precision arithmetic, Linear programming, complexity theory and elementary functional analysis, Calmness of the Optimal Value in Linear Programming, Strong duality and minimal representations for cone optimization, Smoothed analysis of condition numbers and complexity implications for linear programming, Revisiting degeneracy, strict feasibility, stability, in linear programming, Stability in linear optimization and related topics. A personal tour, On condition number theorems in mathematical programming, Generating and measuring instances of hard semidefinite programs, Unnamed Item, Characterization of total ill-posedness in linear semi-infinite optimization, Robust smoothed analysis of a condition number for linear programming, A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints, Computing the homology of real projective sets, On two-stage convex chance constrained problems, Violation analysis on two-step method for interval linear programming, The radius of robust feasibility of uncertain mathematical programs: a survey and recent developments, Stability under perturbations of some condition numbers in optimization, Largest dual ellipsoids inscribed in dual cones, On strata of degenerate polyhedral cones. II: Relations between condition measures, Probabilistic analyses of condition numbers, Probabilistic analysis of condition numbers for linear programming, Connections between the total least squares and the correction of an infeasible system of linear inequalities, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Error bounds for the inverse feasible set mapping in linear semi-infinite optimization via a sensitivity dual approach, On the behavior of the homogeneous self-dual model for conic convex optimization, Ill-posedness with respect to the solvability in linear optimization, Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems, Stability of systems of linear equations and inequalities: distance to ill-posedness and metric regularity, Generalized derivatives of the optimal value of a linear program with respect to matrix coefficients, Quadrature rules with neighborhood of spherical designs on the two-sphere, A condition number theorem in convex programming, A Data-Independent Distance to Infeasibility for Linear Conic Systems, Unnamed Item, Extending the mixed algebraic-analysis Fourier–Motzkin elimination method for classifying linear semi-infinite programmes, A hybrid branch-and-bound approach for exact rational mixed-integer programming, A geometric analysis of Renegar's condition number, and its interplay with conic curvature, Towards a deeper geometric, analytic and algorithmic understanding of margins, Computation of condition numbers for linear programming problems using Peña’s method, On strata of degenerate polyhedral cones. I: Condition and distance to strata, POINTWISE RESIDUAL METHOD FOR SOLVING PRIMAL AND DUAL ILL-POSED LINEAR PROGRAMMING PROBLEMS WITH APPROXIMATE DATA, Iterative Refinement for Linear Programming, Lipschitz modulus of the optimal value in linear programming, Quantitative Stability Analysis of Two-Stage Stochastic Linear Programs with Full Random Recourse, Distance to ill-posedness for linear inequality systems under block perturbations: convex and infinite-dimensional cases, On optimal zero-preserving corrections for inconsistent linear systems, Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming, Condition measures and properties of the central trajectory of a linear program, Condition Number Theorems in Linear-Quadratic Optimization, On infeasibility of systems of convex analytic inequalities, Infeasibility analysis for systems of quadratic convex inequalities, Probabilistic analysis of the Grassmann condition number, Real computations with fake numbers

Cites Work