Constrained minimization example

We consider the simple example from the Gloptipoly manual,

\begin{array}{ll} \text{minimize} & -2 x_1 + x_2 - x_3\\ \text{subject to} & 24 - 20 x_1 + 9 x_2 - 13 x_3 + 4 x_1^2 - 4 x_1 x_2 + 4 x_1 x_3 + 2 x_2^2 - 2 x_2 x_3 + 2 x_3^2 \geq 0\\ & x_1 + x_2 + x_3 \leq 4, \quad 3 x_2 \leq 6\\ & 0 \leq x_1 \leq 2, \quad 0 \leq x_2, \quad 0\leq x_3\leq 3 \end{array}



In [1]:

    
using Polyopt

We define the variables



In [2]:

    
x1, x2, x3 = variables(["x1","x2","x3"]);

and the objective function



In [3]:

    
f = -2*x1 + x2 - x3;

and an array with all inequalities in the form $g_i(x) \geq 0$,



In [4]:

    
g = [24 - 20*x1 + 9*x2 - 13*x3 + 4*x1^2 - 4*x1*x2 + 4*x1*x3 + 2*x2^2 - 2*x2*x3 + 2*x3^2,
     4 - (x1 + x2 + x3),
     6 - (3*x2 + x3),
     x1, 2-x1, 
     x2, 
     x3, 3-x3]









    Out[4]:





8-element Array{Polyopt.Poly{Int64},1}:
 24-13*x3+2*x3^2+9*x2-2*x2*x3+2*x2^2-20*x1+4*x1*x3-4*x1*x2+4*x1^2
 4-x3-x2-x1                                                      
 6-x3-3*x2                                                       
 x1                                                              
 2-x1                                                            
 x2                                                              
 x3                                                              
 3-x3

Solving the second-order moment relaxation

This problem has multiple optimal minima, so we perturb the problem to locate one of the minimizers,



In [5]:

    
prob = momentprob(2, f + 1e-3*(x1+x2+x3), g);

We next solve the problem using MOSEK, turning off log-output:



In [6]:

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



In [7]:

    
t









    Out[7]:





-5.688354583203682

Solving the third-order moment relaxation



In [8]:

    
prob = momentprob(3, f + 1e-3*(x1+x2+x3), g);



In [9]:

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

The lower bound decreases going from order two to order three,



In [10]:

    
t









    Out[10]:





-4.064806932586617

Solving the fourth-order order moment relaxation



In [11]:

    
prob = momentprob(4, f + 1e-3*(x1+x2+x3), g);

We solve the fourth-order relaxation, this time showing the log-output from the solver,



In [12]:

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









    



Open file 'polyopt.task'
Problem
  Name                   :                 
  Objective sense        : max             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 165             
  Cones                  : 0               
  Scalar variables       : 1               
  Matrix variables       : 9               
  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            : 165
Optimizer  - Cones                  : 1
Optimizer  - Scalar variables       : 2                 conic                  : 2               
Optimizer  - Semi-definite variables: 9                 scalarized             : 2310            
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 : 1.37e+04          after factor           : 1.37e+04        
Factor     - dense dim.             : 0                 flops                  : 4.49e+06        
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   5.8e-01  3.8e-01  3.0e-01  -2.46e-02  5.354328913e-01   -2.498346026e-01  3.8e-01  0.01  
2   2.5e-01  1.7e-01  1.6e-01  -5.67e-02  -3.460869631e-03  -6.484988902e-01  1.7e-01  0.02  
3   1.0e-01  6.6e-02  1.3e-01  8.27e-01   -7.818898506e-01  -8.565003054e-01  6.6e-02  0.02  
4   4.5e-02  3.0e-02  9.2e-02  1.21e+00   -1.101371626e+00  -1.139945796e+00  3.0e-02  0.03  
5   1.1e-02  7.5e-03  4.6e-02  1.15e+00   -1.606437915e+00  -1.616702602e+00  7.5e-03  0.04  
6   4.2e-03  2.8e-03  1.9e-02  5.78e-01   -2.334125841e+00  -2.347107798e+00  2.8e-03  0.04  
7   1.6e-03  1.1e-03  1.1e-02  7.57e-01   -2.847574109e+00  -2.853939720e+00  1.1e-03  0.05  
8   5.7e-04  3.8e-04  6.3e-03  9.13e-01   -3.150346625e+00  -3.152705940e+00  3.8e-04  0.07  
9   3.0e-04  2.0e-04  3.4e-03  6.24e-01   -3.278009107e+00  -3.280645322e+00  2.0e-04  0.08  
10  1.4e-04  9.1e-05  1.9e-03  6.88e-01   -3.436416768e+00  -3.438216712e+00  9.1e-05  0.08  
11  7.2e-05  4.8e-05  9.9e-04  2.58e-01   -3.554698422e+00  -3.556684047e+00  4.8e-05  0.09  
12  2.6e-05  1.7e-05  4.5e-04  3.73e-01   -3.771501425e+00  -3.772801130e+00  1.7e-05  0.10  
13  3.4e-06  2.2e-06  1.7e-04  7.95e-01   -3.966193345e+00  -3.966347469e+00  2.2e-06  0.10  
14  7.9e-07  5.3e-07  7.6e-05  1.03e+00   -3.990433768e+00  -3.990476956e+00  5.3e-07  0.11  
15  5.6e-08  3.7e-08  2.1e-05  1.03e+00   -3.997473055e+00  -3.997475862e+00  3.7e-08  0.12  
16  2.6e-09  2.0e-09  4.7e-06  1.02e+00   -3.997974389e+00  -3.997974508e+00  1.8e-09  0.12  
17  6.4e-10  1.3e-08  7.1e-07  9.88e-01   -3.997999571e+00  -3.997999573e+00  3.0e-11  0.13  
18  1.3e-09  3.0e-07  1.2e-07  1.00e+00   -3.997999988e+00  -3.997999988e+00  8.3e-13  0.13  
Interior-point optimizer terminated. Time: 0.13. 

Optimizer terminated. Time: 0.13    

Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -3.9979999882e+00   nrm: 2e+01    Viol.  con: 4e-07    var: 0e+00    barvar: 0e+00  
  Dual.    obj: -3.9979999883e+00   nrm: 4e+02    Viol.  con: 0e+00    var: 5e-12    barvar: 4e-12

Again the lower increases when we increase the relaxation order,



In [13]:

    
t









    Out[13]:





-3.997999988220454

At this point the hierarchy of relaxations has converged; higher order relaxations give the same bound. Let us inspect the recovered solution



In [14]:

    
[prob.basis y]









    Out[14]:





165×2 Array{Polyopt.Poly{Float64},2}:
 1.0           1.0        
 x3            7.95982e-6 
 x3^2          2.38727e-5 
 x3^3          7.16109e-5 
 x3^4          0.000214822
 x3^5          0.000644446
 x3^6          0.0019333  
 x3^7          0.0057998  
 x3^8          14.2424    
 x2            6.80074e-9 
 x2*x3         1.22965e-8 
 x2*x3^2       3.30135e-8 
 x2*x3^3       9.46562e-8 
 ⋮                        
 x1^5*x2^2*x3  -0.566143  
 x1^5*x2^3     1.37997    
 x1^6          63.9998    
 x1^6*x3       1.96216e-7 
 x1^6*x3^2     3.22142    
 x1^6*x2       1.2041e-7  
 x1^6*x2*x3    -0.344823  
 x1^6*x2^2     3.18658    
 x1^7          128.0      
 x1^7*x3       -2.09519   
 x1^7*x2       2.03974    
 x1^8          266.08

Let us verify that the recovered solution



In [15]:

    
X1, X2, X3 = Polyopt.vectorize([x1,x2,x3], 8)*y









    Out[15]:





3-element Array{Float64,1}:
 2.0       
 6.80074e-9
 7.95982e-6

is optimal. It achieves the same objective value as the relaxation,



In [16]:

    
Polyopt.evalpoly(f, [X1; X2; X3])









    Out[16]:





-3.9999999922512517

and it is feasible,



In [17]:

    
[ Polyopt.evalpoly(gi, [X1; X2; X3]) for gi=g ]









    Out[17]:





8-element Array{Float64,1}:
 -2.38707e-5
  2.0       
  5.99999   
  2.0       
  3.98038e-6
  6.80074e-9
  7.95982e-6
  2.99999



In [ ]: