Re: Expressing a polynomial as a sum of squares
- From: borchers@xxxxxxx (Brian Borchers)
- Date: Thu, 27 Oct 2005 14:30:07 +0000 (UTC)
> 27-10u^2+27u^4-128uv-10v^2+108u^2v^2+54u^4v^2+27v^4 +54u^2v^4+27u^4v^4
>
> (a) Can this polynomial be written as the sum of squares of
> polynomials?
> (b) If so, can you find an explicit representation?
> (c) Is there a general algorithm that can be used to express a
> polynomial as the
> sum of squares of polynomials when such a representation exists?
> (d) Is the problem any easier for univariate polynomials?
There has been interesting work on using conic optimization to determine
whether or not a multivariate polynomial can be written as a sum of squares.
The software package SOSTOOLS available from
http://www.cds.caltech.edu/sostools/
can be used to do the calculations. There are several relevant papers
at this web site.
In solving these problems there are some difficult numerical issues:
It may or may not be possible to round off the solution to the conic
optimization problem to an exact rational solution to the sum of
squares problem.
> (a) Can this polynomial be written as the sum of squares of
> polynomials?
> (b) If so, can you find an explicit representation?
Here's some output from SOSTOOLS. First, we use floating point arithmetic.
>>Size: 81 25
>>
>>SeDuMi 1.05R5 by Jos F. Sturm, 1998, 2001-2003.
>>Alg = 2: xz-corrector, theta = 0.250, beta = 0.500
>>eqs m = 25, order n = 10, dim = 82, blocks = 2
>>nnz(A) = 45 + 0, nnz(ADA) = 625, nnz(L) = 325
>> it : b*y gap delta rate t/tP* t/tD* feas cg cg
>> 0 : 1.37E+01 0.000
>> 1 : -1.51E+01 3.77E+00 0.000 0.2745 0.9000 0.9000 1.66 1 1
>> 2 : -7.48E-01 3.07E-01 0.000 0.0814 0.9900 0.9900 1.58 1 1
>> 3 : -1.69E-02 7.37E-03 0.000 0.0240 0.9900 0.9900 1.12 1 1
>> 4 : -1.78E-03 8.17E-04 0.000 0.1110 0.9450 0.9450 0.95 1 1
>> 5 : -7.97E-05 3.43E-05 0.000 0.0419 0.9900 0.9900 0.96 1 1
>> 6 : -1.47E-05 6.19E-06 0.000 0.1806 0.9000 0.9000 0.95 1 2
>> 7 : -7.40E-07 2.30E-07 0.424 0.0372 0.9900 0.9900 1.02 2 2
>> 8 : -8.76E-08 2.78E-08 0.007 0.1209 0.9450 0.9450 1.16 4 4
>> 9 : -1.55E-08 5.25E-09 0.000 0.1885 0.9000 0.9000 1.13 4 4
>> 10 : -1.65E-09 5.84E-10 0.188 0.1112 0.9450 0.9450 1.06 6 6
>> 11 : -1.97E-10 7.09E-11 0.248 0.1215 0.9450 0.9450 1.03 7 9
>>Run into numerical problems.
>>iter seconds digits c*x b*y
>> 11 0.1 11.1 0.0000000000e+00 -1.9717003602e-10
>>|Ax-b| = 6.7e-10, [Ay-c]_+ = 1.3E-12, |x|= 1.7e+02, |y|= 1.8e-01
>>Max-norms: ||b||=128, ||c|| = 0,
>>Cholesky |add|=0, |skip| = 2, ||L.L|| = 4.686.
>>
>>Residual norm: 6.6677e-10
>>
>> cpusec: 0.1400
>> iter: 11
>> feasratio: 1.0296
>> pinf: 0
>> dinf: 0
>> numerr: 0
>>
>>
>>Q =
>>
>> Columns 1 through 7
>>
>> 27.0000 -0.0000 -16.8611 0.0000 -41.6518 0.0000 -16.8611
>> -0.0000 23.7221 -0.0000 -22.3482 -0.0000 -14.1962 -0.0000
>> -16.8611 -0.0000 27.0000 -0.0000 14.1962 0.0000 8.2380
>> 0.0000 -22.3482 -0.0000 23.7223 0.0000 10.0744 -0.0000
>> -41.6518 -0.0000 14.1962 0.0000 84.9823 -0.0000 14.1964
>> 0.0000 -14.1962 0.0000 10.0744 -0.0000 47.1070 0.0000
>> -16.8611 -0.0000 8.2380 -0.0000 14.1964 0.0000 27.0000
>> -0.0000 10.0746 0.0000 -14.1964 0.0000 -34.7415 0.0000
>> -16.8781 0.0000 3.4465 -0.0000 34.7415 -0.0000 3.4465
>>
>> Columns 8 through 9
>>
>> -0.0000 -16.8781
>> 10.0746 0.0000
>> 0.0000 3.4465
>> -14.1964 -0.0000
>> 0.0000 34.7415
>> -34.7415 -0.0000
>> 0.0000 3.4465
>> 47.1070 0.0000
>> 0.0000 27.0000
>>
>>
>>Z =
>>
>>[ 1]
>>[ v]
>>[ v^2]
>>[ u]
>>[ u*v]
>>[ u*v^2]
>>[ u^2]
>>[ u^2*v]
>>[ u^2*v^2]
This says that papprox(u,v)=Z'*Q*Z is a close numerical
approximation to the original polynomial. However, when we attempt to
get an exact solution with rational coefficients, we get:
>>Could not compute a rational SOS!
>>
>>Q =
>>
>>[ empty sym ]
>>
>>
>>Z =
>>
>> []
This suggests that this problem is numerically challenging. I'd
encourage you to contact the authors of SOSTOOLS- they might be able
to solve your problem by finding a solution in rational arithmetic,
or show that no such solution exists.
> (c) Is there a general algorithm that can be used to express a
> polynomial as the sum of squares of polynomials when such a
> representation exists?
The conic programming approach can in theory do this, although in
practice you can run into numerical problems as we did here.
Note that being able to find a sum of squares representation does not
solve the problem of "Is this polynomial always nonnegative?", since a
polynomial might be nonnegative but not have a sum of squares
representation.
However,
For univariate polynomials, p(x)>=0 for all x if and only if p(x) can
be written as a sum of squares.
For bivariate quartic polynomials (like the one given here), it can
also be shown that p(u,v)>=0 for all u and v if and only if p(u,v) can
be written as a sum of squares.
In these particular cases, nonnegativity of the polynomial is equivalent
to the polynomial having a sum of squares representation.
> (d) Is the problem any easier for univariate polynomials?
What do you mean by "easier"? In theory, for either the univariate or
multivariate cases, the conic optimization problems can be solved to
any desired accuracy in polynomial time, thus providing a solution to
the problem.
--
Brian Borchers borchers@xxxxxxx
Department of Mathematics http://www.nmt.edu/~borchers/
New Mexico Tech Phone: 505-835-5813
Socorro, NM 87801 FAX: 505-835-5366
.
- References:
- Expressing a polynomial as a sum of squares
- From: Stan Rabinowitz
- Re: Expressing a polynomial as a sum of squares
- From: José Carlos Santos
- Expressing a polynomial as a sum of squares
- Prev by Date: Re: Extended Beta function?
- Next by Date: Re: Extended Beta function?
- Previous by thread: Re: Expressing a polynomial as a sum of squares
- Next by thread: Re: Expressing a polynomial as a sum of squares
- Index(es):
Relevant Pages
|
