The Saddle Point Problem of Polynomials

Jiawang Nie; Zi Yang; Guangming Zhou

doi:10.1007/s10208-021-09526-8

The Saddle Point Problem of Polynomials

Jiawang Nie
, Zi Yang
, Guangming Zhou

Mathematics and Statistics

University at Albany

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre’s hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence.

Original language	English
Pages (from-to)	1133-1169
Number of pages	37
Journal	Foundations of Computational Mathematics
Volume	22
Issue number	4
DOIs	https://doi.org/10.1007/s10208-021-09526-8
State	Published - Aug 2022

Keywords

Lasserre relaxation
Nonsingularity
Polynomial
Saddle point
Semidefinite program

Access to Document

10.1007/s10208-021-09526-8

Cite this

@article{d9207db65cf74f58a339ec39d0168111,

title = "The Saddle Point Problem of Polynomials",

abstract = "This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre{\textquoteright}s hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence.",

keywords = "Lasserre relaxation, Nonsingularity, Polynomial, Saddle point, Semidefinite program",

author = "Jiawang Nie and Zi Yang and Guangming Zhou",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s).",

year = "2022",

month = aug,

doi = "10.1007/s10208-021-09526-8",

language = "English",

volume = "22",

pages = "1133--1169",

journal = "Foundations of Computational Mathematics",

issn = "1615-3375",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - The Saddle Point Problem of Polynomials

AU - Nie, Jiawang

AU - Yang, Zi

AU - Zhou, Guangming

PY - 2022/8

Y1 - 2022/8

N2 - This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre’s hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence.

AB - This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre’s hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence.

KW - Lasserre relaxation

KW - Nonsingularity

KW - Polynomial

KW - Saddle point

KW - Semidefinite program

UR - https://www.scopus.com/pages/publications/85110276948

U2 - 10.1007/s10208-021-09526-8

DO - 10.1007/s10208-021-09526-8

M3 - Article

SN - 1615-3375

VL - 22

SP - 1133

EP - 1169

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

IS - 4

ER -

The Saddle Point Problem of Polynomials

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this