Оптимизация с использованием аппроксимирующих полиномов

В методах прямого поиска мы не имели никакой информации о минимизируемой функции за исключением ее значений в выбранных нами точках и предположения, что она непрерывна и является унимодальной функцией на рассматриваемом отрезке. Если функцию в некоторой окрестности точки ее минимума можно достаточно точно заменить (аппроксимировать) многочленом, то для ее минимизации целесообразно использовать так называемые методы полиномиальной аппроксимации. Используется несколько значений функции в определенных точках для аппроксимации функции обычным полиномом, по крайней мере в небольшой области. Затем положение минимума функции аппроксимируется положением минимума полинома, поскольку последний вычислить проще. При этом характер поведения оптимизируемой функции учитывается при выборе вида полинома и при его построении.

Метод линейной интерполяции (метод секущих или regula falsi)

Хорошо известный метод секущих отыскания нуля функции первоначально назывался методом regula falsi или regula falsorum. Этот метод правильно предсказывает положение нуля функции, если она зависит линейно от своего аргумента.

Метод секущих предлагает заменить вторую производную в ньютоновской формуле ее линейной аппроксимацией.

Тем самым очередное приближение к стационарной точке x^* задается формулой вида.

Легко видеть, что — точка пересечения с осью абсцисс секущей прямой, проходящей через точки x_k и.

В отличие от метода Ньютона метод секущих гарантирует сходимость точек {x_k} к стационарной точке x^*, однако сходимость метода достигается ценой потери быстродействия. Как правило, метод дихотомии оказывается эффективнее метода секущих, хотя последний и получен из более быстродействующей схемы.

Начальный этап. Пусть методом Свенна получен интервал неопределенности [a₁, b₁], границы которого удовлетворяют неравенству. Задать — погрешность вычисления минимума и принять k = 1.

Основной этап.

Шаг 1. Найти очередное приближение x_{k + 1} к минимуму x^* и проверить условие окончания поиска:

если то остановиться.

Шаг 2. Уменьшить интервал поиска минимума:

если в противном случае принять.

положить и перейти к шагу 1.

Метод работает надежно только в случае, если функция почти линейна или хотя бы строго выпукла. Кроме того, стартовые точки должны быть выбраны в окрестности точки минимума. Иначе процедура может выдать в качестве ответа точку максимума, так как при движении к нему производная тоже будет уменьшаться.

Модификации метода Ньютона обладают только локальной сходимостью, т. е. сходятся, если начальная точка выбрана в некоторой окрестности точки минимума функции. Если же начальная точка расположена слишком далеко от точки минимума, то подобный метод может расходиться или «зацикливаться». В некоторых случаях целесообразно сочетать различные модификации метода Ньютона, чередуя их применение в зависимости от номера шага.

Рассмотрим метод квадратичной аппроксимации минимизируемой функции, в котором график этой функции приближенно заменяют параболой, проходящей через три известные точки, i = 1,2,3, где .

Метод квадратичной интерполяции.

Итак, найти с точностью .

Выбираем .

Через точки проводим параболу, то есть строим интерполяционный многочлен 2-й степени:

Находим вершину параболы из условия ,.

.

Если, то необходимо выяснить или нет.

Если, то по трем точкам строится следующая парабола.

Если, то следующая парабола строится по точкам:

В случае, если соответствующим образом подбирается очередная тройка чисел, через которые проводится парабола.

Каждая новая вершина параболы принимается за очередное приближенное решение.

На рисунке представлена блок-схема метода парабол, в которой итерационный процесс заканчивается как только абсциссы вершины последующей и предыдущей параболы разнятся менее, чем на .