Ищем многочлены Чебышова

Напомним, что алгоритмы SOS-оптимизации умеют решать следующую задачу.

Вход: многочлен p(x1,,xn,c1,,cm) линейный относительно c1,,cm и линейная функция (c1,,cm)

Выход: Максимальное значение (c1,,cm) среди наборов чисел c1,,cm, для которых p(x1,,xn,c1,,cm) - SOS относительно x1,,xn.

Пример: Чему равно наибольшее значение a, при котором x2+ax+4 является суммой квадратов?

In [1]:
using SumOfSquares
using DynamicPolynomials
using Mosek
using MosekTools
using SemialgebraicSets
In [2]:
opt = optimizer_with_attributes(Mosek.Optimizer, "QUIET" => true);
model = SOSModel(opt)

@polyvar z
S = @set -1 <= z && z <= 1 # живем на [-1, 1]

d = 10
@variable(model, a[0:d])
p = sum([a[i] * z^i for i in 0:d])
Out[2]:
(a[10])z10+(a[9])z9+(a[8])z8+(a[7])z7+(a[6])z6+(a[5])z5+(a[4])z4+(a[3])z3+(a[2])z2+(a[1])z+(a[0])
In [3]:
@objective(model, Max, a[d]) # функция L, которую оптимизируем
@constraint(model, p <= 1, domain = S)
@constraint(model, p >= -1, domain = S)
Out[3]:
(a[10])z10+(a[9])z9+(a[8])z8+(a[7])z7+(a[6])z6+(a[5])z5+(a[4])z4+(a[3])z3+(a[2])z2+(a[1])z+(a[0]+1) is SOS
In [4]:
optimize!(model)
In [5]:
value(p)
Out[5]:
511.9999962549675z10+3.294303089955077e8z91279.999990250578z86.894012698563223e8z7+1119.9999911124535z6+4.701037338930788e8z5399.9999967084261z41.1565773067861164e8z3+49.99999957877693z2+7.358655835241071e10z0.9999999910424843
In [6]:
round(value(p), digits = 3)
Out[6]:
512.0z101280.0z8+1120.0z6400.0z4+50.0z21.0

Эксперимент: Наименьшее уклонение на двух отрезках сразу

In [7]:
opt = optimizer_with_attributes(Mosek.Optimizer, "QUIET" => true);
model = SOSModel(opt)

@polyvar z
S = @set (z - 2) * (z - 1) * (z + 1) * (z + 2) <= 0 # NEW
# живем [-2, -1] в [1, 2]

d = 4
@variable(model, a[0:d])
p = sum([a[i] * z^i for i in 0:d])

@objective(model, Max, a[d])
@constraint(model, p <= 1, domain = S)
@constraint(model, p >= -1, domain = S)

optimize!(model)
In [8]:
value(p)
Out[8]:
0.8888888896752403z44.444444446977403z2+4.5555555564390575
In [9]:
round(value(p), digits = 5)
Out[9]:
0.88889z44.44444z2+4.55556

Видно, что здесь приятные рациональные числа! Для других значений d всё менее очевидно - надо раскладывать в цепные дроби и подбирать. Если есть интерес - смело пробуйте

In [ ]: