Rounding of convex sets and efficient gradient methods for linear programming problems

DOI10.1080/10556780701550059zbMath1192.90119OpenAlexW2111208481MaRDI QIDQ5459820

No author found.

Publication date: 29 April 2008

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556780701550059

zbMATH Keywords

convex optimizationnonlinear optimizationgradient methodscomplexity boundsoptimal methodsrelative accuracyfully polynomial approximation schemes

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Linear programming (90C05)

Related Items (5)

OSGA: a fast subgradient algorithm with optimal complexity ⋮ Gradient methods for minimizing composite functions ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Barrier subgradient method ⋮ Self-concordant barriers for convex approximations of structured convex sets

Cites Work

• Smooth minimization of non-smooth functions
• Minimum-volume enclosing ellipsoids and core sets
• Introductory lectures on convex optimization. A basic course.
• Potential function methods for approximately solving linear programming problems: theory and practice.
• Lectures on Modern Convex Optimization
• Ellipsoidal Approximations of Convex Sets Based on the Volumetric Barrier
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Rounding of Polytopes in the Real Number Model of Computation
• Excessive Gap Technique in Nonsmooth Convex Minimization

This page was built for publication: Rounding of convex sets and efficient gradient methods for linear programming problems