Sums of squares certicates

We examime whether $f(x,z) = 2 x^4 + 2 x^3 z - x^2 z^2 + 5 z^4$ can be written as a sum of squares.



In [1]:

    
using Polyopt



In [2]:

    
x, z = variables(["x", "z"]);



In [3]:

    
f = 2*x^4 + 2*x^3*z - x^2*z^2 + 5*z^4;

The degree of $f$ is 4, so we need a second order relaxation,



In [4]:

    
prob = momentprob(2, f);

We solve the problem,



In [5]:

    
X, Z, t, y, solsta = solve_mosek(prob);









    



Open file 'polyopt.task'
Problem
  Name                   :                 
  Objective sense        : max             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 15              
  Cones                  : 0               
  Scalar variables       : 1               
  Matrix variables       : 1               
  Integer variables      : 0               

Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator - tries                  : 0                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Optimizer  - threads                : 4               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 15
Optimizer  - Cones                  : 1
Optimizer  - Scalar variables       : 2                 conic                  : 2               
Optimizer  - Semi-definite variables: 1                 scalarized             : 21              
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 120               after factor           : 120             
Factor     - dense dim.             : 0                 flops                  : 2.70e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   1.5e+00  1.0e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.01  
1   3.1e-01  2.1e-01  3.7e-01  2.33e-02   -1.056985241e+00  -1.198994361e+00  2.1e-01  0.01  
2   5.8e-02  3.8e-02  2.3e-01  1.55e+00   -8.359333125e-02  -5.057825847e-02  3.8e-02  0.01  
3   1.2e-02  7.8e-03  1.1e-01  1.17e+00   -3.081228563e-02  -2.447346289e-02  7.8e-03  0.01  
4   2.8e-03  1.9e-03  5.3e-02  1.09e+00   -6.266733278e-03  -4.923378331e-03  1.9e-03  0.01  
5   8.2e-04  5.4e-04  2.8e-02  1.04e+00   -2.728768959e-03  -2.389405363e-03  5.4e-04  0.01  
6   3.0e-04  2.0e-04  1.8e-02  1.05e+00   -2.873706024e-04  -1.554517993e-04  2.0e-04  0.01  
7   7.6e-05  5.1e-05  8.7e-03  1.00e+00   -3.200709212e-04  -2.912119718e-04  5.1e-05  0.01  
8   1.6e-05  1.1e-05  4.1e-03  1.01e+00   -2.615638047e-05  -1.910262185e-05  1.1e-05  0.01  
9   3.2e-06  2.1e-06  1.8e-03  1.00e+00   -9.387786516e-06  -8.091193792e-06  2.1e-06  0.01  
10  8.2e-07  5.4e-07  9.2e-04  1.00e+00   -1.571764527e-06  -1.232789196e-06  5.4e-07  0.01  
11  2.3e-07  1.5e-07  4.8e-04  9.94e-01   -8.508624409e-07  -7.612519322e-07  1.5e-07  0.01  
12  7.6e-08  5.1e-08  2.8e-04  1.02e+00   -8.025604595e-08  -4.801548839e-08  5.1e-08  0.01  
13  1.8e-08  1.2e-08  1.3e-04  9.96e-01   -6.968714742e-08  -6.291425458e-08  1.2e-08  0.02  
14  3.9e-09  2.6e-09  6.4e-05  1.00e+00   -6.787319801e-09  -5.127503277e-09  2.6e-09  0.02  
15  8.4e-10  5.6e-10  2.9e-05  9.99e-01   -2.639488817e-09  -2.311525824e-09  5.6e-10  0.02  
Interior-point optimizer terminated. Time: 0.02. 

Optimizer terminated. Time: 0.03    

Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -2.6394888170e-09   nrm: 5e+00    Viol.  con: 1e-09    var: 0e+00    barvar: 0e+00  
  Dual.    obj: -2.3115258241e-09   nrm: 1e+00    Viol.  con: 0e+00    var: 5e-10    barvar: 9e-10

Since $t$ is zero, we have a sum-of-squares certificate



In [6]:

    
t









    Out[6]:





-2.639488816988779e-9



In [7]:

    
X[1]









    Out[7]:





6×6 Array{Float64,2}:
  3.57726e-9   -1.81915e-23  -6.74645e-5   …  -2.69095e-5   -4.05731e-5 
 -1.81915e-23   0.00013493    3.03332e-18     -2.09355e-18  -5.24651e-18
 -6.74645e-5    3.03332e-18   5.0              1.20543e-15  -1.16066    
 -5.31613e-24   2.69095e-5   -3.58204e-18      2.3055e-18    2.27659e-18
 -2.69095e-5   -2.09355e-18   1.20543e-15      1.32131       1.0        
 -4.05731e-5   -5.24651e-18  -1.16066      …   1.0           2.0

To verify the sum-of-squares certificate, we compute a monomial vector



In [8]:

    
v = monomials(2, [x, z])









    Out[8]:





6-element Array{Polyopt.Poly{Int64},1}:
 1  
 z  
 z^2
 x  
 x*z
 x^2



In [9]:

    
u = chol(X[1])*v









    Out[9]:





6-element Array{Polyopt.Poly{Float64},1}:
 5.98102e-5-3.0415308296830084e-19*z-1.1279750966692583*z^2-8.888321181151843e-20*x-0.4499152233766339*x*z-0.6783640782805423*x^2
 0.011615929540429733*z+2.3159922819982084e-16*z^2+0.002316606395603652*x-1.9201181869680026e-16*x*z-4.69427727230001e-16*x^2    
 1.930718047759143*z^2-2.1851051249998448e-18*x-0.2628520348531689*x*z-0.9974698114250142*x^2                                    
 0.008705197856060009*x+2.4536638739071805e-16*x*z+1.2914052004525108e-16*x^2                                                    
 1.0245952671050569*x*z+0.4222220402442358*x^2                                                                                   
 0.6054789024617869*x^2

or discarding monomial terms with small coeffients,



In [10]:

    
u = [truncate(ui, 1e-8) for ui=u ]









    Out[10]:





6-element Array{Polyopt.Poly{Float64},1}:
 5.98102e-5-1.1279750966692583*z^2-0.4499152233766339*x*z-0.6783640782805423*x^2
 0.011615929540429733*z+0.002316606395603652*x                                  
 1.930718047759143*z^2-0.2628520348531689*x*z-0.9974698114250142*x^2            
 0.008705197856060009*x                                                         
 1.0245952671050569*x*z+0.4222220402442358*x^2                                  
 0.6054789024617869*x^2

and the sum-of-squares term can be evaluated to



In [11]:

    
truncate(f - dot(u,u), 1e-8)









    Out[11]:





0.0