Interior-point methods for unconstrained geometric programming and scaling problems

Abstract

We provide a condition-based analysis of two interior-point methods for unconstrained geometric programs, a class of convex programs that arise naturally in applications including matrix scaling, matrix balancing, and entropy maximization. Our condition numbers are natural geometric quantities associated with the Newton polytope of the geometric program, and lead to diameter bounds on approximate minimizers. We also provide effective bounds on the condition numbers both in general and under combinatorial assumptions on the Newton polytope. In this way, we generalize the iteration complexity of recent interior-point methods for matrix scaling and matrix balancing. Recently, there has been much work on algorithms for certain optimization problems on Lie groups, known as capacity and scaling problems. For commutative groups, these problems reduce to unconstrained geometric programs, which serves as a particular source of motivation for our work.

33 pages, 2 figures

References in corpus (5)

• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Maximum Entropy Distributions: Bit Complexity and Stability
• Combinatorial and algorithmic aspects of hyperbolic polynomials
• Minimal length in an orbit closure as a semiclassical limit
• Primal-Dual Interior-Point Methods for Domain-Driven Formulations

Cited by in corpus (7)

• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• Toric invariant theory for maximum likelihood estimation in log-linear models
• Complexity of Sparse Polynomial Solving 2: Renormalization
• Polynomial time algorithms in invariant theory for torus actions
• On the Computability of Continuous Maximum Entropy Distributions: Adjoint Orbits of Lie Groups
• Barriers for recent methods in geodesic optimization
• Quantum algorithms for matrix scaling and matrix balancing