Incorporating Condition Measures into the Complexity Theory of Linear Programming
From MaRDI portal
Publication:4852578
DOI10.1137/0805026zbMath0838.90139OpenAlexW2002728800MaRDI QIDQ4852578
Publication date: 4 June 1996
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/8957
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Complexity and performance of numerical algorithms (65Y20) Error analysis and interval analysis (65G99)
Related Items (56)
An SOS1-based approach for solving MPECs with a natural gas market application ⋮ Learning from rounded-off data. ⋮ On the complexity of quadratic programming with two quadratic constraints ⋮ Some perturbation theory for linear programming ⋮ Extreme points of well-posed polytopes ⋮ CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization ⋮ Erratum to: ``CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization ⋮ Local linear convergence for alternating and averaged nonconvex projections ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information ⋮ On the complexity of solving feasible systems of linear inequalities specified with approximate data ⋮ On the complexity of linear programming under finite precision arithmetic ⋮ Linear programming, complexity theory and elementary functional analysis ⋮ Strong duality and minimal representations for cone optimization ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Some results on condition numbers in convex multiobjective optimization ⋮ Faster first-order primal-dual methods for linear programming using restarts and sharpness ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ A complementarity partition theorem for multifold conic systems ⋮ Probabilistic analysis of a differential equation for linear programming ⋮ Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization ⋮ Some preconditioners for systems of linear inequalities ⋮ Learning Paths from Signature Tensors ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ Computing the homology of real projective sets ⋮ The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms ⋮ A simple polynomial-time rescaling algorithm for solving linear programs ⋮ Grid methods in computational real algebraic (and semialgebraic) geometry ⋮ On strata of degenerate polyhedral cones. II: Relations between condition measures ⋮ Probabilistic analyses of condition numbers ⋮ Probabilistic analysis of condition numbers for linear programming ⋮ On the block-structured distance to non-surjectivity of sublinear mappings ⋮ Conic systems and sublinear mappings: equivalent approaches. ⋮ A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF ⋮ Solving linear programs with finite precision. II: Algorithms ⋮ New characterizations of Hoffman constants for systems of linear constraints ⋮ On the von Neumann and Frank--Wolfe Algorithms with Away Steps ⋮ Quadrature rules with neighborhood of spherical designs on the two-sphere ⋮ The condition number of a function relative to a set ⋮ A Data-Independent Distance to Infeasibility for Linear Conic Systems ⋮ Coderivative calculus and metric regularity for constraint and variational systems ⋮ A hybrid branch-and-bound approach for exact rational mixed-integer programming ⋮ Towards a deeper geometric, analytic and algorithmic understanding of margins ⋮ Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation ⋮ On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming ⋮ On strata of degenerate polyhedral cones. I: Condition and distance to strata ⋮ Quantitative Stability Analysis of Two-Stage Stochastic Linear Programs with Full Random Recourse ⋮ Condition measures and properties of the central trajectory of a linear program ⋮ Condition Number Theorems in Linear-Quadratic Optimization ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ The Condition Number of Riemannian Approximation Problems ⋮ Probabilistic analysis of the Grassmann condition number ⋮ A theory of complexity for continuous time systems ⋮ Real computations with fake numbers ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ Solving Conic Optimization Problems via Self-Dual Embedding and Facial Reduction: A Unified Approach
This page was built for publication: Incorporating Condition Measures into the Complexity Theory of Linear Programming
