Численные методы безусловной оптимизации нулевого порядка

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽⁵⁾ = 2•х⁽⁴⁾ – х⁽³⁾;

х_p ⁽⁵⁾ = [10][10] Þ f =126

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

5. Исследующий поиск вокруг точки х_p ⁽⁵⁾:

фиксируя х2, даём приращение переменной х1:

х2=10; х1=10+2=12 Þ f = 170>46Þнеудача

х2=10; х1=10-2=8 Þ f = 90>46Þудача

фиксируя х1, даём приращение переменной х2:

х1=10;  х2=10+2=12 Þ f = 154>46Þнеудача

х1=10;  х2=10-2=8 Þ f = 106>46Þнеудача

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

α = 2/2=1;

Далее необходимо произвести исследующий поиск вокруг точки  х⁽⁴⁾ = [6][6],

используя новое значение приращения α =1;

6. Исследующий поиск вокруг точки х_p ⁽⁴⁾:

фиксируя х2, даём приращение переменной х1:

х2=6; х1=6+1=7 Þ f = 55>46Þнеудача

х2=6; х1=6-1=5 Þ f = 39<46Þудача

фиксируя х1, даём приращение переменной х2:

х1=5;  х2=6+1=7 Þ f = 39=39Þнеудача

х1=5;  х2=6-1=5 Þ f = 41>39Þнеудача

х⁽⁵⁾ = [5][6];

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽⁶⁾ = 2•х⁽⁵⁾ – х⁽⁴⁾;

х_p ⁽⁶⁾ = [4][6] Þ f =34

 

7. Исследующий поиск вокруг точки х_p ⁽⁶⁾:

фиксируя х2, даём приращение переменной х1:

х2=6; х1=4-1=3 Þ f = 31<34Þудача

фиксируя х1, даём приращение переменной х2:

х1=3;  х2=6-1=5 Þ f = 35 >31Þнеудача

х1=2;  х2=6+1=7 Þ f = 29 <31Þудача

х⁽⁶⁾ = [3][7];

Т.к. поиск был удачным, переходим к поиску по образцу:

х_p ⁽⁷⁾ = 2•х⁽⁶⁾ – х⁽⁵⁾;

х_p ⁽⁷⁾ = [1][8] Þ f =25

8. Исследующий поиск вокруг точки х_p ⁽⁷⁾:

фиксируя х2, даём приращение переменной х1:

х2=8;  х1=1+1=2 Þ f = 26>25Þнеудача

х2=8; х1=1-1=0 Þ f = 26>25Þнеудача

фиксируя х1, даём приращение переменной х2:

х1=1;  х2=8-1=7 Þ f = 27>25Þнеудача

х1=1;  х2=8+1=9 Þ f = 25 = 26Þнеудача

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

α = 1/2=0.5;

Далее необходимо произвести исследующий поиск вокруг точки  х_р⁽⁷⁾ = [1][8],

используя новое значение приращения α =0.5;

Когда α достигнет  какого-то небольшого значения, заданного  пользователем, поиск экстремума можно  прекратить.

Т.о. мы получили точку  х* = [1;8]^Т, значение функции в которой f(x*) = 25. Эта точка ещё не значительно приближена к стационарной, однако дальнейший ход решения укажет на улучшение результата.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Графическое приложение к методу Хука-Дживса

 

 

 

 

 

 

 

 

 

 

 

2.3 Тесты

1. Решение многих теоретических и практических задач сводится к отысканию:

А) наибольшего значения

Б) наименьшего знчения

В) наибольшего  и наименьшего значения

Г) производной

2. Метод нулевого порядка:

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

б)на каждой итерации используются  значения минимизируемых функций и  требуется вычисление первых производных минимизируемой функции

в)все ответы верны

г) нет правильного  ответа

3. Какой из рисунков  относится к геометрической интепретации  метода Розенберка

А)

Б)

В)

Г) нет правильного  ответа

4. Геометрическая интерпретация метода деформируемого многогранника:

А)

Б)

Г)

Д) нет правильного  ответа

5.  Геометрическая  интерпретация метода Пауэлла: 

А)

Б)

Г)

Д) нет правильного  ответа

6.Каждая точка х в n-мерном пространстве переменных х₁, …, х_n, в которой выполняются ограничения, называется

А) допустимая точка задачи

Б)  ограниченная точка  задачи

В) Допустимо-ограниченная точка задачи

Г) нет правильного  ответа

7. Сколько существует  подходов к отысканию минимума функции многих переменных f(x) = f(x₁, ..., х_n) при отсутствии ограничений на диапазон изменения неизвестных?

А) 3 подхода

Б) 4 подхода

В) 1 подход

Г) 2 подхода

8. Что представляет  собой метод Хука-Дживса?

А) является методом прямого поиска минимума функции нескольких переменных, т. е. методом использующим только значения функции.

Б) метод безусловной оптимизации функции от нескольких переменных, не использующий производной функции, а поэтому легко применим к негладким и/или зашумлённым функциям.

Суть метода заключается  в последовательном перемещении  и деформировании симплекса вокруг точки экстремума.

В) метод нахождения локального минимума (максимума) функции с помощью движения вдоль антиградиента (градиента).

Г) называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в определённом виде.

9. Метод Пауэлла:

А) является методом прямого поиска минимума функции нескольких переменных, т. е. методом использующим только значения функции.

Б) метод безусловной  оптимизации функции от нескольких переменных, не использующий производной  функции, а поэтому легко применим к негладким и/или зашумлённым  функциям.

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

В) метод нахождения локального минимума (максимума) функции с помощью движения вдоль антиградиента (градиента).

Г) называют также  и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в определённом виде.

10.  Какого вида метода  спуска нет?

А) Метод градиентного спуска

Б) Метод наискорейшего  спуска

В) Метод покоординатного спуска

Г) Метод повекторного спуска

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованных источников

 

1.  Акулич И.Л. Математическое  программирование в примерах  и задачах / И.Л. Акулич. М.: Высшая  школа, 2007.335 с.

2.  Аттетков А.В.  Методы оптимизации / А.В. Аттетков, С.В. Галкин,

3. В.С. Зарубин. М.: МГТУ, 2008.432 с.

4.   Васильев В.П.  Численные методы решения экстремальных  задач / В.П. Васильев. М.: Наука, 2007.518 с.

5.   Габасов Р. Методы оптимизации / Р. Габасов, Ф.М. Кириллова. Минск: БГУ, 2007.400 с

6.Голубев А. Д. «  Методы оптимизации». – Киров, 1997.

7. Щетинин Е.Ю. Математические методы оптимизации. Конспект лекций