Tutorial: polynomial minimization on a box

For sense="min", res.bound is a lower bound on the minimum. As an example take the Styblinski–Tang function in two variables,

\[f(x)=\tfrac12\sum_{i=1}^2\big(x_i^4-16x_i^2+5x_i\big),\qquad x\in[-5,5]^2 ,\]

a classic non-convex test function whose global minimum is \(-78.3323\) at \(x_i\approx-2.9035\).

import moment_sos as po

x = po.variables(2)
f = sum((xi**4 - 16*xi**2 + 5*xi) / 2 for xi in x)
problem = po.Problem(f, sense="min", box=(-5, 5))

res = po.solve(problem, order=2, iters_per_stage=2000)
pt, value = res.round()
print("lower bound:", res.bound, " best point:", pt, value)
assert res.bound <= value + 1e-6                  # lower bound below the feasible value
assert abs(value - (-78.33233)) < 1e-3            # the recovered point is the global minimizer
assert value - res.bound < 0.05                   # and the bound is tight to about 0.02

Three things to note.

  1. The degree sets the minimum order. The objective has degree 4, so order=2 is the smallest admissible order (po.min_order(problem) returns 2). A degree-\(d\) polynomial needs \(2r\ge d\).

  2. The box matters. The certificate uses the box to bound \(\|v(x)\|^2\), and the bound degrades as the box grows relative to the region of interest. Use the tightest box you can justify.

  3. A tight bound plus a feasible point is a certificate of near-optimality: here the minimum lies in \([\text{bound},\,\text{value}]\), an interval of width about \(0.02\).

A problem where order 2 is not enough

Raising the order is the only way to tighten the relaxation; when it does not help the problem may need a higher order than is affordable. Polynomial problems with no structure grow quickly: the moment block has \(\binom{n+r}{r}\) rows.

import math

for n in (2, 5, 10):
    print(n, [math.comb(n + r, r) for r in (1, 2, 3)])

Exploit structure when you can (Tutorial: correlative sparsity on a chain).