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

Недостаток метода прямого поиска состоит в том, что в случае сильно вытянутых, изогнутых или обладающих острыми углами линий уровня целевой функции он может оказаться неспособным обеспечить продвижение к точке минимума. Действительно, в случаях, изображенных на Рис. 1.4, а и б, каким бы малым ни брать шаг в направлении х₁ или x₂ из точки х’ нельзя получить уменьшения значения целевой функции.

Рис. 1.4. Прямой поиск: невозможность продвижения к минимуму: а – С₁ > C₂ > C₃; б - С₁ > C₂

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

 

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

 

Данный метод состоит в том, что для минимизации функции п переменных f(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому вектору х. Вычисляются значения целевой функции f(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершина х[h]. Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точка х[q] с меньшим значением целевой функции, чем в вершине х[h] (Рис. 1.5). Затем исключается вершина х[h]. Из оставшихся вершин и точки x[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.

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

Введем следующие обозначения:

x[i, k] =(x₁[i, k], …, x_j[i, k], …, x_n[i, k])^T

где i = 1, ..., п + 1; k = 0, 1, ..., - i-я вершина многогранника на k-м этапе поиска; х[h, k] — вершина, в которой значение целевой функции максимально, т. е. f(х[h, k] = max{f(x[1, k]), …, f(x[n+1, k])}; х[l, k] - вершина, в которой значение целевой функции минимально, т. е. f(х[l, k]) =min {f(x[1, k]), …, f(x [n+1, k])}; х [п+2, k]- центр тяжести всех вершин, за исключением х[h, k]. Координаты центра тяжести вычисляются по формуле

Алгоритм метода деформируемого многогранника  состоит в следующем.

1. Осуществляют проецирование точки  х[h, k] через центр тяжести:

x[n+3, k] =x[n+2, k] + a(x[n+2, k] - x[h, k]) ,

где а > 0 - некоторая константа. Обычно а = 1.

2. Выполняют операцию растяжения вектора х[n+3, k] - х[n+2, k]:

x[n+4, k] =x[n+2, k] + а(x[n+3, k] - x[n+2, k]),

где а > 1 - коэффициент растяжения. Наиболее удовлетворительные результаты получают при 2,8 <= а <= 3.

Если f(x[n+4, k]) < f(х[l, k]), то х[h , k] заменяют на x[n+4, k] и продолжают вычисления с п. 1 при k = k + 1. В противном случае х[h, k] заменяют на х[n+3, k] и переходят к п. 1 при k = k + 1.

3. Если f(x[n+3, k]) > f(х[i, k]) для всех i, не равных  h, то сжимают вектор x[h, k] - x[n+2, k]:

x[n+5, k] =x[n+2, k] + b (х[h, k] – x[n+2, k] ), где b > 0 - коэффициент сжатия. Наиболее хорошие результаты получают при 0,4 <= b <= 0,6.

Затем точку х[h, k] заменяют на х[n+5, k] и переходят к п. 1 при k = k+ 1.

4. Если f(x[n+3, k])> f(x[h, k]), то все векторы х[i, k] - х[l, k] . i= 1,..., п + 1, уменьшают в два раза:

x[i, k] = x[l, k] + 0,5(x[i, k] - x[l, k]) .

Затем переходят к  п. 1 при k= k + 1.

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

,

где e = (е₁ ,..., е_n) - заданный вектор.

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

1.3 Метод вращающихся координат (метод Розенброка)

 

Суть метода состоит  во вращении системы координат в  соответствии с изменением скорости убывания целевой функции. Новые  направления координатных осей определяются таким образом, чтобы одна из них соответствовала направлению наиболее быстрого убывания целевой функции, а остальные находятся из условия ортогональности. Идея метода состоит в следующем (Рис. 1.6).

Рис. 1.6. Геометрическая интерпретация метода Розенброка

Из начальной точки х[0] осуществляют спуск в точку х[1] по направлениям, параллельным координатным осям. На следующей итерации одна из осей должна проходить в направлении y₁ = х[1] - х[0], а другая - в направлении, перпендикулярном к у₁ . Спуск вдоль этих осей приводит в точку х[2] , что дает возможность построить новый вектор х[2] - х[1] и на его базе новую систему направлений поиска. В общем случае данный метод эффективен при минимизации овражных функций, так как результирующее направление поиска стремится расположиться вдоль оси оврага.

Алгоритм метода вращающихся  координат состоит в следующем.

1. Обозначают через р₁[k], ..., р_n[k] направления координатных осей в некоторой точке х[k] (на к-й итерации). Выполняют пробный шаг h₁ вдоль оси р₁[k], т. е.

x[kl] = x[k] + h₁p₁[k].

Если при этом f(x[kl]) < f(x[k]), то шаг h умножают на величину b > 1;

Если f(x[kl]) > f(x[k]), - то на величину (-b), 0 < |b| < 1;

x[kl] = x[k] + b h₁p₁[k].

Полагая ?h₁ = а₁ .получают

x[kl] = x[k] + a₁p₁[k].

2. Из точки х[k1] выполняют шаг h₂ вдоль оси р₂[k]:

x[k2] = x[k] + a₁p₁[k] + h₂p₂[k].

Повторяют операцию п. 1, т. е.

x[k2] =x[k] + а₁р₁[k] +а₂p₂[k].

Эту процедуру выполняют  для всех остальных координатных осей. На последнем шаге получают точку

х[kn] = х[k+1] = х[k] + .

3. Выбирают новые оси  координат p₁[k+1], …, р_n[k+1]. В качестве первой оси принимается вектор

р₁[k+1] = x[k+l] - x[k].

Остальные оси строят ортогональными к первой оси с  помощью процедуры ортогонализации  Грама - Шмидта. Повторяют вычисления с п. 1 до удовлетворения условий  сходимости.

Коэффициенты b подбираются эмпирически. Хорошие результаты дают значения b = - 0,5 при неудачных пробах (f(x[ki]) > f(x[k])) и b = 3 при удачных пробах (f(x[ki]) < f(x[k])).

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

1.4 Метод параллельных касательных (метод Пауэлла)

 

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

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

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

Суть метода такова. Выбирается некоторая начальная точка х[0] и выполняется одномерный поиск вдоль произвольного направления, приводящий в точку х[1] . Затем выбирается точка х[2], не лежащая на прямой х[0] - х[1], и осуществляется одномерный поиск вдоль прямой, параллельной х[0] - х[1],. Полученная в результате точка х[3] вместе с точкой х[1] определяет направление x[1] - х[3] одномерного поиска, дающее точку минимума х^*. В случае квадратичной функции n переменных оптимальное значение находится за п итераций. Поиск минимума при этом в конечном счете осуществляется во взаимно сопряженных направлениях. В случае неквадратичной целевой функции направления поиска оказываются сопряженными относительно матрицы Гессе. Алгоритм метода параллельных касательных состоит в следующем.

1. Задаются начальной точкой x[0]. За начальные направления поиска р[1], ..., р[0] принимают направления осей координат, т. е. р [i] = е[i], i = 1, ..., n (здесь e[i]= (0, ..., 0, 1, 0, … 0)^T).

2. Выполняют n одномерных поисков вдоль ортогональных направлений р[i] , i = 1, ..., п. При этом каждый следующий поиск производится из точки минимума, полученной на предыдущем шаге. Величина шага а_k находится из условия

f(x[k] + а_kр[k]) = f(x[k] + ар[k]).

Полученный шаг определяет точку

х[k+1] = х[k] + а_kр[k] .

3. Выбирают новое направление p =-x[n] - х[0] и заменяют направления р[1], ..., р[n] на р[2], ..., р [n], р. Последним присваивают обозначения р[1], ..., р[n]

4. Осуществляют одномерный  поиск вдоль направления р = р[n] = х[n] - х[0]. Заменяют х[0] на х[n+1] = х[n] + а_nр[п] и принимают эту точку за начальную точку х[0] для следующей итерации. Таким образом, в результате выполнения рассмотренной процедуры осуществляется поочередная замена принятых вначале направлений поиска. В итоге после n шагов они окажутся взаимно сопряженным.

2 Вопросы по теме 

 

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

2. Какой метод называется  методом нулевого порядка?

3. Какой алгоритм называется  случайным поиском минимума?

4. Расскажите про методы прямого поиска?

5. Расскажите про методы  деформируемого многогранника?

6. Расскажите про метод вращающихся координат?

7. Расскажите про Метод  параллельных касательных?

8. Задача условной  оптимизации это?

9. Нарисуйте графики   глобального минимума?

10. Расскажите побольше  про методы нулевого порядка?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.1 Задачи

Найти минимум функции  методом равномерного поиска

Воспользуемся алгоритмом равномерного поиска.

1. Найдем начальный  интервал неопределенности методом  Свенна

2 Задача Найти минимум  функции  методом Розенброка.

 

 

 

 

 

Задача 3 .

Найти минимум целевой  функции f(x)= (х1 - 5)² + (х2 – 9)² +х1•х2. Методом Хука-Дживса

Dх – векторная величина приращения

Dх = 1;

a - коэффициент уменьшения шага.

a = 2;

e - минимальное значение приращения α, при котором ещё стоит искать минимум.

В условиях данной задачи ограничимся значением α =1, т.е. будем  искать минимум до первого уменьшения приращения.

Ход решения.

х⁽⁰⁾=[-10.00][-10.00]Þ f = 686

1. Исследующий поиск вокруг базовой точки х⁽⁰⁾:

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

х2=-10; х1=-10+2=-8 Þ f = 610<686Þудача

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

х1=-8;  х2=-10+2=-8 Þ f = 522<610Þудача

х⁽¹⁾ = [-8.00][-8.00];

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

х_p⁽²⁾ = 2•х⁽¹⁾ – х⁽⁰⁾;

х_p ⁽²⁾ = [-6][-6]Þ f =382

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

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

х2=-6; х1=-6+2=-4 Þ f = 330<382Þудача

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

х1=-4;  х2=-6+2=-4 Þ f = 266<330Þудача

х⁽²⁾ = [-4.00][-4.00];

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

х_p ⁽³⁾ = 2•х⁽²⁾ – х⁽¹⁾;

х_p ⁽³⁾ = [0][0] Þ f =106

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

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

х2=0; х1=0+2=2 Þ f = 90<106Þудача

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

х1=2;  х2=0+2=2 Þ f = 62<90Þудача

х⁽³⁾ = [2][2];

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

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

х_p ⁽⁴⁾ = [8][8] Þ f =74

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

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

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

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

х2=8; х1=8-2=6 Þ f = 50 < 62Þудача

х1 = 6;

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

х1=6;  х2=8+2=10 Þ f = 62>50Þнеудача

х1=6;  х2=8-2=6 Þ f = 46<50Þудача

х⁽⁴⁾ = [6][6];