4. Метод сплайнов 1-го порядка (нахождения точки глобального минимума)

Будем рассматривать задачу

, (1)

где – некоторые числа ( ).

Определение. Сплайном некоторой функции на называют некоторую непрерывную функцию, состоящую из кусков функций заданного класса и аппроксимирующую исходную функцию снизу.

Если в качестве кусков выбирается линейная функция, то сплайн представляет из себя некоторую ломаную и называется сплайном 1-го порядка.

Если в качестве кусков выбирается квадратичные функции (куски парабол), то говорят о сплайне 2-го порядка.

Метод состоит в следующем: пусть дана задача (1), задана – начальное приближение.

Предполагаем, что выполняется условие

(2)

, (то есть тангенс угла наклона касательной находится на ). Пусть одновременно с реализацией метода задана некоторая процедура поиска. (То есть по некоторому принципу на выбираются точки. Эти точки подставляются в целевую функцию и находится рекорд и рекордный план.)

1-ая итерация: по строится простейший сплайн

На рисунке сплайн ломаная 1-2-3. Простейший сплайн представляет из себя ломаную 1-2-3, причём угловой коэффициент [1,2]= , а [2,3]= . Так как выполняется неравенство (2), то аппроксимирует снизу функцию , (лежит не выше неё), затем решаем задачу и пусть – оптимальный план этой задачи. Затем производится анализ.

П

a

усть – рекордный план, тогда если , где 0 – малое (требуемая точность вычислений), тогда рекордный план принимается за -оптимальное.

В противном случае переходим ко 2-ой итерации: строим сплайн. Сначала по – простейший

Затем и решается задача , её решение принимается за .

Затем совершается анализ: если , то рекордный план принимается за приближённое решение, в противном случае 3-я итерация и так далее.

Опишем -ую итерацию: пусть построена точка и сплайн тогда строим простейший сплайн по

;

затем . Затем рассматривается задача и решение принимается за .

Анализ: если выполняется неравенство , то служит приближённым значением задачи, в противном случае приходим к -итерации.

Замечание. Обычно при реализации схемы перебора включаются в неё и перебираемые планы и они выбираются из окрестности этой точки.

Последовательность сходится к оптимальному плану: – оптимальный план задачи (1).

С ростом итераций сплайн всё точнее описывает целевую функцию в окрестности точки минимума.

Чем точнее подобрано в (2), тем быстрее сходится метод.

Замечание. Если в методе вместо линейных сплайнов использовать квадратичные (по определённым 3-м точкам строятся куски парабол с ветвями направленными вверх и вниз в зависимости от кривизны), то приходим к методу сплайнов 2-го порядка, которые точнее аппроксимируют функцию в окрестности оптимального плана. Этот метод быстрее сходится.

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

Определение. Функция называется унимодальной на [ ], если существует точка такая, что на функция монотонно убывает, а на монотонно возрастает.

- оптимальный план задачи (1).

В задаче (1) унимодальная функция имеет единственный оптимальный план и не имеет локальных минимумов. В частности, если в задаче (1)

(3) , то функция строго выпукла и является унимодальной. Если в задаче (1) функция не унимодальная, то в некоторых случаях [a,b] с помощью неравенства (3) её удаётся разбить на интервалы унимодальности, затем чтобы решить исходную задачу (1) достаточно на каждом таком отрезке решить задачу минимизации унимодальной функции и простым перебором найти оптимальный план.

Будем решать задачу (1), в которой - унимодальная функция.

Поставим цель: по заданному найти на [a,b] такую часть (длиною ) и чтобы . Эта задача называется задачей локализации точки минимума.

Если задача локализации решена, то в любую точку из (например, середину) принимают в качестве приближённого решения задачи (1).

Метод равномерного поиска

Выбираем некоторое и разбиваем исходный отрезок [ ] на частей точками …, где и поочерёдно начиная с вычисляем значение функции . В силу унимодальности будут выполняться неравенства . Тогда ясно, что

Если , то задача локализации решена. В противном случае выбираем и разбиваем его на некоторое количество частей и операцию поиска повторяем. В конце концов, задача (1) будет решена.

Замечание. Можно сразу подобрать таким образом, чтобы выполнялось , но это не рационально, так как количество точек перебора будет очень большим. Лучше на 1-ом этапе исходный отрезок разбить на количество частей , потом количество точек увеличить.