# Minimization of a univariate polynomial

```
using DynamicPolynomials
using SumOfSquares
import CSDP
```

Consider the problem of finding both the minimum value of `p = x^4 - 4x^3 - 2x^2 + 12x + 3`

as well as its minimizers.

We can use SumOfSquares.jl to find such these values as follows. We first define the polynomial using DynamicPolynomials.

```
@polyvar x
p = x^4 - 4x^3 - 2x^2 + 12x + 3
```

\[ 3 + 12x - 2x^{2} - 4x^{3} + x^{4} \]

Secondly, we create a Sum-of-Squares program searching for the maximal lower bound `σ`

of the polynomial.

```
model = SOSModel(CSDP.Optimizer)
@variable(model, σ)
@constraint(model, cref, p >= σ)
@objective(model, Max, σ)
```

$ σ $

Thirdly, solve the program and find `σ = -6`

as lower bound:

```
optimize!(model)
solution_summary(model)
```

```
* Solver : CSDP
* Status
Result count : 1
Termination status : OPTIMAL
Message from the solver:
"Problem solved to optimality."
* Candidate 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) : 1.45411e-03
```

We can look at the certificate that `σ = -6`

is a lower bound:

`sos_dec = sos_decomposition(cref, 1e-4)`

`(-3.0000000049643614 - 1.999999998797403*x + 0.9999999995176428*x^2)^2`

Indeed, `p + 6 = (x^2 - 2x - 3)^2`

so `p ≥ -6`

.

## Extraction of minimizers

We can now find the minimizers from the moment matrix:

```
ν = moment_matrix(cref)
ν.Q
```

```
3×3 SymMatrix{Float64}:
1.0 0.0669168 3.13383
0.0669168 3.13383 6.46842
3.13383 6.46842 22.3383
```

This matrix is the convex combination of the moment matrices corresponding to two atomic measures at `-1`

and `3`

which allows us to conclude that `-1`

and `3`

are global minimizers.

```
η = atomic_measure(ν, 1e-4)
minimizers = [η.atoms[1].center; η.atoms[2].center]
```

```
2-element Vector{Float64}:
-1.0000001975826245
2.9999999542477056
```

Below are more details on what we mean by convex combination. The moment matrix of the atomic measure at the first minimizer is:

```
η1 = moment_matrix(dirac(monomials(x, 0:4), x => round(minimizers[1])), ν.basis.monomials)
η1.Q
```

```
3×3 SymMatrix{Float64}:
1.0 -1.0 1.0
-1.0 1.0 -1.0
1.0 -1.0 1.0
```

The moment matrix of the atomic measure at the second minimizer is:

```
η2 = moment_matrix(dirac(monomials(x, 0:4), x => round(minimizers[2])), ν.basis.monomials)
η2.Q
```

```
3×3 SymMatrix{Float64}:
1.0 3.0 9.0
3.0 9.0 27.0
9.0 27.0 81.0
```

And the moment matrix is the convex combination of both:

`Q12 = η1.Q * η.atoms[1].weight + η2.Q * η.atoms[2].weight`

```
3×3 Matrix{Float64}:
1.0 0.0669169 3.13383
0.0669169 3.13383 6.46842
3.13383 6.46842 22.3383
```

Another way to see this (by linearity of the expectation) is that `ν`

is the moment matrix of the convex combination of the two atomic measures.

## Changing the polynomial basis

The monomial basis used by default can leave a problem quite ill-conditioned for the solver. Let's try to use another basis instead:

```
model = SOSModel(CSDP.Optimizer)
@variable(model, σ)
@constraint(model, cheby_cref, p >= σ, basis = ChebyshevBasisFirstKind)
@objective(model, Max, σ)
optimize!(model)
solution_summary(model)
```

```
* Solver : CSDP
* Status
Result count : 1
Termination status : OPTIMAL
Message from the solver:
"Problem solved to optimality."
* Candidate 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.24209e-03
```

Although the gram matrix in the monomial basis:

```
g = gram_matrix(cref)
@show g.basis
g.Q
```

```
3×3 SymMatrix{Float64}:
9.0 6.0 -3.0
6.0 4.0 -2.0
-3.0 -2.0 1.0
```

looks different from the gram matrix in the Chebyshev basis:

```
cheby_g = gram_matrix(cheby_cref)
@show cheby_g.basis
cheby_g.Q
```

```
3×3 SymMatrix{Float64}:
6.25 5.0 -1.25
5.0 4.0 -1.0
-1.25 -1.0 0.25
```

they both yields the same Sum-of-Squares decomposition:

`cheby_sos_dec = sos_decomposition(cheby_cref, 1e-4)`

`(-3.000000002974674 - 1.9999999995036628*x + 0.9999999997868867*x^2)^2`

The gram matrix in the Chebyshev basis can be understood as follows. To express the polynomial $-x^2 + 2x + 3$ in the Chebyshev basis, we start by substituting $x$ into $\cos(\theta)$ to obtain $-\cos(\theta)^2 + 2\cos(\theta) + 3$. We now express it as a combination of $\cos(n\theta)$ for $n = 0, 1, 2$: $-(2\cos(\theta) - 1) /2 + 2 \cos(\theta) + 5/2.$ Therefore, the coefficients in the Chebyshev basis is:

`cheby_coefs = [5/2, 2, -1/2]`

```
3-element Vector{Float64}:
2.5
2.0
-0.5
```

We can indeed observe that we obtain the same matrix as `cheby_g.Q`

`cheby_coefs * cheby_coefs'`

```
3×3 Matrix{Float64}:
6.25 5.0 -1.25
5.0 4.0 -1.0
-1.25 -1.0 0.25
```

*This page was generated using Literate.jl.*