Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry

Abstract

Convex optimization is a well-established research area with applications in almost all fields. Over the decades, multiple approaches have been proposed to solve convex programs. The development of interior-point methods allowed solving a more general set of convex programs known as semi-definite programs and second-order cone programs. However, it has been established that these methods are excessively slow for high dimensions, i.e., they suffer from the curse of dimensionality. On the other hand, optimization algorithms on manifold have shown great ability in finding solutions to nonconvex problems in reasonable time. This paper is interested in solving a subset of convex optimization using a different approach. The main idea behind Riemannian optimization is to view the constrained optimization problem as an unconstrained one over a restricted search space. The paper introduces three manifolds to solve convex programs under particular box constraints. The manifolds, called the doubly stochastic, symmetric and the definite multinomial manifolds, generalize the simplex also known as the multinomial manifold. The proposed manifolds and algorithms are well-adapted to solving convex programs in which the variable of interest is a multidimensional probability distribution function. Theoretical analysis and simulation results testify the efficiency of the proposed method over state of the art methods. In particular, they reveal that the proposed framework outperforms conventional generic and specialized solvers, especially in high dimensions.

References in corpus (5)

• Manopt, a Matlab toolbox for optimization on manifolds
• Geometric Optimization Methods for Adaptive Filtering
• Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry
• Clustering by Low-Rank Doubly Stochastic Matrix Decomposition
• Analysis of Exact and Approximated Epidemic Models over Complex Networks

Cited by in corpus (11)

• Geoopt: Riemannian Optimization in PyTorch
• Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry
• Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope
• Riemannian Newton-CG Methods for Constructing a Positive Doubly Stochastic Matrix From Spectral Data
• Stochastic $p$th root approximation of a stochastic matrix: A Riemannian optimization approach
• On a numerical construction of doubly stochastic matrices with prescribed eigenvalues
• Manifold optimization for non-linear optimal transport problems
• Coupling Matrix Manifolds and Their Applications in Optimal Transport
• Saddle Hierarchy in Dense Associative Memory
• Multiple Intelligent Reflecting Surface aided Multi-user Weighted Sum-Rate Maximization using Manifold Optimization
• A Novel Riemannian Optimization Approach to the Radial Distribution Network Load Flow Problem