Лекции / Т5_ДГМ
.pdf
ТЕМА5. МЕТОДЫ ПОИСКА ЭКСТРЕМУМА ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕЕННЫХ
Методы, ориентированные на решение задачи поиска экстремума функции нескольких переменных, можно условно разделить на три широких класса в соответствии типом используемой при реализации того или иного метода информации:
1.Методы прямого поиска, основанные на вычислении только значения целевой функции.
2.Градиентные методы, в которых используются точные значения первых производных целевой функции .
3. |
Методы второго порядка, в которых наряду с первыми производными |
|
|
используются так же и вторые производные целевой функции |
. |
5.1 Методы прямого поиска |
|
|
5.1.1 |
Метод поиска экстремума Нелдера-Мида (деформированного |
|
многогранника) |
|
|
Данный метод хорошо зарекомендовал себя при решении задач параметрической оптимизации систем управления электромеханическими объектами.
Поиск экстремума этим методом основан на использовании симплексов. Симплексом называется n-мерная замкнутая геометрическая фигура, ребра которой представляют собой прямые линии, пересекающиеся в n+1 вершине.
|
Суть алгоритма минимизации функции нескольких переменных |
||||
|
|
|
где |
варьируемые параметры системы |
|
управления,, |
состоит, … , |
в следующем:1 … |
|
||
1. В соответствии с числом варьируемых параметров "n"nформируется1 n
нормированная матрица планирования на симплексе, размером .
65
|
|
|
|
|
|
|
|
0 |
0 |
|
|
|
0 |
|
|
|
|
|
|
|
|
, |
|
|
|
|
$ |
, |
|
|
|||||
|
|
|
|
|
|
|
! |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
где |
|
|
|
|
|
|
|
|
- . |
|
|
|
|
|
|
||
|
√ |
√ |
|
|
|
|
|
|
|
|
|||||||
|
)√+ +, |
|
)√+ |
|
, |
, а |
|
|
расстояние |
между вершинами |
|||||||
симплекса (на практике часто принимают |
- 1 ). |
При |
- 1 и 2 |
||||||||||||||
нормированная матрица М(3,2)получит вид: |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
3,2 20.965 |
|
0.2592 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
0.259 |
|
0.965 |
|
|
|
|||
На основании матрицы , вычисляется матрица планирования |
|||||||||||||||||
|
|
|
|
|
8 89 ∆ 8 8, |
|
|
|
|
|
|||||||
7 , в натуральных единицах. Элементы этой матрицы определяются как:
где 89— начальные значение варьируемых параметров, а ∆ 8 — начальные шаги их изменения.
С целью удобства дальнейшего описания алгоритма строка параметров, |
|||
задающая . ю вершину, обозначается как: |
, |
|
|
|
|
|
|
а описание самого алгоритма7 на примере… … |
варьирования |
двух переменных |
|
поясняется графически на рисунке 5.1.
2. В каждой вершине симплекса вычислим значение целевой функции:
=7>? , 1 … 1, @ 0
Индекс "@" соответствует номеру текущего шага в направлении экстремума.
3. Определяется наихудшее (максимальное) и наилучшее (минимальное)"A"и "B"
значение целевой функции и соответствующие им индексы строк в
матрице планирования на симплексе:
=7C>? D E =7>? , =7>? … =7+> ?F
66
=7G > ? E =7 > ? , =7 > ? … =7+> ?F
4. Вычисляются координаты центра тяжести симплекса: |
|
|||||||||||||||
|
|
7+> ,8 |
|
|
|
=∑+I 7 8> . 7C8> ?, 1 … . |
||||||||||
|
|
|
|
|||||||||||||
5. Определяются координаты отраженной точки: |
|
|||||||||||||||
|
7+J,8> |
7+> ,8 |
K =7+> ,8 |
. 7C8> ? , 1, … |
||||||||||||
. |
|
K L 0 |
|
|
|
|
|
|
|
|
> ] Коэффициент отражения |
|||||
а затем значение целевой функции в ней f[ |
||||||||||||||||
K 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
модификации принят равным |
||
принимается всегда |
|
|
|
|
, |
|
|
а |
в конкретной |
7+J |
|
|||||
6. Проверяется условие: |
? N =7G > ?………………….(5-1) |
|||||||||||||||
|
|
|
|
|||||||||||||
|
|
=7+J> |
||||||||||||||
|
Если оно выполняется, то производится растяжение симплекса с |
|||||||||||||||
коэффициентом |
растяжения |
O 2 |
. |
Координаты |
точки растяжения |
|||||||||||
определяются как: |
|
|
|
|
|
|
|
|
|
|
|
. 7+> ,8 ? , 1 … , |
||||
|
7+P,8> |
7+> ,8 O 2 =7+J,8> |
||||||||||||||
В точке растяжения вычисляется значение |
=7+P> ? |
|
||||||||||||||
7. Проверяется условие: |
|
|
|
=7+P> ? N =7+J> ?, |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||
в случае его выполнения худшая вершина симплекса с индексом "A" |
||||||||||||||||
заменяется вершиной с индексом 4, то есть: |
|
|||||||||||||||
|
7C> |
V 7+P> |
; =7C> ? V =7+P> ? |
(5-2) |
||||||||||||
|
В противном случае худшая вершина заменяется на вершину с |
|||||||||||||||
индексом " 3": |
|
|
7C> |
V 7+J> ; =7C> ? V =7+J> ? |
|
|||||||||||
|
|
|
|
|
||||||||||||
и поиск экстремума продолжается, начиная с пункта 3.
8. Если условие (5-1) не выполняется, тогда определяется вершина симплекса с наибольшими после худшей вершины с индексом «h» значением целевой функции:
67
=7X> ? D E =7 > ? , =7 > ? … =7,> ? , =7+> ? … =7+> ?F |
|
и анализируется условие: =7+J> ? N =7X> ?. |
|
При выполнении этого условия худшая вершина заменяется на |
|
вершину 7+J> : |
7C> V 7+J> ; =7C> ? V =7+J> ? |
|
|
после чего движение к экстремуму продолжается с пункта 3, иначе анализируется условие
=7+J> ? N =7C> ? |
(5-3) |
|
Если (5-3) выполняется, то координаты худшей вершины заменяются |
||
на координаты вершины с индексом " 3": |
?, |
|
7C> V 7+J> ; =7C> ? V =7+J> |
(5-4) |
|
после чего осуществляется сжатие вектора |
7C> . 7+> |
, смысл которого |
состоит в определении вершины с индексом «n+4», в соответствии с выражением:
7+P,8> |
7+> ,8 Y 0.5 =7C,8> . 7+> ,8 |
?, |
1 … |
и вычислении значения =7+P> ?. |
|
|
|
Коэффициент сжатия принимается равным =0,5. |
|
||
Если (5-3) |
не выполняется, то операцияY |
сжатия выполняется сразу, |
|
минуя замену (5-4).
9.Проверяется эффективность сжатия по условию:
=7+P> ? N =7C> ?
Если оно соблюдается, то выполняется операция (5-4) и поиск экстремума выполняется с пункта 3. Если нет, то симплекс редуцируют, то
68
есть, все векторы X (k) − X (k) (i =1...n +1) |
уменьшают в 2 раза с отсчетом от |
||||
i |
l |
|
|
|
|
Xl(k) в соответствии с формулой: |
|
|
|
|
|
X (k) = X |
(k) + 0,5[X |
(k) − X |
(k) |
],i =1...n + 1; j =1...n |
|
i, j |
i, j |
i, j |
|
l, j |
|
Далее вычисляются значения целевой функции во вновь определенных точках (n+1)-мерного пространства параметров и поиск экстремума продолжается с пункта.3.
Рисунок 5.1
10. Для окончания поиска экстремума функции нескольких переменных Нелдером и Мидом предложен критерий, состоящий в проверке условия:
69
|
1 |
+ |
> |
> |
|
/ |
N e |
|
^ 1 |
_I `7 a . b7+ |
a c |
|
|||
где ε – |
наперед заданное |
сколько |
угодно |
малое положительное число, |
|||
а =7+> |
? - значение целевой функции в центре тяжести на -ой итерации. |
||||||
5.1.2 Метод поиска экстремума Хука-Дживса.
Процедура поиска экстремума функции нескольких переменных, разработанная Хуком и Дживсом, представляет собой комбинацию исследующего поиска с циклическим изменением переменных и поиска по
образцу с использование определенных правил.
Алгоритм поиска Хука-Дживса можно представить последовательностью
следующих шагов: |
|
|
1. На старте определяются: |
|
|
1.1 |
Координаты начальной точки - 79. |
, 1 … . |
|
g L 1 |
|
1.2 |
Величины приращений варьируемых переменных |
|
1.4Параметр окончания цикла e L 0. .
2.Выполняется процедура исследующего поиска/1.3 Коэффициент уменьшения шага
Поиск начинается из начальной точки. Поочерёдно изменяется одна из варьируемых переменных, значения остальных переменных при этом не изменяются. Если значения целевой функции в пробной точке оказывается меньше, чем в исходной, то шаг поиска по этой переменной рассматривается как успешный. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой значения целевой функции. После последовательного перебора всех «n» координат исследующий поиск завершается. Полученную в результате точку в пространстве варьируемых параметров называют базовой
70
точкой.
Если поиск новой базовой точки оказался удачным, осуществляется переход к выполнению шага «4», в противном случае к шагу «3».
3. Производится проверка на завершение поиска экстремума. С этой целью проверяется выполнение неравенства:
hΔ7h i_ N e
I
Если оно выполняется, то поиск прекращается, иначе приращения всех
переменных уменьшаются по формуле:/g, 1 …
,
после чего осуществляется переход к шагу «2».
4. Выполняется поиск по образцу, который заключается в реализации единственного шага из полученной базовой точки вдоль прямой соединяющей эту точку с предыдущей базовой точкой. Новая точка образца
определяется в соответствии с формулой: |
|
|
, |
|
|
|
|
|
|
|
||||
|
|
7 >+ |
7> 7>.7>, |
|
7 |
> |
, |
7 |
>, |
|
||||
где |
>+ – точка полученная |
при движении |
по образцу, |
а |
– |
|||||||||
соответственно7 |
текущая и предыдущая базовые точки |
7>+ |
|
|
|
|
||||||||
5. Выполняется исследующий поиск, в котором |
используется |
в |
||||||||||||
качестве базовой точки. Пусть |
7 |
>+ , полученная в результате такого поиска |
||||||||||||
точка. |
|
|
|
|
|
|
|
|
|
|
|
|
||
6. Проверяется выполнение неравенства j7>+ k N j7>k . Если оно |
||||||||||||||
выполняется, то производится переиндексация |
>+ |
, |
|
|
|
|
|
|
|
|||||
|
|
>, |
> |
> |
|
|
|
|
|
|
|
|||
после |
чего осуществляется7 |
переходV 7 ; к7 |
шагуV 74. Если не |
выполняется, |
||||||||||
7осуществляется переход к шагу 3, минуя операцию переиндексации значений
.
Пример поиска экстремума методом Хука-Дживса
71
Требуется определить минимум функции:
8 4 5 , используя начальную точку 79 .4, .4Т. Зададим следующие величины:
1.Величину приращения переменных ∆Х = [1,1]Т;
2.Коэффициент уменьшения шагаε α =2;
3.Параметр окончания поиска = 10-3
и будем графически с помощью рисунка 5.2 пояснять характер движение к экстремуму при применении данного метода
Рисунок 5.2 |
|
79 , |
Итерации начинаются с исследующего поиска вокруг точки |
||
которой соответствует значение функции 79 |
=272. Фиксируя значение |
|
дадим приращение переменной : |
|
72 |
.4; |
|
|
|
|
|
|
|
= |
.4+1→ .3, .4 200 N 79 → Успех, |
.3 и |
|
дать |
|||
следовательно, теперь |
необходимо зафиксировать |
|
|||||
приращение переменной : |
|
|
|
|
|||
.3; |
|
153 N 200 →Успех. |
|
|
|
|
|
.4 1 → .3, .3 |
|
|
|
|
|||
|
Таким образом, в результате исследующего поиска найдена точка |
||||||
Поскольку7 .3,исследующий.3 , в которойпоиск7удачный153.переходим к поиску по образцу: |
|
||||||
|
|
Т |
|
|
|
|
|
7р 7 `7 . 79a .2, .2 Т, а f[7р ]=68 |
|
|
|
|
|||
|
Далее производить исследующий поиск вокруг точки 7р который |
||||||
.1, .1 Т,f 7 |
17. |
В результате получаем |
точку |
7 |
|
|
|
оказывается |
удачным. |
|
|
||||
Поскольку f 7 Nf 7 поиск по образцу следует считать успешным и |
|||||||
7 становится новой базовой точкой при следующем проведении |
|||||||
поиска по образцу. Итерации продолжаются |
пока |
уменьшение |
|||||
величины шага не укажет на окончание поиска. |
|
|
|||||
5.2 Градиентные методы поиска экстремума |
|
|
|||||
5.2.1 Метод наискорейшего спуска (Метод Коши) |
|
|
|||||
Если |
целевая |
функция |
непрерывна и |
дифференцируема, то |
|||
существует |
градиент |
gradf(x)определяемый |
как вектор-столбец из первых |
||||
частных производных f(x) по 7> |
значения которых берется в данной точке |
||||||
Х> таким образом, что градиент в |
7>равен: |
|
|
|
|||
|
|
… > |
†‡†ˆjˆŠ‰k$; |
|
|
||
|
|
†‡jˆ‰k |
|
|
|||
|
|
|
|
†ˆ‹ |
|
|
|
|
|
|
|
|
|
|
73 |
Известно, что градиент скалярной функции направлен в сторону
наискорейшего увеличения функции (наискорейшего подъема) и что он |
||||||||
ортогонален линии равного |
уровня |
проход |
через |
точку |
> . |
|||
Следовательно нужно двигать в направлении противоположном градиенту |
||||||||
|
т.е. в направлении наискорейшего спуска поскольку отрицательный |
|||||||
градиент в точке > направлен в |
сторону наибольшего |
уменьшения |
||||||
по |
всем компонентам Х и ортогонален линии равного уровня |
в |
||||||
точке |
|
>.Переход из одной точки в другую при поиске экстремума по методу |
||||||
наискорейшего |
>+ |
> . > |
… > |
|
|
|
||
спуска выполняется по выражению: |
|
|
|
|||||
|
|
|
|
λ |
> |
|
|
|
|
Отрицательный градиент |
дает толькоh…направлениеh |
оптимизации, но не |
|||||
величину шага. При этом можно использовать различные процедуры метода
наискорейшего спуска в зависимости от выбора λ и определения выражения |
|||||||||||||||||
Œ… > Œ |
. При выборе размера шага обычно |
|
применяют |
один |
из двух |
||||||||||||
подходов. |
В случае использования первого подхода при переходе из |
||||||||||||||||
> в |
>+ |
целевая |
функция минимизируется по |
λ. При |
другом |
подходе |
|||||||||||
величина |
λ может рассматриваться как фиксированное или меняющееся от |
||||||||||||||||
шага к шагу. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Пример: |
Требуется минимизировать |
|
функцию |
||||||||||||||
начиная поиск экстремума из точки |
9 |
|
• |
|
|
|
25 ; |
||||||||||
|
На каждом этапе нам потребуется значения2,2 ; |
следующих выражений: |
|||||||||||||||
Ž > |
2 |
> |
; |
Ž > |
> |
|
Œ… |
> |
Π|
Ž > |
Ž > |
||||||
Ž |
|
Ž |
50 ; |
|
|
•• |
Ž |
‘ |
• |
|
Ž ‘ |
||||||
Будем считать что длина шага λ 1 |
|
|
|
|
|
|
|
|
|
|
|
||||||
Результаты нескольких этапов поиска экстремумов удобно представить
как показано в таблице 5.1.
74