Тогда прямая соединякяцая точки Ф, и сопряжена любой пря мой, параллельной гиперплоскостям. Соответственно, если Ф1 и Ф- два различных минимума, полученных с помощью поиска вдоль направ лення S но с началом в двух различных точках то вектор (Ф1 - Ф) сопряжен направлению s. Поэтому если s, взято вдоль линии, соединя ющей два минимума полученных поиском вдоль s, , то направления (Si-i. ь) сопряжены.

Метод Пауэлла поиска по образцу заключается в минимизации вдоль множества направлений в Ф-пространстве. Вначале это множество совпадает с множеством координатных направлений. Направление о&цего приращения i одном цикле является направлением образца и кроме того, испольчуется как следукндее направление поиска. Во втором цикле напрац.1ение образца вклнмается в множество пробных направлений, а nepiwe направление исключается. Продолжая таким же образом, получаем в п-м цикле направления {и„, s,, Sj,..., s„ i}

Чтобы первое направление образца Sj было сопряжено и„, поиск перед первым циклом выполняется вдоль Un. Поэтому в п-м цикле все направления являются сопряженными. Метод Пауэлла является очень эффективным методом поиска вследствие хорошей сходимости вдоль сопряженных направлений. Это обусловлено не тем, что часто прнхо днтся оптимизировать квадратичные функции, а тем, что большинство функций в окрестности минимума хорошо приближается квадратичны ми функциями. Если разложить п-мерную функцию в ряд Тейлора в окрестности минимума, то члены включающие производные высшего порядка, являются малыми более высокого порядка, чем квадратич ные, и поэтому U (Ф) хорошо приближается ква;фатичной функцией в окрестности минимума.

Алгорй-ш метода Хука и Дживса, приведенный ранее, можно видо изменить так чтобы получить алгоритм метода Пауэлла:

Метод Пауэлла

Фо-начальная точка

For alt \ to п do si u,

Получить X.*, минимизирующее U(©o-Xs)

Repecd

Ф„ Ф

For all i- I ton do begin

Получить X* минимизирующее и(Ф- X&i)

Ф = Ф + Х51

For alliri io n -I do SfSi

5„ Ф-Фв

Получить к мннимизнрукицее и(Ф Xsn) until до сходимост Ф

17 I 3 МЕТОД ЛЕЗВИЯ

В работе 13! указано, что минимум для многих минимаксных типов целевых функций лежит вдоль направления разрыва производных функции и (Ф). Примером целевой функции такого типа является

[/(Ф) тш{ max (р(Ф /) I)} (17 5)

Ф II,. f„i

где, например, р представляет собой комплексный коэффициент отра жения от многоступенчатого согласующего трансформатора сопро тивлений; fj и /и -- нижняя и верхняя частоты рабочей полосы частот Ф - множество параметров проектирования, которыми являются длины и волновые сопротивления (или размеры) различных секций Целевые функции этого типа имеют кривую разрыва производных расположенную вдоль узкой искривленной долины. Разрывы производ ных возникают когда U (Ф) перескакивает с одного экстремума на другой.

Поиск по образцу, рассмотренный в пощзазд. 17.1.1, может окон чнться в ложном минимуме на кривой разрыва производных В модифи цированном алгоритме 13) после одной такой остановки производится случайный выбор новой точки Новая точка выбирается согласно пра вилу

ф.,, = ф, „, + kR{i) f.= l 2 п (17 6)

где Ф,, задают положение точки минимума (возможно, ложного) вычисленного в одном цикле процедуры поиска по образцу Хука и Дживса; R (i) •- случайное число в интервале --1... + 1; k - масштабный множитель Пусть следукмций цикл поиска по образцу начинается

Ф, (Ф, 4, I 1 2

(17 7)

и оканчивается, например в Фг- Если Ф приблизительно совпадает с конечной точкой первого цикла поиска то можно сделать вывод о том, что минимум найден правильно и не является ложным. С другой стороны, если Ф,, отличается от Фт1, направление образца определя ется как

s-Ф-Ф„,

(17 8)

и поиск продолжается в этом направлении Довольно часто это приво дит к правильному нахождению минимума что можно проверить с по мощью другого случайного перемещения, как в (17.6).

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

[/(Ф) -=100(Фг-Ф?)-(1-Ф). (17.9)

Эта функция не имеет разрывных производных. Если метод лезвия используется без случайных перемещений (т. е. имеем метод поиска по образцу) и (Ф) становится равной 7,4-10""* после двухсот циклов

вычисления значения функции. В методе лезвия с тремя случайными перемещениями значение минимума U {Ф) равно 1,6-10 * после 172 циклов вычисления значения функций Теоретически минимальное значение U (Ф) равно нулю

Модификация алгоритма поиска по образцу включающая случаи !(ые перемшхения имеет вид

Алгоритм лезвия /

Получить Фд миннмтнрующее L (Ф) методом Хука и Дживса с нaчdльнoн точ коб Ф,

Repeui

Ф.-Фа

For all \-ltund Ф- Ф] kR(i)ui

Получить Фь мн шмизирующее L {Ф) методом XvKa и Дживса с началыой точкой Ф]

s-Фь-Фа

Получить к минимизирующее СЦФь + ья) ФаФьЯЧ

until (/s<8

172 МЕТОД ВРАЩЕНИЯ КООРДИНАТ

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

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

поиска si, sj,..., s„. На ;-m этапе минимизации (начиная с ; ~ 1) вы полняются следукйцие действия. Множество направлений s, s",. si и базисная точка известны. При у - 1 эти направления совпадакуг с координатными осями, а в качестве базисной точки берется любая до пустимая точка. Вдоль направления s> из известной базисной точки делается шаг Л.,. Если этот шаг успешный, то умножается на по стоянную а и новая точка запоминается. Еслн шаг неудачен, то умножается на другую шстоянную - р, и новая точка стирается. Шаг считается успешным, если новое значение целевой функции меньше старого или равно ему. В противном случае шаг считается неудачным Значения постоянных аир, рекомендованные Розенброком равны со ответственно 3,0 и 0,5.

Поиск продолжается последовательно вдоль направлении s[", s{K... sl/Li, si", s[", so ... до тех пор, пока в каждом из « направлении {- Ч. s" не окажется, по крайней мере, по одному успешному и Одному неудачному шагу Новое множество направлений s/+>, 5+ , sl* для использования в / + 1 итерации процедуры миннмиза ций получается с помощью алгоритма ортогонализации Грама -

Шмидта 8. Дяя этой цели множество независимых направлении pi р2,..., р„ вычисляется как

(17 10)

где - алгебраическая сумма всех успешных длин шагов в соответ ствунмцем направлении s*, k - 1,2.....п.

Матрица в правой части (17.10) является нижней треугольной. Мож но заметить, что р, представляет собой вектор, соединяющий началь ную и конечную полученную в результате последовательности поис ков на /-Й операции, точки. Вектор р обозначает алгебраическую сум му длин успешных шагов по всем направлениям, кроме первого и т д Поэтому векторы р,, рг,,., Рп линейно-независимы

Направление 5/"" задается теперь формулой

st"-p, 11р,

а остальные направления s как s;*H q jq [ i. 2 3 п

q, -р - V [ps;;) i

(1711)

(17 12)

(17 13)

Конечная точка, полученная в результате (-й итерации, служит ба зиснойдля следующей итерации, и процесс продолжается.

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

IL К i Д1я всех i

(17 14)

удовлетворяется при достаточно малом е.

Метод Розенброка, рассмотренный в этом подфазделе позволяет осуществлять перемещение вдоль искривленных и крутых долин, пос кольку систем} координат в п-мерном пространстве можно вращать в желаемом направлении. Исходный метод Розенброка можно видоизме пять так, 410 в любом цикле поиск будет продолжаться в каждом на правлении до тех пор, пока небудет найден оптимум [9}. Другими ело вами, к каждому из направлений поиска применяется одномерная ми нимизация. Этот видоизмененный метод, по-видимому, превосходит по качеству как метод Хука и Дживса, так и метод Розенброка

Процедура метода вращения координат Розенброка оформленная в виде алгоритма имеет вид

Алгоритм вращения координат

For all il to п do s) =ui Repeat

For ail i = 1 to n do begin

1-1=0 sue (i)=0

fail(i) -0 /sue и fa I end (for i) Repeal

For all i = i lo П do begin

then

begin

Ф-Ф + Х)

U* = f/i Li--L,-rX X,=- aX, suc(i)-i

else

begin X f

X.,--pX., fail(i)~!

end (lor i) ex=l ex логическая переменная/ For all s- \ lo n do ex = ex and shc(i) and ia\\ { )

until ex

Получить рд Pj P„ яспо1ьзуя (17 10)

For all i=2 /0 n do begin

i 1

41-я1 - 2 IpI*™}*™

m=i s = 4i/Il ч1II end (for i)

until Max / Ll / < e

173 СИМПЛЕКСНЫЙ МЕТОД 5. 6

Геометрическая фигура, порожденная n Ц- 1 точкой в /i-мериом пространстве, называется симплексом. Эти точки называются вершинами симплекса. Симплекс-топологическое обобш.ение треугольника, который может быть назван симплексом в двумерном пространстве. Тетраэдр - это трехмерный симплекс. Когда вершины равноудалены друг от друга, симплекс называется правильным.

Симплексный метод [5,61 минимизации многомерной ц&тевой функ ции начинается с симплекса произвольной формы в и-мерном прост ранстве. Значение функции вычисляется в п + 1 вершине симплекса. В результате последовательных итераций симплекс модифицируется, двигаясь к точке оптимума и сжимаясь вокруг нее. Симплекс преобразуется с помощью различных операций, таких как отражение, растяжение, редукция и сжатие. При рассмотрении этих операций будем использовать следукндие обозначения:

- вершина, соответствунмдая наиб01ьшему значению U (ф) среди вершин симплекса, т. е

(/(Фд)- max {(У(Ф»1

(17 15)

Ф« - вершина соответствующая второму по величине значению и (Ф) т. е

(/(Ф,)- шах {и{ф,)):

(17 16)

Ф -вершина соответствующая наименьшему значению u (ф) и{ф!} - min {у{ф}у (17 17)

Фп - центр тяжести симплек а образованного всеми вершинами отличными от Ф:

Фу J- у ф

(17 18)

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

ффц-о(Ф Фв)

(17 19) 331