Рассмотрим класс алгоритмов, поиск глобального минимума по которым сводится к следующей последовательности действий:

1) проводятся испытания в точках x_i, i = 1, 2,…, N, расположенных определенным образом на интервале [a, b];

2) по полученным значениям (x_i, Q (x_i)), i = 1,2,…, N, строится математическая модель, аппроксимирующая функцию Q (х) на интервале [a, b];

3) оценивается точность приближения построенной модели к функции Q (х);

4) если точность аппроксимации недостаточна, то проводятся дополнительные испытания и процедура поиска повторяется с п. 2; в противном случае при помощи полученной математической модели принимается решение о расположении на интервале [а, b] точки глобального минимума х* функции Q (х).

Будем считать, что минимизируемые кривые Q (х) являются непрерывными функциями, удовлетворяющими условию (4.1), в котором количественное значение константы Липшица L в общем случае может быть неизвестно.

Согласно теореме Вейерштрасса, любая непрерывная функция Q (х) может быть аппроксимирована равномерно сходящейся последовательностью алгебраических полиномов P_N(х)=∑a_kx^k, т. е. для
любого числа ε > 0 найдется такой полином P_N (х), что для всех х∈[a, b] будет справедливо неравенство

|Q(x) — P_N(х)| ≤ ε.

Однако степень аппроксимирующего полинома P_N (х) при этом является произвольной и может оказаться очень высокой. В связи с этим возникает экстремальная задача определения при фиксированной степени N такого полинома P_N (x), который наилучшим образом аппроксимирует функцию Q (х):

min max |Q(x)—P_N(х)|.

Для непрерывных функций Q (х) оптимальное решение задачи (4.25) существует и является единственным многочленом степени не выше N, который в аналитическом виде может быть представлен при помощи интерполяционного полинома Лагранжа

P_N(x) = ∑Q(x_i)ω_N+1 (x)/[(x-x_i)ω_N+1(x_i)], (4.26)

Точность приближения функции Q (x) полиномом (4.26) будет тем выше, чем меньше многочлен ω_N+1(х) будет отклоняться от нуля. Поэтому точки испытаний x_i, i = 1, 2,…, N, которые в (4.26) являются узлами интерполяции, необходимо выбирать таким образом, чтобы при увеличении числа испытаний N, С одной стороны, обеспечить равномерную сходимость последовательности полиномов P_N (х) к функции Q (х), а с другой — наибольшую скорость уменьшения многочлена ω_N+1(х). Для рассматриваемого класса минимизируемых функций Q (х) сформулированные требования выполняются, если в качестве точек испытаний x_i выбирать нули многочлена Чебыщева T_N(х) = cos (N arccos (x)), которые являются вещественными, простыми и лежат в интервале [-1, 1]:

x_i = cos[(2i-1)/2N — π], i=1,2,…,V, (4.27)

Использование в качестве математической модели интерполяционного полинома Лагранжа (4.26), а в качестве точек испытаний — нулей многочлена Чебышева (4.27) приводит к алгоритму F¹³, реализующему пассивную стратегию поиска точки глобального минимума х* произвольной кривой Q (х):

1. Определяется расположение точек испытаний на интервале [а, b]

x_i = |(b — а)ξ_i + (а + b)|/2, i = 1, 2, …, N + 1, где
ξ_i = cos[(2i-1)/2(N+1) — π]

2. По информации о проведенных испытаниях (x_i, Q (x_i)), i = 1, 2, …, N + 1, строится математическая модель функции Q (х) в виде интерполяционного полинома Лагранжа.

3. Находится первая производная от полинома Р_N (х) и путем решения уравнения:

Р_N(x) = 0

(например, с помощью метода Мюллера вычисляются корни алгебраического полинома (N — 1)-й степени, среди которых выбирается значение x*, удовлетворяющее условию

Р_N(х) = min Р_N(х).

4. В качестве апостериорного интервала неопределенности [a_N, b_N], в котором предполагается наличие точки минимума х*, выбирается отрезок между точками испытаний x_ш и x_i+1 удовлетворяющих условию:

x_i ≤ x* ≤ х_i+1.

При малом числе испытаний алгоритм F¹³ может не локализовать точку минимума х* (т. е. интервал [x_i, x_i+1] не будет содержать точку x*). Однако в силу равномерной сходимости полиномов Р_N(х) к функции Q(x) с ростом числа испытаний N вероятность потери точки глобального минимума х* будет убывать. Недостатком рассмотренного алгоритма является то, что при изменении числа проводимых испытаний хотя бы на одно (так как многочлены Чебышева T_N (х) и T_N+1 (х) не имеют общих корней), для сохранения свойства равномерной сходимости полиномов P_N(х) к функции Q (х), необходимо узлы интерполяции {x_i} вычислять заново, что приводит к потере всей информации о предыдущих испытаниях. В связи с этим рассмотрим последовательную стратегию поиска точки глобального минимума x* с помощью интерполяционных полиномов Лагранжа (4.26), в которых система узлов интерполяции {x_i} обладает следующими свойствами:
— при увеличении числа испытаний N новые узлы лишь добавляются между старыми узлами, которые сохраняются неизменными;
— построенные по этим узлам интерполяционные полиномы P_N(х) обладают свойством равномерной сходимости к функции Q (х).

Для удовлетворения сформулированных требований, предъявляемых к узлам интерполяции {х_i}, необходимо, чтобы они вычислялись о помощью полиномов, корни которых не меняются при изменении числа N, но в то же время эти полиномы должны обладать свойствами многочленов, наименее отклоняющихся от нуля на интервале [-1,1].

Комментарии запрещены.