4.6 Article

Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks

相关参考文献

注意:仅列出部分参考文献,下载原文获取全部文献信息。
Article Computer Science, Software Engineering

Sum-of-squares chordal decomposition of polynomial matrix inequalities

Yang Zheng et al.

Summary: In this paper, we prove decomposition theorems for sparse positive (semi)definite polynomial matrices and provide some specific forms of decomposition. We also propose sparse SOS reformulations for convex optimization problems with large and sparse polynomial matrix inequalities. Numerical examples demonstrate the lower computational complexity of these reformulations.

MATHEMATICAL PROGRAMMING (2023)

Article Computer Science, Software Engineering

CS-TSSOS: Correlative and Term Sparsity for Large-Scale Polynomial Optimization

Jie Wang et al.

Summary: This work proposes a new moment-SOS hierarchy, called CS-TSSOS, for solving large-scale sparse polynomial optimization problems. Its novelty is to exploit simultaneously correlative sparsity and term sparsity by combining advantages of two existing frameworks for sparse polynomial optimization.

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE (2022)

Article Mathematics, Applied

Bounding the separable rank via polynomial optimization

Sander Gribling et al.

Summary: This study investigates questions related to linear maps acting on a specific set SEPd, which consists of maps that can be expressed as a convex combination of rank one matrices. The study introduces bounds for the separable rank, and uses the moment method to obtain a hierarchy of semidefinite-based lower bounds. The approach can be extended to the multipartite setting and the real separable rank, and it strengthens known bounds for the completely positive rank.

LINEAR ALGEBRA AND ITS APPLICATIONS (2022)

Article Automation & Control Systems

Stability and Performance Verification of Dynamical Systems Controlled by Neural Networks: Algorithms and Complexity

Milan Korda

Summary: This letter contributes to the stability and performance verification of nonlinear dynamical systems controlled by neural networks. The authors show that the stability and performance of a polynomial dynamical system controlled by a neural network with semialgebraically representable activation functions can be certified using convex semidefinite programming. They also remark that the problem of verifying asymptotic stability for a linear system controlled by a neural network with ReLU activation functions is undecidable. Additionally, they establish a converse result on the existence of a polynomial Lyapunov function for this class of systems.

IEEE CONTROL SYSTEMS LETTERS (2022)

Article Mathematics, Applied

TSSOS: A MOMENT-SOS HIERARCHY THAT EXPLOITS TERM SPARSITY

Jie Wang et al.

Summary: This paper introduces a new hierarchy of semidefinite programming relaxations for polynomial optimization problems, exploiting the sparsity of input polynomials. The novelty lies in involving block-diagonal matrices obtained through an iterative procedure for completing connected components of certain adjacency graphs. The theoretical framework is then applied to compute lower bounds for polynomial optimization problems.

SIAM JOURNAL ON OPTIMIZATION (2021)

Article Mathematics, Applied

CHORDAL-TSSOS: A MOMENT-SOS HIERARCHY THAT EXPLOITS TERM SPARSITY WITH CHORDAL EXTENSION

Jie Wang et al.

Summary: The chordal-TSSOS hierarchy proposed in this work is a sparse moment-SOS framework based on term sparsity and chordal extension, utilizing block matrices and adjacency graphs for semidefinite programming relaxations to achieve efficiency and scalability in polynomial optimization problems.

SIAM JOURNAL ON OPTIMIZATION (2021)

Article Engineering, Electrical & Electronic

A Clique Merging Algorithm to Solve Semidefinite Relaxations of Optimal Power Flow Problems

Julie Sliwak et al.

Summary: In this paper, a new strategy for computing efficient clique decompositions for the SDP problem is proposed, using a clique merging heuristic based on two different estimates of the computational burden. Comparisons with other algorithms on MATPOWER instances show a significant decrease in solver time.

IEEE TRANSACTIONS ON POWER SYSTEMS (2021)

Review Automation & Control Systems

Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization

Yang Zheng et al.

Summary: Chordal and factor-width decomposition methods have enabled the analysis and control of large-scale linear systems and medium-scale nonlinear systems. Chordal decomposition exploits matrix sparsity in semidefinite programming for more efficient solving, while factor-width decompositions trade feasibility or optimality for lower computational complexity in solving dense matrices. These methods allow for significant computational savings and have potential applications in various fields like control theory and machine learning.

ANNUAL REVIEWS IN CONTROL (2021)

Proceedings Paper Automation & Control Systems

A clique graph based merging strategy for decomposable SDPs

Michael Garstka et al.

IFAC PAPERSONLINE (2020)

Article Computer Science, Theory & Methods

Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

Sander Gribling et al.

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS (2019)

Article Operations Research & Management Science

Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets

Jean B. Lasserre et al.

MATHEMATICS OF OPERATIONS RESEARCH (2019)

Article Mathematics, Applied

Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization

Gennadiy Averkov

SIAM JOURNAL ON APPLIED ALGEBRA AND GEOMETRY (2019)

Article Mathematics, Applied

LASSERRE HIERARCHY FOR LARGE SCALE POLYNOMIAL OPTIMIZATION IN REAL AND COMPLEX VARIABLES

Cedric Josz et al.

SIAM JOURNAL ON OPTIMIZATION (2018)

Article Mathematics, Applied

JuMP: A Modeling Language for Mathematical Optimization

Iain Dunning et al.

SIAM REVIEW (2017)

Article Mathematics, Applied

Julia: A Fresh Approach to Numerical Computing

Jeff Bezanson et al.

SIAM REVIEW (2017)

Article Mathematics, Applied

Symmetric Tensor Nuclear Norms

Jiawang Nie

SIAM JOURNAL ON APPLIED ALGEBRA AND GEOMETRY (2017)

Article Automation & Control Systems

Stability and performance verification of optimization-based controllers

Milan Korda et al.

AUTOMATICA (2017)

Article Computer Science, Software Engineering

Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank

Hamza Fawzi et al.

MATHEMATICAL PROGRAMMING (2016)

Article Mathematics, Applied

RELATIVE ENTROPY RELAXATIONS FOR SIGNOMIAL OPTIMIZATION

Venkat Chandrasekaran et al.

SIAM JOURNAL ON OPTIMIZATION (2016)

Article Mathematics, Applied

ON THE TURING MODEL COMPLEXITY OF INTERIOR POINT METHODS FOR SEMIDEFINITE PROGRAMMING

Etienne de Klerk et al.

SIAM JOURNAL ON OPTIMIZATION (2016)

Article Mathematics

Amoebas, nonnegative polynomials and sums of squares supported on circuits

Sadik Iliman et al.

RESEARCH IN THE MATHEMATICAL SCIENCES (2016)

Article Operations Research & Management Science

Approximation Limits of Linear Programs (Beyond Hierarchies)

Gabor Braun et al.

MATHEMATICS OF OPERATIONS RESEARCH (2015)

Article Mathematics, Applied

NEW LOWER BOUNDS AND ASYMPTOTICS FOR THE CP-RANK

Immanuel M. Bomze et al.

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS (2015)

Article Operations Research & Management Science

On the computational complexity of membership problems for the completely positive cone and its dual

Peter J. C. Dickinson et al.

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS (2014)

Article Computer Science, Theory & Methods

The -Truncated -Moment Problem

Jiawang Nie

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS (2014)

Article Mathematics, Applied

From seven to eleven: Completely positive matrices with high cp-rank

Immanuel M. Bomze et al.

LINEAR ALGEBRA AND ITS APPLICATIONS (2014)

Article Operations Research & Management Science

Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization

Cordian Riener et al.

MATHEMATICS OF OPERATIONS RESEARCH (2013)

Article Mathematics, Applied

ON THE CP-RANK AND MINIMAL CP FACTORIZATIONS OF A COMPLETELY POSITIVE MATRIX

Naomi Shaked-Monderer et al.

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS (2013)

Article Mathematics, Applied

On the geometric interpretation of the nonnegative rank

Nicolas Gillis et al.

LINEAR ALGEBRA AND ITS APPLICATIONS (2012)

Article Computer Science, Theory & Methods

Treewidth computations I. Upper bounds

Hans L. Bodlaender et al.

INFORMATION AND COMPUTATION (2010)

Article Mathematics, Applied

Real rank versus nonnegative rank

LeRoy B. Beasley et al.

LINEAR ALGEBRA AND ITS APPLICATIONS (2009)

Article Mathematics, Applied

ON THE COMPLEXITY OF NONNEGATIVE MATRIX FACTORIZATION

Stephen A. Vavasis

SIAM JOURNAL ON OPTIMIZATION (2009)

Article Computer Science, Software Engineering

A semidefinite programming approach to the generalized problem of moments

Jean B. Lasserre

MATHEMATICAL PROGRAMMING (2008)

Article Mathematics

A note on the representation of positive polynomials with structured sparsity

David Grimm et al.

ARCHIV DER MATHEMATIK (2007)

Article Mathematics, Applied

Convergent SDP-relaxations in polynomial optimization with sparsity

Jean B. Lasserre

SIAM JOURNAL ON OPTIMIZATION (2006)

Article Mathematics, Applied

The maximal cp-rank of rank k completely positive matrices

F Barioli et al.

LINEAR ALGEBRA AND ITS APPLICATIONS (2003)

Article Mathematics, Applied

Global optimization with polynomials and the problem of moments

JB Lasserre

SIAM JOURNAL ON OPTIMIZATION (2001)

Article Mathematics

The truncated complex K-moment problem

RE Curto et al.

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY (2000)