--{(a + b)z + bux + avb).

(16.90) (16.91)

begin

If > уф then

begin

с -В

А = Ф*

Получить Ф*, ((/ до тех пор. 1

i критерий i.

Метод кубической интерполяции [16, 81. Прн этом методе используется кубическая функция

И{Ф}га + ЬФ - сФ + аФ"* (16.83)

для приближения целевой функции u (Ф) между точками А и S. Д.1я вычисления постоянных а, Ь, с и d используются значения 6/ (Ф) и ее первой производной в точках Л и В. Имеем

и а а + ЬА+сА + dA, ua -а ЬВ + cBdB, ua--b + 2iA 3dA\ uh-b 2(B3dB.

Значения постоянных находятся следующим образом: а --ua~bA -cA-dA\

b----Bua+A-uh + 2ABZ,

(/1 - 8)2

(16.84) (16.85) (16.86) (16.87)

(16 89)

Z -3 (0- ,-ta)/(S- a)-\-ukub.

(16.92)

Минимум h (Ф) определяется из условия dh/dO О и задается формулой

ф*\~c±Vc~Зbd]/Зd. (16.93)

Применение достаточного условия минимума к h (Ф) приводит к

dhdФ - 2с4 6Ф*>0.

(16.94)

После подстановки значений Ь, с. d точка минимума Ф* определяется как

фа; ф-а),

(16.95)

Q - {Z -UAUk}" (16.96)

Два значения Ф*, соответствующие двум корням h (Ф), определяют положения максимума н минимума h (Ф). Выбираем значение Ф*, лежащее в промежутке от А до В- Чтобы избежать мнимых значений Q, следует потребовать выполнения

(16.97)

Это неравенство будет автоматически выполнено, если выбрать А к В такими, что t/i < О и ub Ю. Значение Ф, полученное таким образом, проверяется согласно (16.78). Если критерий не удовлетворен, то для аппроксимации u (Ф) используется новый кубический многочлен

h (Ф) а bФ + cФ + dФ.

(16-98)

Постоянные а. Ь, с, d вычисляются по значениям функции и ее производных в двух наилучших точках из трех - А, В и Ф*, полученных на предыдущем шаге. Если U (Ф*) <С О, то Ф* и В берутся в качестве новых А а В; в противном случае (т. е. если U (Ф*) > 0) в качестве новых А а В берутся Л н Ф*. Вычисляется новое значение Ф* и проверяется критерий сходимости аппроксимации (16.78)- Если он выполняется, процедура останавливается и в качестве Фтт берется Ф*.

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

11 зак. 2259 321

Кубическая инте;

Пд = и (с) Ua =U (0)

Vb-V (М »Л.7е Ub<0 rfo

J длина шага /1

Ua = Ub

Ub = (te) end (ortiYe)

Палучмть Ф* используя (S6%J i Ui<0

А = ф-

ua=Ui

Ug -- и (Ф") Ub U*

Па1учитъ Ф" используя (1695) и (lb 96) mtil до сходимости

Рассмотренные в этой главе идеи оптимизации и одномерная опгн мизацня используются в гл 17 18 где обсуждаются методы многомерной оптимизации

МЕТОДЫ ОПТИМИЗАЦИИ ПРЯМОГО ПОИСКА

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

17 1 МЕТОД ПОИСКА ПО ОБРАЗЦУ

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

Метод поиска по образцу [11 является улучшенным вариантом поиска «по одному за итерацию» и позволяет производить поиск вдоль уз кой долины, поскольку делается попытка ориентировать поиск вдоль долины. Этот метод включает в себя два типа перемещений в многомерном пространстве координат Ф. В начальном положении пробные перемещения делаются вдоль различных ф-осей способом «по одному за итерацию». Наилучшая точка, достигнутая таким способом, определяет направление образца по отношению к начальному положению. По на правлению образца находится минимум вдоль этого направления с по мощью одномерных методов, рассмотренных в гл 16. Последователь ность пробных перемещений и перемещений образца повторяется до достижения оптимума

Два хорошо известных метода поиска по образцу ........метод Хука и

Дживса [II и метод Пауэлла 2[ - отличаются только в выборе осей, вдоль которых осуществляется перемещение по образцу. В методе Хука и Дживса направзения образца определяются с помощью исходных Ф-осей, в то время как в методе Пауэлла множество осей для каждой последовательности перемещений по образцу модифицируется так, чтобы в результате получилось множество сопряженных направлений В работе 131 метод Хука и Дживса видоизменен для минимаксных целе вых функций, .Минимаксные целевые функции часто имеют узкую ис кривленную долину, вдоль которой лежит кривая разрыва производ ных. Модифицированный метод носит название метода лезвия. Поиск образца производится здесь тем же методом, что и в методе Хука и Дживса. Затем автоматически выбирается точка в окрестности началь ной точки образца и производится второй поиск образца Конечные точ II* 323

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

17 1 1 МЕТОД ХУКА И ДЖИВСА [!]

Как отмечалось ранее метод поиска по образцу Хука и Дживса представляет собой последовательность итераций, каждый шаг кото рой состоит из перемещений двух типов. Первый тип (называемый проб ным перемещением) осуществляется для исследования локального по ведения це-певой функции; второй, называемый перемещением по образцу, использует преимущества направления образца, найденного на пер вом шаге.

Поиск начинается из произвольно выбранной точки Ф]- [Ф,,, *t*i.ni. называемой начальной базисной точкой, и предписанной длины шага ЛФ, вдоль каждого координатного направления u; (i - I 2 ., п). Для 11ачального пробного перемещения вычисляется и (Ф) Для получения новой базисной точки каждая из перемен ных Фь , возмущается вблизи текущей базисной точки;

Ф, , f ДФ если и (Ф, + ДФ( u,) < и (ФО. Ф;,<= Фь,-АФ.. если СУ(Ф,-ДФ,и()<С(Ф,) (17.1)

Ф,,( если t/(Ф,)<min([/(Ф,-f ДФ,и,) U {Ф ДФ(и()} Процесс, описываемый (17.1), повторяется вокруг временной базисной точки для I - 1,2,..., п. Точка Ф, объявляется новой базисной точкой, а направление сбразиа s, определяется как

s, =.Ф,-Ф1 (17.2)

еслн Ф 7 Ф. Вдоль направления s, осуществляется одномерный по иск и положение минимума вдоль s, можно записать как

(17.3)

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

тах(ДФЛ<е О (17 4)

а процедура, представленная в виде алгоритма имеет вид

/Метод Хука и Дживса иф..= и(Ф);/Ф-нач; Repeat

Ub-иф

for all 1 = 1 Ion do begin

ий=и(Фь AOiUi) Ihen

begin

Фь Фь ] ДФ] 1

Ub- (/a

elbe

Ua--U(0b ДФ,и,» / Uf, < Ub then

begin

Фь Ф.

Ub и a

else Дф 4Ф, 2

end (for 1) s - - Фь Ф II sO

then

hegm

Получить л, I Ф Фь I 1ф и(Ф)

until Max (ДФ, < e und s С

17 1 3 НРТОД ПД..-»ЛЛД. (2]

ннми1ир\и)щее 1(Фь-! >.s)

Метод Пауэлла представляет собой улучшенный вариант рассмот реиного основного метода поиска по образцу Этот метод широко распространен, и можно доказать, что он является методом сопряженных направлений

Следунйцая теорема [71 помогает обнаружить сопряженные направления в методе Пауэлла. Рассмотрим квадратичную функцию размера п, и две параллельные гиперплоскости размерности k <i п обозначим цифрами 1 и 2, Пусть Ф, и - лежащие внутри области ограниче НИИ стационарные точки квадратичной функции в плоскостях I и 2