Optimization Online


Products of positive forms, linear matrix inequalities, and Hilbert 17-th problem for ternary forms

E De Klerk (E.deKlerk***at***its.tudelft.nl)
D.V. Pasechnik (D.Pasechnik***at***its.tudelft.nl)

Abstract: A form p on R^n (homogeneous n-variate polynomial) is called positive semidefinite (psd) if it is nonnegative on R^n. In other words, the zero vector is a global minimizer of p in this case. The famous 17th conjecture of Hilbert (later proven by Artin) is that a form p is psd if and only if it can be decomposed a sum of squares of rational functions. In this paper we give an algorithm to compute such a decomposition for ternary forms (n=3). This algorithm involves the solution of a series of systems of linear matrix inequalities (LMI's). In particular, for a given psd ternary form p of degree 2m, we show that the abovementioned decomposition can be computed by solving at most m/4 systems of LMI's of dimensions polynomial in m. The underlying methodology is largely inspired by the original proof of Hilbert, who had been able to prove his conjecture for the case of ternary forms.

Keywords: semidefinite programming, ternary forms, positive semidefinite forms

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Global Optimization (Theory )

Citation: Preprint, TU Delft, Mekelweg 4, 2628 CD, Delft, The Netherlands, 2001

Download: [Postscript]

Entry Submitted: 11/06/2001
Entry Accepted: 11/06/2001
Entry Last Modified: 11/06/2001

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society