Multiplicative updates for symmetric-cone factorizations

• 成果类型: Article
• 署名作者: Soh, Yong Sheng; Varvitsiotis, Antonios
• 署名单位: National University of Singapore; Agency for Science Technology & Research (A*STAR); Agency for Science Technology & Research (A*STAR); A*STAR - Institute of High Performance Computing (IHPC); Singapore University of Technology & Design
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02015-6
• 发表日期: 2024
• 页码: 427-456
• 关键词: nonnegative matrix factorization; algorithms

摘要

Given a matrix X is an element of R-mxn (+) with non-negative entries, the cone factorization problem concerns computing {a(1),..., a(m)}subset of Kappa belonging to a convex cone K subset of R-k, and {b(1),..., b(n)}subset of K-* belonging to its dual so that X-i j = < a(i), b(j) > for all i is an element of [m], j is an element of [n]. Cone factorizations are fundamental to mathematical optimization as they allow us to express convex bodies as feasible regions of linear conic programs. In this paper, we introduce the symmetric-cone multiplicative update (SCMU) algorithm for computing cone factorizations in settings where K is symmetric; i.e., the cone is self-dual and homogeneous. Our proposed SCMU algorithm is multiplicative in the sense that each iterate is updated by applying a suitably chosen automorphism of the cone, which is is obtained via a generalization of the geometric mean to symmetric cones. In particular, the SCMU update ensures that iterates remain in the interior of the cone by design. When applied to direct sums of simpler symmetric cones, theSCMUalgorithm preserves the direct sum structure, and hence specifies an algorithm for computing cone factorizations over such cones. By using an extension of the Lieb's concavity theorem to symmetric cones, we showthat the squared-loss objective is non-decreasing under the SCMU algorithm. When specialized to the nonnegative orthant, the SCMU algorithm recovers the seminal multiplicative update algorithm for computing Nonnegative Matrix Factorizations developed by Lee and Seung. Last, we apply theSCMU algorithm to investigate hybrid lifts (combining SDP- and SOCP-based descriptions) of regular polygons from a numerical perspective.