Entropy Penalized Semidefinite Programming
arXiv:1802.04332 · doi:10.24963/ijcai.2019/157
Abstract
Low-rank methods for semidefinite programming (SDP) have gained a lot of interest recently, especially in machine learning applications. Their analysis often involves determinant-based or Schatten-norm penalties, which are hard to implement in practice due to high computational efforts. In this paper, we propose Entropy Penalized Semi-definite programming (EP-SDP) which provides a unified framework for a wide class of penalty functions used in practice to promote a low-rank solution. We show that EP-SDP problems admit efficient numerical algorithm having (almost) linear time complexity of the gradient iteration which makes it useful for many machine learning and optimization problems. We illustrate the practical efficiency of our approach on several combinatorial optimization and machine learning problems.
arXiv comment28th International Joint Conference on Artificial Intelligence, 2019
References in corpus (8)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Guaranteed Matrix Completion via Non-convex Factorization
- Matrix Completion has No Spurious Local Minimum
- Optimal Power Flow as a Polynomial Optimization Problem
- Semidefinite approximations of the matrix logarithm
- Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization
- A Low-Rank Coordinate-Descent Algorithm for Semidefinite Programming Relaxations of Optimal Power Flow
- Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs