2018/10/31 by Shenglong Hu, Defeng Sun, Hu, Shenglong +3 · 1 citation
Computer Science · Mathematics · #15A18 #15A42 #15A69 #90C22 #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Tensor decomposition and applications #math.OC #msc:15A18 #msc:15A42 #msc:15A69 #msc:90C22
paper · pdf · doi:10.48550/arxiv.1810.13372
27 pages
arxiv created 2018/10/31 · openalex publication_date 2018/10/31 · arxiv updated 2018/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the polynomial optimization problem of multi-forms over the intersection of the multi-spheres and the nonnegative orthants. This class of problems is NP-hard in general, and includes the problem of finding the best nonnegative rank-one approximation of a given tensor. A Positivstellensatz is given for this class of polynomial optimization problems, based on which a globally convergent hierarchy of doubly nonnegative (DNN) relaxations is proposed. A (zero-th order) DNN relaxation method is applied to solve these problems, resulting in linear matrix optimization problems under both the positive semidefinite and nonnegative conic constraints. A worst case approximation bound is given for this relaxation method. Then, the recent solver SDPNAL+ is adopted to solve this class of matrix optimization problems. Typically, the DNN relaxations are tight, and hence the best nonnegative rank-one approximation of a tensor can be revealed frequently. Extensive numerical experiments show that this approach is quite promising.