Combinatorial optimization with information geometry: the Newton method

DOI10.3390/E16084260MaRDI QIDQ296294zbMATH OpenOpenAlexFDO

Authors Luigi Malagò, Giovanni Pistone

Publication date 15 June 2016

Published in Entropy (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3390/e16084260

zbMATH Keywords

combinatorial optimizationNewton methodRiemannian Hessianstatistical manifold

Mathematics Subject Classification ID

Local Riemannian geometry (53B20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Numerical optimization and variational techniques (65K10) Combinatorial optimization (90C27) Applications of mathematical programming (90C90)

Review text

Summary: We discuss the use of the Newton method in the computation of \(\max(p\mapsto\mathbb E_p[f])\), where \(p\) belongs to a statistical exponential family on a finite state space. In a number of papers, the authors have applied first order search methods based on information geometry. Second order methods have been widely used in optimization on manifolds, e.g., matrix manifolds, but appear to be new in statistical manifolds. These methods require the computation of the Riemannian Hessian in a statistical manifold. We use a non-parametric formulation of information geometry in view of further applications in the continuous state space cases, where the construction of a proper Riemannian structure is still an open problem.

Recommendations

• Optimization via Information Geometry
• Information Theoretic Approach to Geometric Programming
• Information-geometric optimization algorithms: a unifying picture via invariance principles
• Information Geometry and Interior-Point Algorithms
• Information geometry applications for optimizing numerical simulations
• Newton polytopes and relative entropy optimization
• The Newton sums method in combinatorial optimization
• scientific article; zbMATH DE number 3872359

Cites work

• Generalised exponential families and associated entropy functions
• On the Measurement of Polarization

Cited in

(10)

• Wasserstein Riemannian geometry of Gaussian densities
• Transport information Bregman divergences
• Newton polytopes and relative entropy optimization
• Second-order optimization over the multivariate Gaussian distribution
• Natural gradient flow in the mixture geometry of a discrete exponential family
• Black-box optimization using geodesics in statistical manifolds
• Optimization via Information Geometry
• Hessian metric via transport information geometry
• Differential analytic aspects of statistical models
• Lagrangian and Hamiltonian dynamics for probabilities on the statistical bundle

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Combinatorial optimization with information geometry: the Newton method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q296294)