Exterior of ellipsoid
Adapted from: (Floudas et al., 1999; Section 3.5) and (Lasserre, 2009; Table 5.1)
Introduction
Consider the polynomial optimization problem from (Floudas et al., 1999; Section 3.5)
A = [
0 0 1
0 -1 0
-2 1 -1
]
bz = [3, 0, -4] - [0, -1, -6]
y = [1.5, -0.5, -5]
using DynamicPolynomials
@polyvar x[1:3]
p = -2x[1] + x[2] - x[3]
using SumOfSquares
e = A * x - y
f = e'e - bz'bz / 4
K = @set sum(x) <= 4 && 3x[2] + x[3] <= 6 && f >= 0 && 0 <= x[1] && x[1] <= 2 && 0 <= x[2] && 0 <= x[3] && x[3] <= 3Basic semialgebraic Set defined by no equality
8 inequalities
4.0 - x[3] - x[2] - x[1] ≥ 0
6.0 - x[3] - 3.0*x[2] ≥ 0
24.0 - 13.0*x[3] + 9.0*x[2] - 20.0*x[1] + 2.0*x[3]^2 - 2.0*x[2]*x[3] + 2.0*x[2]^2 + 4.0*x[1]*x[3] - 4.0*x[1]*x[2] + 4.0*x[1]^2 ≥ 0
x[1] ≥ 0
2.0 - x[1] ≥ 0
x[2] ≥ 0
x[3] ≥ 0
3.0 - x[3] ≥ 0
We will now see how to find the optimal solution using Sum of Squares Programming. We first need to pick an SDP solver, see here for a list of the available choices.
import Hypatia
using Dualization
solver = dual_optimizer(Hypatia.Optimizer)#7 (generic function with 1 method)A Sum-of-Squares certificate that $p \ge \alpha$ over the domain S, ensures that $\alpha$ is a lower bound to the polynomial optimization problem. The following function searches for the largest lower bound and finds zero using the dth level of the hierarchy`.
function solve(d)
model = SOSModel(solver)
@variable(model, α)
@objective(model, Max, α)
@constraint(model, c, p >= α, domain = K, maxdegree = d)
optimize!(model)
println(solution_summary(model))
return model
endsolve (generic function with 1 method)The first level of the hierarchy gives a lower bound of -7`
model2 = solve(2)
Hypatia v0.11.0
Floating-point type: Float64.
Problem with 3 variables, 0 equality constraints and 1 cone:
8-dimensional nonnegative cone.
iter p_obj d_obj | abs_gap x_feas z_feas | tau kap mu | dir_res prox step alpha
0 -1.6284e+00 -8.5958e+00 | 8.00e+00 5.25e-01 8.46e-02 | 1.00e+00 1.00e+00 1.00e+00 |
1 -5.5506e+00 -6.8229e+00 | 1.13e+00 1.14e-01 1.83e-02 | 6.93e-01 3.14e-01 1.50e-01 | 2.2e-16 8.2e-01 co-a 8.50e-01
2 -5.8838e+00 -6.1656e+00 | 2.46e-01 2.29e-02 3.69e-03 | 6.88e-01 4.51e-02 3.08e-02 | 5.0e-15 7.0e-01 co-a 8.00e-01
3 -5.9733e+00 -6.0031e+00 | 2.59e-02 2.28e-03 3.67e-04 | 6.91e-01 3.31e-03 3.13e-03 | 6.9e-15 9.2e-01 co-a 9.00e-01
4 -5.9989e+00 -6.0021e+00 | 2.08e-03 2.69e-04 4.34e-05 | 5.85e-01 5.29e-04 2.66e-04 | 4.0e-15 9.8e-01 co-a 9.00e-01
5 -5.9998e+00 -6.0003e+00 | 2.78e-04 4.57e-05 7.37e-06 | 5.17e-01 7.44e-05 3.52e-05 | 1.7e-11 8.2e-01 co-a 8.50e-01
6 -5.9999e+00 -6.0000e+00 | 4.19e-05 7.07e-06 1.14e-06 | 5.02e-01 8.39e-06 5.13e-06 | 5.9e-13 6.0e-01 co-a 8.50e-01
7 -6.0000e+00 -6.0000e+00 | 3.68e-06 7.84e-07 1.26e-07 | 4.52e-01 1.05e-06 4.62e-07 | 1.9e-12 3.8e-01 co-a 9.00e-01
8 -6.0000e+00 -6.0000e+00 | 3.82e-07 7.78e-08 1.25e-08 | 4.56e-01 8.18e-08 4.66e-08 | 2.8e-11 7.6e-01 co-a 9.00e-01
9 -6.0000e+00 -6.0000e+00 | 4.96e-08 1.30e-08 2.10e-09 | 4.08e-01 1.63e-08 6.25e-09 | 4.0e-11 4.8e-01 co-a 8.50e-01
10 -6.0000e+00 -6.0000e+00 | 5.23e-09 1.27e-09 2.05e-10 | 4.18e-01 1.28e-09 6.41e-10 | 3.9e-12 9.1e-01 co-a 9.00e-01
optimal solution found; terminating
status is Optimal after 10 iterations and 0.002 seconds
solution_summary(; result = 1, verbose = false)
├ solver_name : Dual model with Hypatia attached
├ Termination
│ ├ termination_status : OPTIMAL
│ ├ result_count : 1
│ └ raw_status : Optimal
├ Solution (result = 1)
│ ├ primal_status : FEASIBLE_POINT
│ ├ dual_status : FEASIBLE_POINT
│ ├ objective_value : -6.00000e+00
│ └ dual_objective_value : -6.00000e+00
└ Work counters
├ solve_time (sec) : 2.48599e-03
└ barrier_iterations : 10The second level improves the lower bound
model4 = solve(4)
Hypatia v0.11.0
Floating-point type: Float64.
Problem with 19 variables, 0 equality constraints and 9 cones:
1-dimensional nonnegative cone.
10-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
iter p_obj d_obj | abs_gap x_feas z_feas | tau kap mu | dir_res prox step alpha
0 -1.3734e+00 -1.2127e+01 | 3.30e+01 2.27e+00 2.99e-01 | 1.00e+00 1.00e+00 1.00e+00 |
1 -1.4460e+00 -5.7608e+00 | 9.87e+00 9.61e-01 1.27e-01 | 7.08e-01 4.69e-01 3.00e-01 | 3.6e-15 5.6e-01 co-a 7.00e-01
2 -2.0209e+00 -3.3405e+00 | 2.82e+00 2.85e-01 3.76e-02 | 7.16e-01 1.13e-01 8.54e-02 | 8.9e-16 9.8e-01 co-a 7.00e-01
3 -3.2621e+00 -3.9154e+00 | 1.02e+00 1.51e-01 1.98e-02 | 5.42e-01 6.89e-02 3.10e-02 | 6.7e-16 7.8e-01 co-a 6.00e-01
4 -4.3199e+00 -4.6348e+00 | 3.81e-01 7.40e-02 9.75e-03 | 4.42e-01 3.02e-02 1.16e-02 | 1.2e-15 9.8e-01 co-a 6.00e-01
5 -5.1818e+00 -5.3342e+00 | 1.41e-01 3.71e-02 4.89e-03 | 3.52e-01 1.41e-02 4.28e-03 | 6.3e-15 8.9e-01 co-a 6.00e-01
6 -5.4507e+00 -5.5301e+00 | 6.95e-02 1.87e-02 2.46e-03 | 3.50e-01 6.08e-03 2.11e-03 | 1.7e-14 7.0e-01 co-a 5.00e-01
7 -5.6031e+00 -5.6266e+00 | 2.09e-02 5.47e-03 7.21e-04 | 3.58e-01 1.74e-03 6.32e-04 | 1.1e-14 5.1e-01 co-a 7.00e-01
8 -5.6824e+00 -5.6848e+00 | 1.99e-03 5.68e-04 7.48e-05 | 3.45e-01 1.89e-04 6.04e-05 | 8.6e-15 7.5e-01 co-a 9.00e-01
9 -5.6904e+00 -5.6909e+00 | 3.83e-04 1.18e-04 1.56e-05 | 3.32e-01 3.46e-05 1.16e-05 | 2.4e-13 7.2e-01 co-a 8.00e-01
10 -5.6919e+00 -5.6920e+00 | 7.60e-05 2.39e-05 3.14e-06 | 3.29e-01 6.57e-06 2.30e-06 | 1.1e-12 8.7e-01 co-a 8.00e-01
11 -5.6922e+00 -5.6922e+00 | 2.23e-05 7.32e-06 9.64e-07 | 3.21e-01 2.08e-06 6.75e-07 | 2.7e-12 2.7e-01 co-a 7.00e-01
12 -5.6923e+00 -5.6923e+00 | 1.11e-06 3.68e-07 4.84e-08 | 3.20e-01 8.70e-08 3.36e-08 | 3.6e-12 8.0e-01 co-a 9.50e-01
13 -5.6923e+00 -5.6923e+00 | 1.57e-07 5.84e-08 7.69e-09 | 3.02e-01 1.46e-08 4.76e-09 | 1.8e-10 8.8e-01 co-a 8.50e-01
14 -5.6923e+00 -5.6923e+00 | 1.06e-07 4.56e-08 5.76e-09 | 2.83e-01 1.20e-08 3.22e-09 | 1.9e-09 3.0e-01 co-a 3.00e-01
15 -5.6923e+00 -5.6923e+00 | 5.35e-08 2.28e-08 2.87e-09 | 2.84e-01 5.68e-09 1.62e-09 | 1.3e-10 7.7e-02 co-a 5.00e-01
16 -5.6923e+00 -5.6923e+00 | 5.30e-08 2.26e-08 2.84e-09 | 2.84e-01 5.66e-09 1.60e-09 | 5.3e-11 8.7e-04 co-a 1.00e-02
17 -5.6923e+00 -5.6923e+00 | 2.65e-08 1.13e-08 1.42e-09 | 2.84e-01 2.83e-09 8.02e-10 | 1.8e-12 4.5e-04 co-a 5.00e-01
optimal solution found; terminating
status is Optimal after 17 iterations and 0.005 seconds
solution_summary(; result = 1, verbose = false)
├ solver_name : Dual model with Hypatia attached
├ Termination
│ ├ termination_status : OPTIMAL
│ ├ result_count : 1
│ └ raw_status : Optimal
├ Solution (result = 1)
│ ├ primal_status : FEASIBLE_POINT
│ ├ dual_status : FEASIBLE_POINT
│ ├ objective_value : -5.69231e+00
│ └ dual_objective_value : -5.69231e+00
└ Work counters
├ solve_time (sec) : 5.62286e-03
└ barrier_iterations : 17The third level improves it even further
model6 = solve(6)
Hypatia v0.11.0
Floating-point type: Float64.
Problem with 55 variables, 0 equality constraints and 9 cones:
55-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
10-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
iter p_obj d_obj | abs_gap x_feas z_feas | tau kap mu | dir_res prox step alpha
0 -8.0826e-01 -1.1348e+01 | 8.40e+01 2.41e+00 3.82e-01 | 1.00e+00 1.00e+00 1.00e+00 |
1 -8.9687e-01 -6.2113e+00 | 3.36e+01 1.26e+00 2.00e-01 | 7.66e-01 5.44e-01 4.00e-01 | 3.6e-15 5.6e-01 co-a 6.00e-01
2 -1.0747e+00 -2.6466e+00 | 9.89e+00 3.59e-01 5.70e-02 | 8.05e-01 1.20e-01 1.18e-01 | 1.8e-15 7.8e-01 co-a 7.00e-01
3 -1.6816e+00 -2.3358e+00 | 3.73e+00 1.55e-01 2.46e-02 | 7.47e-01 6.54e-02 4.44e-02 | 3.5e-15 6.9e-01 co-a 6.00e-01
4 -2.2888e+00 -2.5987e+00 | 1.42e+00 7.52e-02 1.20e-02 | 6.14e-01 3.13e-02 1.69e-02 | 5.6e-15 7.1e-01 co-a 6.00e-01
5 -2.8879e+00 -3.0430e+00 | 5.41e-01 3.92e-02 6.24e-03 | 4.71e-01 1.56e-02 6.45e-03 | 2.4e-14 7.6e-01 co-a 6.00e-01
6 -3.1219e+00 -3.2416e+00 | 3.73e-01 3.01e-02 4.78e-03 | 4.30e-01 1.06e-02 4.44e-03 | 5.1e-14 4.2e-01 co-a 3.00e-01
7 -3.3948e+00 -3.4481e+00 | 1.48e-01 1.40e-02 2.22e-03 | 3.70e-01 5.11e-03 1.77e-03 | 4.0e-14 6.3e-01 co-a 6.00e-01
8 -3.6651e+00 -3.6910e+00 | 5.72e-02 7.45e-03 1.18e-03 | 2.78e-01 2.74e-03 6.82e-04 | 1.8e-13 8.8e-01 co-a 6.00e-01
9 -3.8410e+00 -3.8522e+00 | 2.25e-02 3.19e-03 5.07e-04 | 2.59e-01 1.07e-03 2.68e-04 | 3.1e-13 6.8e-01 co-a 6.00e-01
10 -3.9160e+00 -3.9219e+00 | 1.10e-02 1.73e-03 2.76e-04 | 2.39e-01 5.76e-04 1.31e-04 | 5.1e-13 6.9e-01 co-a 5.00e-01
11 -3.9356e+00 -3.9402e+00 | 7.51e-03 1.41e-03 2.25e-04 | 2.05e-01 4.53e-04 8.94e-05 | 2.1e-12 4.3e-01 co-a 3.00e-01
12 -3.9789e+00 -3.9809e+00 | 2.92e-03 8.24e-04 1.31e-04 | 1.41e-01 2.76e-04 3.48e-05 | 5.2e-12 7.7e-01 co-a 6.00e-01
13 -4.0231e+00 -4.0239e+00 | 1.14e-03 4.13e-04 6.56e-05 | 1.12e-01 1.30e-04 1.36e-05 | 5.1e-12 9.2e-01 co-a 6.00e-01
14 -4.0331e+00 -4.0337e+00 | 7.95e-04 2.98e-04 4.74e-05 | 1.09e-01 8.76e-05 9.46e-06 | 3.3e-12 5.8e-01 co-a 3.00e-01
15 -4.0480e+00 -4.0483e+00 | 3.93e-04 1.59e-04 2.53e-05 | 1.02e-01 4.68e-05 4.68e-06 | 2.0e-12 6.4e-01 co-a 5.00e-01
16 -4.0610e+00 -4.0611e+00 | 1.16e-04 5.09e-05 8.09e-06 | 9.56e-02 1.51e-05 1.38e-06 | 2.8e-12 8.7e-01 co-a 7.00e-01
17 -4.0671e+00 -4.0671e+00 | 2.20e-05 1.09e-05 1.73e-06 | 8.93e-02 3.26e-06 2.62e-07 | 1.0e-11 9.4e-01 co-a 8.00e-01
18 -4.0680e+00 -4.0680e+00 | 6.62e-06 3.28e-06 5.21e-07 | 8.91e-02 8.93e-07 7.88e-08 | 1.5e-11 7.2e-01 co-a 7.00e-01
19 -4.0684e+00 -4.0684e+00 | 9.86e-07 4.96e-07 7.89e-08 | 8.83e-02 1.34e-07 1.17e-08 | 3.0e-11 8.7e-01 co-a 8.50e-01
20 -4.0685e+00 -4.0685e+00 | 9.80e-08 4.99e-08 7.94e-09 | 8.77e-02 1.32e-08 1.17e-09 | 5.1e-11 3.8e-01 co-a 9.00e-01
21 -4.0685e+00 -4.0685e+00 | 4.89e-08 2.50e-08 3.97e-09 | 8.77e-02 6.65e-09 5.82e-10 | 6.5e-11 2.1e-01 co-a 5.00e-01
22 -4.0685e+00 -4.0685e+00 | 4.87e-08 2.48e-08 3.95e-09 | 8.77e-02 6.60e-09 5.79e-10 | 1.4e-11 1.1e-02 co-a 5.00e-03
23 -4.0685e+00 -4.0685e+00 | 3.41e-08 1.74e-08 2.77e-09 | 8.77e-02 4.62e-09 4.05e-10 | 1.3e-12 1.9e-03 co-a 3.00e-01
24 -4.0685e+00 -4.0685e+00 | 3.24e-08 1.65e-08 2.63e-09 | 8.77e-02 4.39e-09 3.85e-10 | 4.3e-12 1.2e-04 co-a 5.00e-02
25 -4.0685e+00 -4.0685e+00 | 2.91e-08 1.49e-08 2.36e-09 | 8.77e-02 3.95e-09 3.47e-10 | 1.5e-12 2.4e-05 co-a 1.00e-01
optimal solution found; terminating
status is Optimal after 25 iterations and 0.434 seconds
solution_summary(; result = 1, verbose = false)
├ solver_name : Dual model with Hypatia attached
├ Termination
│ ├ termination_status : OPTIMAL
│ ├ result_count : 1
│ └ raw_status : Optimal
├ Solution (result = 1)
│ ├ primal_status : FEASIBLE_POINT
│ ├ dual_status : FEASIBLE_POINT
│ ├ objective_value : -4.06848e+00
│ └ dual_objective_value : -4.06848e+00
└ Work counters
├ solve_time (sec) : 4.34957e-01
└ barrier_iterations : 25The fourth level finds the optimal objective value as lower bound.
model8 = solve(8)
Hypatia v0.11.0
Floating-point type: Float64.
Problem with 119 variables, 0 equality constraints and 9 cones:
210-dimensional real positive semidefinite cone.
210-dimensional real positive semidefinite cone.
210-dimensional real positive semidefinite cone.
55-dimensional real positive semidefinite cone.
210-dimensional real positive semidefinite cone.
210-dimensional real positive semidefinite cone.
210-dimensional real positive semidefinite cone.
210-dimensional real positive semidefinite cone.
210-dimensional real positive semidefinite cone.
iter p_obj d_obj | abs_gap x_feas z_feas | tau kap mu | dir_res prox step alpha
0 -7.3181e-01 -1.1348e+01 | 1.70e+02 2.41e+00 3.97e-01 | 1.00e+00 1.00e+00 1.00e+00 |
1 -7.5788e-01 -7.1300e+00 | 8.50e+01 1.48e+00 2.44e-01 | 8.14e-01 6.24e-01 5.00e-01 | 1.8e-15 4.1e-01 co-a 5.00e-01
2 -8.5054e-01 -3.2871e+00 | 3.38e+01 5.50e-01 9.08e-02 | 8.75e-01 1.91e-01 1.99e-01 | 1.3e-15 5.9e-01 co-a 6.00e-01
3 -1.1830e+00 -2.0914e+00 | 1.32e+01 2.06e-01 3.41e-02 | 9.33e-01 8.21e-02 7.79e-02 | 4.4e-15 7.4e-01 co-a 6.00e-01
4 -1.6707e+00 -2.0630e+00 | 5.14e+00 9.07e-02 1.50e-02 | 8.48e-01 3.90e-02 3.02e-02 | 5.8e-15 7.2e-01 co-a 6.00e-01
5 -2.0431e+00 -2.2701e+00 | 2.50e+00 5.32e-02 8.79e-03 | 7.23e-01 2.17e-02 1.47e-02 | 4.7e-14 7.3e-01 co-a 5.00e-01
6 -2.3879e+00 -2.5210e+00 | 1.22e+00 3.19e-02 5.27e-03 | 6.03e-01 1.27e-02 7.21e-03 | 6.1e-14 8.9e-01 co-a 5.00e-01
7 -2.5890e+00 -2.6928e+00 | 8.47e-01 2.52e-02 4.15e-03 | 5.35e-01 9.51e-03 4.99e-03 | 1.2e-13 4.9e-01 co-a 3.00e-01
8 -2.8991e+00 -2.9570e+00 | 4.21e-01 1.44e-02 2.38e-03 | 4.68e-01 5.42e-03 2.48e-03 | 1.1e-13 9.4e-01 co-a 5.00e-01
9 -3.1127e+00 -3.1426e+00 | 2.08e-01 7.48e-03 1.24e-03 | 4.50e-01 2.79e-03 1.23e-03 | 7.1e-13 6.9e-01 co-a 5.00e-01
10 -3.1913e+00 -3.2142e+00 | 1.44e-01 5.84e-03 9.65e-04 | 4.03e-01 2.15e-03 8.48e-04 | 1.4e-12 4.7e-01 co-a 3.00e-01
11 -3.3243e+00 -3.3376e+00 | 7.13e-02 3.62e-03 5.98e-04 | 3.25e-01 1.36e-03 4.19e-04 | 1.5e-12 9.1e-01 co-a 5.00e-01
12 -3.3965e+00 -3.4070e+00 | 4.92e-02 2.99e-03 4.93e-04 | 2.76e-01 1.07e-03 2.89e-04 | 1.4e-11 5.7e-01 co-a 3.00e-01
13 -3.5370e+00 -3.5432e+00 | 2.42e-02 2.01e-03 3.32e-04 | 2.05e-01 7.32e-04 1.43e-04 | 3.0e-12 7.8e-01 co-a 5.00e-01
14 -3.7091e+00 -3.7124e+00 | 1.18e-02 1.22e-03 2.01e-04 | 1.69e-01 4.33e-04 6.97e-05 | 2.3e-11 9.6e-01 co-a 5.00e-01
15 -3.9099e+00 -3.9110e+00 | 3.48e-03 3.95e-04 6.52e-05 | 1.57e-01 1.30e-04 2.05e-05 | 6.9e-12 7.7e-01 co-a 7.00e-01
16 -3.9821e+00 -3.9824e+00 | 7.00e-04 7.67e-05 1.27e-05 | 1.61e-01 2.37e-05 4.11e-06 | 1.4e-11 9.1e-01 co-a 8.00e-01
17 -3.9947e+00 -3.9948e+00 | 2.08e-04 2.27e-05 3.75e-06 | 1.64e-01 7.43e-06 1.22e-06 | 2.8e-11 8.3e-01 co-a 7.00e-01
18 -3.9995e+00 -3.9995e+00 | 2.07e-05 2.25e-06 3.71e-07 | 1.65e-01 6.98e-07 1.22e-07 | 2.1e-11 9.2e-01 co-a 9.00e-01
19 -3.9999e+00 -3.9999e+00 | 3.08e-06 3.39e-07 5.60e-08 | 1.64e-01 1.05e-07 1.81e-08 | 4.8e-10 6.6e-01 co-a 8.50e-01
20 -4.0000e+00 -4.0000e+00 | 1.22e-06 1.37e-07 2.25e-08 | 1.63e-01 4.44e-08 7.17e-09 | 4.8e-09 9.4e-01 co-a 6.00e-01
21 -4.0000e+00 -4.0000e+00 | 3.65e-07 4.14e-08 6.75e-09 | 1.63e-01 1.31e-08 2.14e-09 | 5.8e-10 8.9e-01 co-a 7.00e-01
22 -4.0000e+00 -4.0000e+00 | 3.63e-07 4.13e-08 6.72e-09 | 1.63e-01 1.31e-08 2.13e-09 | 2.4e-10 2.9e-02 co-a 5.00e-03
23 -4.0000e+00 -4.0000e+00 | 1.09e-07 1.24e-08 2.01e-09 | 1.63e-01 3.92e-09 6.40e-10 | 5.2e-12 1.9e-02 co-a 7.00e-01
optimal solution found; terminating
status is Optimal after 23 iterations and 0.1 seconds
solution_summary(; result = 1, verbose = false)
├ solver_name : Dual model with Hypatia attached
├ Termination
│ ├ termination_status : OPTIMAL
│ ├ result_count : 1
│ └ raw_status : Optimal
├ Solution (result = 1)
│ ├ primal_status : FEASIBLE_POINT
│ ├ dual_status : FEASIBLE_POINT
│ ├ objective_value : -4.00000e+00
│ └ dual_objective_value : -4.00000e+00
└ Work counters
├ solve_time (sec) : 1.00153e-01
└ barrier_iterations : 23This page was generated using Literate.jl.