Global optimization of low-rank polynomials

Llorenç Balada Gaggioli; Didier Henrion; Milan Korda

doi:10.48550/arxiv.2512.08394

Abstract

This work considers polynomial optimization problems where the objective admits a low-rank canonical polyadic tensor decomposition. We introduce LRPOP (low-rank polynomial optimization), a new hierarchy of semidefinite programming relaxations for which the size of the semidefinite blocks is determined by the canonical polyadic rank rather than the number of variables. As a result, LRPOP can solve low-rank polynomial optimization problems that are far beyond the reach of existing sparse hierarchies. In particular, we solve problems with up to thousands of variables with total degree in the thousands. Numerical conditioning for problems of this size is improved by using the Bernstein basis. The LRPOP hierarchy converges from below to the global minimum of the polynomial under standard assumptions.

Affiliated Institutions

Related Publications

GloptiPoly

Didier Henrion , Jean B. Lasserre

GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally nonconvex) global optimization problem of minimizing a mult...

2003 ACM Transactions on Mathematical Soft... 376 citations

Global Optimization with Polynomials and the Problem of Moments

Jean B. Lasserre

We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x): {\mathbb{R}}^n\to {\mathbb{R}}$, as well as the global minimum of p(x), in ...

2001 SIAM Journal on Optimization 2531 citations

Interior-Point Method for Nuclear Norm Approximation with Application to System Identification

Zhang Liu , Lieven Vandenberghe

The nuclear norm (sum of singular values) of a matrix is often used in convex heuristics for rank minimization problems in control, signal processing, and statistics. Such heuri...

2009 SIAM Journal on Matrix Analysis and A... 504 citations

Applied Regression Analysis and Other Multivariable Methods

Esteban Walker , David G. Kleinbaum , Lawrence L. Kupper +1 more

1. CONCEPTS AND EXAMPLES OF RESEARCH. Concepts. Examples. Concluding Remarks. References. 2. CLASSIFICATION OF VARIABLES AND THE CHOICE OF ANALYSIS. Classification of Variables....

1989 Technometrics 8347 citations

A Singular Value Thresholding Algorithm for Matrix Completion

Jian‐Feng Cai , Emmanuel J. Candès , Zuowei Shen

This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understoo...

2010 SIAM Journal on Optimization 5710 citations

Publication Info

Year: 2025
Type: preprint
Citations: 0
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

Global optimization of low-rank polynomials

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

OpenAlex

Cite This

APA Style

                            
                                    Llorenç Balada Gaggioli, 
                                
                                    Didier Henrion, 
                                
                                    Milan Korda
                                
                            (2025). 
                            Global optimization of low-rank polynomials. 
                            arXiv (Cornell University)
                            
                            .
                            https://doi.org/10.48550/arxiv.2512.08394

Identifiers

DOI: 10.48550/arxiv.2512.08394