Duality properties and sums-of-squares

A simple problem with equality and inequality constraints

We consider a problem with both equality and inequality constraints

\begin{array}{ll} \text{minimize} & x + z\\ \text{subject to} & x - z \geq 0\\ & x^2 + z^2 = 1. \end{array}



In [1]:

    
using Polyopt



In [2]:

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



In [3]:

    
f = x + z;



In [4]:

    
g = x - z;



In [5]:

    
h = x^2 + z^2 - 1;



In [6]:

    
prob = momentprob(2, f, [g], [h]);



In [7]:

    
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       : 7               
  Matrix variables       : 2               
  Integer variables      : 0               

Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 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       : 8                 conic                  : 8               
Optimizer  - Semi-definite variables: 2                 scalarized             : 27              
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                  : 3.36e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.0e+00  1.0e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.01  
1   6.4e-01  3.2e-01  4.1e-01  2.86e-01   -4.653334109e-01  -6.237304963e-01  3.2e-01  0.01  
2   1.4e-01  6.8e-02  3.2e-01  1.01e+00   -1.250925203e+00  -1.213892948e+00  6.8e-02  0.01  
3   1.7e-02  8.3e-03  1.3e-01  1.13e+00   -1.389157294e+00  -1.384192283e+00  8.3e-03  0.01  
4   1.6e-03  8.2e-04  3.8e-02  1.11e+00   -1.412333100e+00  -1.411934407e+00  8.2e-04  0.01  
5   3.9e-04  2.0e-04  1.8e-02  1.05e+00   -1.413859444e+00  -1.413774675e+00  2.0e-04  0.01  
6   1.1e-04  5.5e-05  8.8e-03  1.01e+00   -1.414055001e+00  -1.414038061e+00  5.5e-05  0.01  
7   3.1e-05  1.5e-05  4.3e-03  1.01e+00   -1.414185489e+00  -1.414182344e+00  1.5e-05  0.01  
8   7.8e-06  3.9e-06  2.1e-03  1.00e+00   -1.414201695e+00  -1.414201132e+00  3.9e-06  0.01  
9   1.8e-06  9.2e-07  1.0e-03  1.00e+00   -1.414211646e+00  -1.414211554e+00  9.2e-07  0.01  
10  4.4e-07  2.2e-07  4.8e-04  1.00e+00   -1.414212912e+00  -1.414212896e+00  2.2e-07  0.02  
11  1.1e-07  5.5e-08  2.4e-04  1.00e+00   -1.414213443e+00  -1.414213440e+00  5.5e-08  0.02  
12  2.9e-08  1.4e-08  1.2e-04  1.00e+00   -1.414213518e+00  -1.414213517e+00  1.4e-08  0.02  
13  7.3e-09  3.9e-09  6.0e-05  9.99e-01   -1.414213555e+00  -1.414213555e+00  3.6e-09  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: -1.4142135548e+00   nrm: 1e+00    Viol.  con: 7e-09    var: 0e+00    barvar: 0e+00  
  Dual.    obj: -1.4142135547e+00   nrm: 1e+00    Viol.  con: 0e+00    var: 2e-09    barvar: 4e-09

We inspect the solution,



In [8]:

    
[prob.basis y]









    Out[8]:





15×2 Array{Polyopt.Poly{Float64},2}:
 1.0      1.0      
 z        -0.707154
 z^2      0.500067 
 z^3      -0.353624
 z^4      0.250067 
 x        -0.707059
 x*z      0.5      
 x*z^2    -0.353577
 x*z^3    0.250033 
 x^2      0.499933 
 x^2*z    -0.35353 
 x^2*z^2  0.25     
 x^3      -0.353482
 x^3*z    0.249967 
 x^4      0.249933

and verify optimality



In [9]:

    
t - Polyopt.evalpoly(f, y[[6,2]])









    Out[9]:





-7.409961533255682e-11



In [10]:

    
Polyopt.evalpoly(g, y[[6,2]]) >= 0









    Out[10]:





true



In [11]:

    
abs(Polyopt.evalpoly(h, y[[6,2]])) < 1e-5









    Out[11]:





true

Duality interpretation

The returned solution consists objective value of the relaxation,



In [12]:

    
t









    Out[12]:





-1.4142135547775996

of two semidefinite matrices $X_1$ and $X_2$, corresponding to $f(x,z)$ and $g(x,z)$,



In [13]:

    
X









    Out[13]:





2-element Array{Array{Float64,2},1}:
 [0.762453 0.549465 … -0.139263 -0.281168; 0.549465 0.949308 … -0.00651993 -0.080656; … ; -0.139263 -0.00651993 … 0.839117 -0.0583538; -0.281168 -0.080656 … -0.0583538 0.519432]
 [0.307644 0.312502 0.122507; 0.312502 0.474474 -0.0325033; 0.122507 -0.0325033 0.205813]

a symmetric indefinite matrix $Z_1$ corresponding to $h(x,z$),



In [14]:

    
Z









    Out[14]:





1-element Array{Array{Float64,2},1}:
 [-0.65176 -0.104357 -0.205958; -0.104357 -0.585633 0.0583538; -0.205958 0.0583538 -0.519432]

and $y$ from which we extracted the coefficients for the optimal monomial solution,



In [15]:

    
y









    Out[15]:





15-element Array{Float64,1}:
  1.0     
 -0.707154
  0.500067
 -0.353624
  0.250067
 -0.707059
  0.5     
 -0.353577
  0.250033
  0.499933
 -0.35353 
  0.25    
 -0.353482
  0.249967
  0.249933

The dual interpretation expresses $f(x,z) - t = v_1^T X_1 v_1 + g(x,z) v_2^T X_2 v_2 + h(x,z) v_2^T Z_1 v_2$, in other words we express $f(x,z)-t$ as

$$f(x,z) - t = s_0(x,z) + g(x,z)s_1(x,z) - h(x,z) w(x, z)$$

where $s_0(x,z)$ and $s_1(x,z)$ are sums-of-squares, but $w(x,z)$ is not. Let us verify the expression,



In [16]:

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









    Out[16]:





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



In [17]:

    
v2 = monomials(1, [x,z])









    Out[17]:





3-element Array{Polyopt.Poly{Int64},1}:
 1
 z
 x



In [18]:

    
f-t









    Out[18]:





1.4142135547775996+z+x



In [19]:

    
truncate( dot(v1, X[1]*v1) + g*dot(v2, X[2]*v2) + h*dot(v2, Z[1]*v2), 1e-8 )









    Out[19]:





1.4142135583531192+0.9999999925133197*z+0.9999999999634588*x



In [ ]: