KNAW

Research

Semidefinite programming, nonnegative polynomials, and approximation theory

Pagina-navigatie:


Update content


Title Semidefinite programming, nonnegative polynomials, and approximation theory
Period 12 / 2002 - 09 / 2005
Status Completed
Research number OND1297649
Data Supplier Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)

Abstract

Nonnegative polynomials are of fundamental theoretical and practical importance in mathematics. The theoretical research on this topic dates back to the classical work of Hilbert and Artin. A relatively new --- and at first glance unrelated --- branch of (applied) mathematics is that of Semidefinite Programming (SDP), where a linear function of a matrix variable is optimized over the intersection of the positive semi-definite matrices with a given affine space. SDP has received much attention due to its tractability and its many applications in control, combinatorial optimization, engineering design, etc. The link with nonnegative polynomials is as follows: SDP can be used to determine whether or not a given polynomial can be written as a sum of squares of polynomials, by a method known to algebraic geometers as the Gram matrix method. This simple observation has many implications in approximation theory and combinatorial optimization. Moreover, the availability of interior point algorithms for SDP allows us to compute various decompositions of polynomials efficiently. This exciting new research area is largely unexplored, and forms the basis for this proposal.

Abstract (NL)

Niet-negatieve polynomen zijn van fundamentele betekenis zowel in de theoretische als toegepaste wiskunde. Het theoretisch onderzoek ontving een sterke impuls in 1900, omdat toen Hilbert in zijn 17e probleem vroeg of een tekenvaste (dit is overal niet-negatieve) -vorm- (dit is het quotiënt is van twee veeltermen) geschreven kan worden als som van kwadraten van vormen. Dit probleem werd in 1923 in positieve zin opgelost door Artin. Het bewijs van Artin was echter niet-constructief. De vraag hoe men van een gegeven tekenvaste vorm daadwerkelijk een decompositie als som van kwadraten kan vinden bleef in essentie dus onbeantwoord. Een cruciale opmerking is dat tekenvastheid van een veelterm in één variabele equivalent is met het bestaan van een positief semidefiniete (symmetrische) matrix waarvan de sommen van de dwarsdiagonalen gelijk zijn aan de opeenvolgende coëfficiënten van de veelterm. Hierdoor wordt tekenvastheid zogenaamd -semidefiniet representeerbaar-. Het vinden van de betreffende decompositie als som van kwadraten kan hierdoor in principe worden herleid tot het oplossen van een semidefiniet optimaliseringprobleem. Dergelijke problemen kunnen tegenwoordig efficiënt worden opgelost met inwendige punt methoden.

Related organisations

Related people

Researcher Dr. R.A. Dontcheva
Researcher Dr. D.V. Pasechnik
Project leader Prof.dr. E. de Klerk
Project leader Prof.dr.ir. C. Roos

Classification

A90000 Fundamental research
D11200 Algebra, group theory
D11700 Operations research
D16200 Software, algorithms, control systems

Go to page top
Go back to contents
Go back to site navigation