Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Вход

Исходные данные a, b, ε1, ε2, f (x)

= b −a

31

1.2.3.3. Метод парабол (метод полиномиальной аппроксимации)

Идея метода весьма проста: если на отрезке [a, b] , внутри

которого лежит точка минимума x , функция f (x) достаточно хорошо аппроксимируется многочленом второй степени, то за

приближенное значение x целесообразно взять точку минимума этого многочлена. В случае, когда функция гладкая и

унимодальная, можно предполагать, что в окрестности точки x она весьма близка к параболе. Ввиду этого метод парабол целесообразно применять после того, как найден отрезок

многочлен второго порядка, который проходит через три данные точки (рис. 1.11).

Рис. 1.11. Графическое представление функции f (x) = α0 + α1x + α2x2

32

Контрольные задачи

Задача 1. Методом удвоения шага найти отрезок, содержащий точку минимума функции f (x) = (x −5)2 . В качестве начальной точки взять: 1) x0 = 3 ; 2) x0 = 7 . Составить блок-схему алгоритма.

Задача 2. Методом золотого сечения найти точку минимума функции

Фибоначчи, Ньютона и методом касательных с погрешностью менее 5 %. Сравнить полученные результаты.

1.3. Минимизация функций без ограничений (безусловная минимизация)

Перейдем к изучению методов нахождения минимума функции многих переменных f (x1 , …, xn ) по всему пространству R n , т.е. при условии, что при поиске экстремума каждая из переменных xi может принимать значения от –∞ до +∞. Допустим, что f (x)

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

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

Все методы безусловной минимизации сводятся к нахождению последовательности точек x0 , x1 , …, x n , значения функции в которых убывают:

34

релаксационными методами).

При получении таких последовательностей точек в задачах с ограничениями, прежде всего, необходимо выбрать начальную точку x0 , удовлетворяющую всем ограничениям.

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

не слишком далеко от точки минимума.

После того, как какая-то точка выбрана, необходимо:

1)выбрать направление, вдоль которого предполагается расположить следующую точку;

2)решить, какой величины шаг должен быть сделан в выбранном направлении.

При любом методе спуска последовательность точек выглядит так:

где единичный вектор Sk задает направление, а λk – величину шага. Изменяя процедуру выбора Sk и λk, можно получать различные методы спуска.

Для задач без ограничений любое направление является возможным, однако не все направления приемлемы. Приемлемым называется такое направление Sk, для которого выполняется условие

Действительно, для достаточно малых λk можно написать разложение функции в ряд Тейлора

если этот член < 0, то f ( xk +λSk )< f ( xk )

Все методы спуска можно разбить на две группы:

1) прямые методы, или методы нулевого порядка – методы,

использующие только значения функций;

35