Products of positive forms, linear matrix inequalities, and {H}ilbert 17th problem for ternary forms

Journal article (2004)

Authors

E. de Klerk Old - EWI Ch. Optimization Technology
DV Pasechnik Old - EWI Ch. Optimization Technology
Research Group
Old - EWI Ch. Optimization Technology
More Info
expand_more

Published Date

2004

Language

Undefined/Unknown

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Research Group

Old - EWI Ch. Optimization Technology

Abstract

A form p on (homogeneous n-variate polynomial) is called positive semidefinite (p.s.d.) if it is nonnegative on . In other words, the zero vector is a global minimizer of p in this case. The famous 17th conjecture of Hilbert [Bull. Amer. Math. Soc. (N.S.), 37 (4) (2000) 407] (later proven by Artin [The Collected Papers of Emil Artin, Addison-Wesley Publishing Co., Inc., Reading, MA, London, 1965]) is that a form p is p.s.d. if and only if it can be decomposed into 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 p.s.d. 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.

Author Keywords: Author Keywords: Semi-definite programming; Ternary forms; Hilbert's 17th problem; Global optimization