Методы безусловной оптимизации

В полученной точке  . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .

В полученной точке  . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку относительно центра тяжести точек и .

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

Искомая точка:

Для получения  более точного результата необходимо уменьшить размер симплекса.

Решение поставленной задачи симплекс методом представлено на рисунке 2.

 

Рисунок 2 – Решение задачи симплекс-методом

1.1.3 Метод Хука-Дживса

 

Процедура Хука-Дживса представляет собой комбинацию “исследующего” поиска с циклическим  изменением переменных и ускоряющего  поиска по найденному образцу. Исследующий  поиск ориентирован на выявление  характера локального поведения  целевой функции и определение  направления вдоль “оврагов”. Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по “оврагам”. 

Исследующий поиск:

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

Поиск по образцу:

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

xр(к + 1) = x(к) + [x(к) - x(к - 1)].

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

 

Шаг1. Задать:

1. Начальную  точку х(0);

2. Приращение  Di , i=1,2…,N;

3. Коэффициент  уменьшения шага a>1;

4. Параметр  окончания поиска e>0.

Шаг2. Произвести исследующий поиск. 

Шаг3. Поиск  удачный

Да: Перейти к шагу 5;

Нет: продолжить.

Шаг4. Проверка на окончание поиска. ||D||<e ?

Да: прекратить поиск;

Нет: уменьшить приращение по формуле    Di=Di/a,  i=1,2…N;

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

Шаг5. Провести поиск по образцу xр(к + 1) = x(к) + [x(к) - x(к - 1)]

Шаг6. Провести исследующий поиск, используя xр(к + 1) в качестве базовой точки ; x(к + 1)  - полученная в результате точка.

Шаг7. Выполняется  ли f(x(k+1))<f(x(k))?

Да: положить x(к - 1)= хк;  xк= x(к + 1);

Перейти к шагу 5;  

Нет: Перейти к шагу 4. 

 

Нахождение минимума целевой функции  методом Хука-Дживса.

 

Исходные данные:

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

Итерации  начинаются с исследующего поиска вокруг точки  , которой соответствует значение функции

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

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

Поскольку исследующий поиск был удачным, переходим к поиску по образцу:

Далее производим исследующий поиск вокруг точки  :

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

Получаем  новую точку:

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

Далее производим исследующий поиск вокруг точки  :

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

Получаем  новую точку:

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

Далее производим исследующий поиск вокруг точки  :

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

Получаем  новую точку:

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

Далее производим исследующий поиск вокруг точки  :

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

Получаем  новую точку:

Поскольку , поиск по образцу следует считать неудачным,

 

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

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

 

Исследующий поиск не дал результатов, поэтому  уменьшаем шаг: , базовая точка

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

 

Получаем  новую точку:

Поскольку исследующий поиск был удачным, переходим к поиску по образцу:

Далее производим исследующий поиск вокруг точки  :

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

Получаем  новую точку:

 

Поскольку , поиск по образцу следует считать неудачным,

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

Фиксируя  , даём приращение переменной :

Следовательно, необходимо зафиксировать  и дать приращение переменной :

 

Исследующий поиск не дал результатов, поэтому  прекращаем поиск. Искомая точка  оптимума:

Решение поставленной задачи методом Хука-Дживса представлено на рисунке 3.

 

Рисунок 3 – Решение задачи методом  Хука-Дживса

 

 

1.1.4 Метод сопряженных направлений Пауэлла

 

Метод ориентирован на решение задач с квадратичными  целевыми функциями. Основная идея алгоритма  заключается в том, если квадратичная функция

q(x) = a + bTx + ½ xT C x

приводится  к виду суммы полных квадратов

Q(x) = xT C x,

то процедура  нахождения оптимального решения сводится к N одномерным поискам по преобразованным  координатным направлениям.

В методе Пауэлла поиск реализуется в  виде

х(k+1) = x(k) + l×s(j)

вдоль направлений s(j),  j = 1,2,...,N, называемых C-сопряженными при линейной независимости этих направлений.

Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции N переменных необходимо выполнить N2 одномерных поисков.

Шаг 1. задать исходные точки х(1), х(2) и направление d. В частности, направление d может  совпадать с направлением координатной оси;

Шаг 2. произвести одномерный поиск из точки х(1) в  направлении d и получить точку y(1), являющуюся точкой экстремума на заданном направлении;

Шаг 3. произвести поиск из точки х(2) в направлении d и получить точку y(2);

Шаг 4. вычислить  направление (y(2) – y(1));

Шаг 5. провести одномерный поиск из точки у(1) (либо у(2)) в направлении (y(2) – y(1)) с выходом  в точку х*.

 

Нахождение минимума целевой функции  методом сопряжённых направлений  Пауэлла.

 

Исходные данные:

       

 

Итерация 1:

1. найдём значение , при котором минимизируется в направлении , т.е.

Произвольная  точка на луче из точки  в направлении определяется как:

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

2) Аналогично находим значение , при котором минимизируется в направлении , т.е.

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

Аналогично  находим значение , при котором минимизируется в направлении , т.е.

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

 

Положим .

Направление оказывается сопряжённым с направлением . Оптимизация вдоль направления даёт искомый экстремум.

Находим значение , при котором минимизируется в направлении , т.е.

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

 

Итерация 2:

1. найдём значение , при котором минимизируется в направлении , т.е.

Произвольная  точка на луче из точки  в направлении определяется как:

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

2) Аналогично  находим значение  , при котором минимизируется в направлении , т.е.

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

3)Аналогично  находим значение  , при котором минимизируется в направлении , т.е.

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

 

Положим .

Направление оказывается сопряжённым с направлением . Оптимизация вдоль направления даёт искомый экстремум.

Находим значение , при котором минимизируется в направлении , т.е.

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

Дифференцируем  по и приравниваем к 0, получаем:

Получаем:

Решение поставленной задачи методом сопряжённых  направлений Пауэлла представлено на рисунке 4.

Рисунок 3 – Решение задачи методом сопряжённых направлений Пауэлла

 

2. Градиентные методы