Linear programming, complexity theory and elementary functional analysis

DOI10.1007/BF01585941zbMath0855.90085MaRDI QIDQ1924066

James Renegar

Publication date: 12 January 1997

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

zbMATH Keywords

interior-point methodssemi-definite programmingcondition numbers

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items

Average-case complexity without the black swans, Local linear convergence for alternating and averaged nonconvex projections, An interior-point method for multifractional programs with convex constraints, OBSERVATIONS ON INFEASIBILITY DETECTORS FOR CLASSIFYING CONIC CONVEX PROGRAMS, On verified numerical computations in convex programming, On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems, Infinite-dimensional quadratic optimization: Interior-point methods and control applications, Metric regularity and Lipschitzian stability of parametric variational systems, 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 estimate of the distance to non-invertibility, On the complexity of linear programming under finite precision arithmetic, Calmness of the Optimal Value in Linear Programming, A primal-dual symmetric relaxation for homogeneous conic systems, Strong duality and minimal representations for cone optimization, Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization, Logarithmic-Barrier Decomposition Interior-Point Methods for Stochastic Linear Optimization in a Hilbert Space, Smoothed analysis of condition numbers and complexity implications for linear programming, Some results on condition numbers in convex multiobjective optimization, Stability in linear optimization and related topics. A personal tour, Sampling rates for \(\ell^1\)-synthesis, On condition number theorems in mathematical programming, Faster first-order primal-dual methods for linear programming using restarts and sharpness, A characterization of the distance to infeasibility under block-structured perturbations, A complementarity partition theorem for multifold conic systems, Round-off estimates for second-order conic feasibility problems, Conditioning for optimization problems under general perturbations, Generating and measuring instances of hard semidefinite programs, Unnamed Item, A condition-based algorithm for solving polyhedral feasibility problems, Unnamed Item, Some preconditioners for systems of linear inequalities, Robust smoothed analysis of a condition number for linear programming, Computing the homology of real projective sets, Level-set methods for convex optimization, On two-stage convex chance constrained problems, On the symmetry function of a convex set, Grid methods in computational real algebraic (and semialgebraic) geometry, 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, Enhanced metric regularity and Lipschitzian properties of variational systems, Probabilistic analysis of condition numbers for linear programming, Connections between the total least squares and the correction of an infeasible system of linear inequalities, On the block-structured distance to non-surjectivity of sublinear mappings, Conic systems and sublinear mappings: equivalent approaches., Improved complexity results on solving real-number linear feasibility problems, Solving linear programs with finite precision. II: Algorithms, Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems, New characterizations of Hoffman constants for systems of linear constraints, Stability of systems of linear equations and inequalities: distance to ill-posedness and metric regularity, On the von Neumann and Frank--Wolfe Algorithms with Away Steps, Robustness analysis via the running time of the interior point methods, Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment, On the Implementation and Usage of SDPT3 – A Matlab Software Package for Semidefinite-Quadratic-Linear Programming, Version 4.0, A condition number theorem in convex programming, The condition number of a function relative to a set, A Data-Independent Distance to Infeasibility for Linear Conic Systems, On the Lipschitz modulus of the argmin mapping in linear semi-infinite optimization, Unnamed Item, 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, Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation, 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, Conditioning of random conic systems under a general family of input distributions, Lipschitz modulus of the optimal value in linear programming, Condition measures and properties of the central trajectory of a linear program, The Condition Number of Riemannian Approximation Problems, Metric regularity of semi-infinite constraint systems, Solving second-order conic systems with variable precision, Probabilistic analysis of the Grassmann condition number, Real computations with fake numbers, The radius of metric regularity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• On condition numbers and the distance to the nearest ill-posed problem
• A polynomial-time algorithm, based on Newton's method, for linear programming
• An interior point algorithm for semi-infinite linear programming
• Unified complexity analysis for Newton LP methods
• Partially finite convex programming. I: Quasi relative interiors and duality theory
• Some perturbation theory for linear programming
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Semi-infinite programming and applications. An International Symposium, Austin, Texas, September 8-10, 1981
• An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
• On the complexity of solving feasible systems of linear inequalities specified with approximate data
• Condition numbers for polyhedra with real number data
• Complexity of Bezout's theorem. III: Condition number and packing
• A course on optimization and best approximation
• Some Remarks on the Foundations of Numerical Analysis
• On the efficiency of algorithms of analysis
• The Probability That a Numerical Analysis Problem is Difficult
• The fundamental theorem of algebra and complexity theory
• Path-Following Methods for Linear Programming
• Complexity of Bezout's Theorem I: Geometric Aspects
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Convex Analysis
• Linear Programming in Reflexive Spaces