Self-concordant barriers for convex approximations of structured convex sets

DOI10.1007/s10208-010-9069-xzbMath1225.90100OpenAlexW2167124007WikidataQ57392903 ScholiaQ57392903MaRDI QIDQ707744

Arkadi Nemirovski, Tunçel, Levent

Publication date: 8 October 2010

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-010-9069-x

zbMATH Keywords

convex optimizationsemidefinite programminginterior-point methodsself-concordant barrierspacking-covering problems

Mathematics Subject Classification ID

Semidefinite programming (90C22) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Numerical methods based on nonlinear programming (49M37) Interior-point methods (90C51) Convex functions and convex programs in convex geometry (52A41)

Related Items

A Self-Concordant Interior Point Approach for Optimal Control with State Constraints, Generalized self-concordant analysis of Frank-Wolfe algorithms, On max-\(k\)-sums, On self-concordant barriers for generalized power cones

Cites Work

• Unnamed Item
• Smooth minimization of non-smooth functions
• Dual extrapolation and its applications to solving variational inequalities and related problems
• Solving combinatorial optimization problems using Karmarkar's algorithm
• Potential function methods for approximately solving linear programming problems: theory and practice.
• ``Cone-free primal-dual path-following and potential-reduction polynomial time interior-point methods
• Fast approximation algorithms for multicommodity flow problems
• A cutting plane algorithm for convex programming that uses analytic centers
• Hyperbolic programs, and their derivative relaxations
• Unconstrained Convex Minimization in Relative Scale
• The maximum concurrent flow problem
• Towards a Practical Volumetric Cutting Plane Method for Convex Programming
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Coordination Complexity of Parallel Price-Directive Decomposition
• Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems
• Rounding of convex sets and efficient gradient methods for linear programming problems
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations