Методы нулевого порядка Метод конфигураций Хука-Дживса.

Стратегия поиска. Метод представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу. Цель исследующего поиска – выявление локального поведения целевой функции и определение направления ее убывания. Эта информация используется при поиске по образцу вдоль направления убывания целевой функции.

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

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

Обозначим через – координатные направления:

Отметим, что при поиске по направлению меняется только переменная , а остальные переменные остаются зафиксированными.

Алгоритм метода.

Шаг 1. Задать начальную точку , число - для остановки алгоритма, начальные значения приращений по координатным приращениям , ускоряющий множитель

Шаг 2. Провести исследующий поиск по выбранному координатному направлению:

Шаг 3. Проверить условия:

а) если i < n, то положить i= i+1 и перейти к шагу 2. (продолжить исследующий поиск по оставшимся направлениям);

б) если i = n, проверить успешность исследующего поиска:

- если , перейти к шагу 4.

- если , перейти к шагу 5.

Шаг 4. Провести поиск по образцу.

В точке провести исследующий поиск, в результате которого получается точка

Если , то точка становится точкой нового базиса, а - точкой старого базиса. Перейти к шагу 5. .

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

Шаг 5. Проверить условие окончания счета:

а) если все , то поиск закончить ;

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

Пример.

Найти минимум функции

Решение.

Зададим начальную точку ; число . Положим i=1, k=0.

, то шаг неудачен. , то шаг удачен.

Поскольку i=1 <2=n, то положим i=2 и перейдем к шагу 2.

, то шаг неудачен.

,то шаг удачен

Поскольку i=2=n и , то перейдем к шагу 4.

Проведем поиск по образцу из точки Положим i=1, k= k+1=1. и перейдем к шагу 2.

Выполняем исследующий поиск из точки . , то шаг неудачен. Т.к. , то шаг удачен.

Поскольку i=1 <2=n, то положим i= i+1=2 и перейдем к шагу 2.

, то шаг неудачен. , то шаг неудачен.

, то поиск по образцу на шаге 40 прошел успешно.

Точка становится новым базисом, а точка становится старым базисом. Выполним поиск по образцу из нового базиса. Перейдем к шагу 4.

Положим i=1, k= k+1=2. и перейдем к шагу 2.

, то шаг удачен.

Поскольку i=1 <2=n, то положим i= i +1=2 и перейдем к шагу 2.

, то шаг удачен.

Т.к. i=2=n и f(4,5)=5 > f(5,5)=1, то поиск по образцу на прошел неудачно. Переходим к шагу 5.

, то следует уменьшить шаг. Положим , за базис возьмем точку (5,5) и повторим цикл вычислений с новым базисом и новыми значениями шагов. Минимум достигается в точке

Метод деформируемого многогранника (метод Нелдера—Мида)

Стратегия поиска.Идея метода состоит в сравнении значений функции в (n+1)вершинах многогранника (симплекса) , i=1,…, n+1, k- номер итерации и перемещении в направлении оптимальной точки с помощью следующей итерационной процедуры. Точки многогранника на k+1 итерации совпадают с точками , за исключением худшей точки многогранника, т.е. той точки, в которой исходная функция принимает наибольшее значение. Точка заменяется на другую с помощью трех основных операций: отражения, растяжения, сжатия и редукции. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода. Построение последовательности многогранников заканчивается, когда значения функции в вершинах многогранника отличается от значения функции в центре тяжести многогранника не более, чем на заданную величину.

Важный вопрос – построение начального симплекса. Задается некото-рая базовая точка , а координаты остальных n вершин симплекса получаются следующим образом:

где , а a – масштабный множитель.

Например, если и остальные две вершины симплекса равны:

Начальный симплекс можно построить иначе: , где - единичный вектор.

Например, если

Алгоритм метода.

Начальный этап

Задать начальную точку и коэффициенты отражения , растяжения и сжатия . Сформировать начальный симплекс. Перейти к основному этапу.

Начальный этап

Шаг 1. Вычислить значение функции во всех точках многогранника и выбрать лучшую и худшую точки и . Вычислить центр тяжести многогранника за исключением худшей точки:

Здесь h – номер худшей точки.(для функции 2-х переменных точка - середина отрезка, соединяющего точки за исключением худшей).

Шаг 2. Проверить условие окончания счета:

а) если

то поиск закончить ;

б) иначе перейти к шагу 3.

Шаг 3. Выполнить операцию отражения худшей точки через центр тяжести:

Здесь – параметр отражения (рекомендуемое значение ).

Шаг 4. Построение нового многогранника. Для этого вычисляется значение функции в точке , которое сравнивается со значением функции в Лучшей точке :

а) если , то выполняется операция растяжения:

Здесь – параметр растяжения (рекомендуемое значение ).

Если , то меняем точку на , если же , то меняем точку на

б) если , то выполняется операция сжатия:

Здесь – параметр сжатия (рекомендуемое значение )

Если , то меняем худшую точку на , если же , то меняем точку на .

в) если , то выполняется операция редукции. В этом случае формируется новый многогранник, содержащий лучшую точку с уменьшенными вдвое сторонами:

Перейти к шагу 1.

Пример.

Найти минимум функции

Решение.

Т.к. n=2, то в качестве начального многогранника возьмем треугольник с вершинами . Положим

Таким образом,

Проверим окончание счета. Так как то процесс продолжается.

Выполним операцию отражения худшей точки через центр тяжести.

Имеем : .

Так как выполним растяжение:

Так как ,

то худшая вершина заменяется на вершину .

Итак новый многогранник содержит вершины: .

Переходим к шагу 1.

. Таким образом,

Так как , то процесс продолжается. и т.д.