где ct > О - коэффициент отражения, оп[еделяемый как отношение ра(хтояний между и Ф„ к расстоянию между Ф и Фц. Точка Ф лежит на прямой, соединякнцей Ф с Фо с другой стороны от Фе относительно Ф и Ф - Фе оф;, - Фо

Целевая функция Вычисляется в точке Ф и сравнивается со значениями Ф,, Ф к ф. Возможны следующие случав.

3) и (Ф,) < и (Ф) < и (Ф;,): 4) и (Ф) > и iФf,), согласно которым далее следуют операции. 1) отражение в новом с!1мт:лексе, 2) растяжение, 3) редукция, 4) сжатие

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

Растяжение. Если процедура отражения дает точку Ф,, для которой и (Фг) < и (Ф,), т е если отражение дает минимум, то можно ожидать, что значение функции уменьщается аце более при движении по прямой, соединяющей Ф,, сф Эта гипотеза проверяется в про-1;едуре растяжения от Ф к Ф.

Ф,, -Ф„-Г (Фо-Ф.),

(17 20)

где 7 > I - кокэфициент растяжения, определяемый как отнощение расстояний между Ф, и Ф,, к расстоянию между Ф и Ф Эта операция также отражена на рис 17 I

В точке Фр вычисляется значение целевой функции Если U (Фе)<! < и (Фг), то точку Фь заменяем точкой Ф,. и вновь начинаем процесс отражения С другой стороны, неравенство U (Ф) > U (Ф,) означает, Что растяжение оказалось неудачным, и вновь заменив точку Ф, иа Ф, приступаем к новому процессу отражения

Реаукция. Если в процессе отражения получается точка Ф. такая, что и (ф,) < (J (ф,), то отражение дает лищь незначительное улучше

/ / / X /

I I / /

Рис. i7 I Отражение, растяжение, редуяция i лсЕкным методой

ние ситуации В этом случае выполняют редукцию в направле НИН, юединяющем Ф, с Ф, чтобы проверить, не пропущена ли лучщая точка Д.1Я редукции полагаем

Ф= = Фв-Р(Фо-Фг). (1721) где р - кокэфициент редукции (О р < 1), определяемый как отношение расстояния между Фс и Фе к расстоянню между Фг и Ф„ Эта операция также отражена на рис 17 t В точке Ф,- вычистяется значение целевой функции Если и (ф) < < и (Фг), то оставляем точку Ф, которая заменяет Ф В противном случае вмкто точки Ф оставляется Фг и следующая итерация начинается с очередного отражения

Сжатие. К операций сжатия прибегают, когда отражение дает полностью неудов.1етворительный результат, т. е (/ (Ф,) > U (Фн) и отраженная точка не приносит никакой пользы для процесса минимизации Остается предположить, что минимум, вероятно, лежитвнутри симплекса Поэтому симплекс сжимается вокруг вершины с минимальным значением Ф„ преобразовывая все остальные вершины симплекса согласно

Ф,-(Ф, + Ф,) 2

П7 22)

Этог процесс в двумерном случае иллюстрируется на рис 17 2 Для нового симплекса начинается процесс отражения

Считается, что симплексный метод достиг сходимости, ем1и среднее квадратнчйкое отклонение Q функции б ;г + 1 вершине текущего симплекса меньше заданного малого значения, т е

Ц1[Ф,)-1/(Ф„)1

(17 23)

Одно из достоинсгв еимплексного метода состоит в том, что начинать его можно с достаточно большого симплекса, так что в начале работы тестир>ю7ся 1ЧЗЧКИ, пасположенаые далеко ;фуг от друга Таким образом, можно помешать симплексу сжимат1й к локальному минимуму. Крайняя гибкость размеров и формы симплекса придает интуитивное ощущение правильности симплексного метода

Приведем симплексный метод. Представленный в виде а.1гОритма

/, Снмплеисный метод

For all i-! to n-bl do Ll - ftepeai

Получись It i и 5(1,2, г-Н

Us-Max lUj)

Получить Фц используя (17 18) Получить Фр, используя (17, 19)

и,=исФг) П и,<и,

Ihen

begin ,1 рас Получить Ф

ис!10льз>я (17 20)

Ur > (Лет

Ыцхп. /I редукция

Пол1чйгь Фс, йссюльзуя (IF.2S) и,и(Фс)

*t,=*c

Ifien

else

begin

U,-t,

begin Ul,--

III -V,

tksn

Ftjr all ! n

II .1 then

u4(i/ (до СЛОДЙЫИТИ)

Различные методы оптнмизаияи. рассмотренные в данной главе, основаны на прямом поиске и не требуют вычисления градиентов. Ме тоды, основанные на вычислении граднентвв. рассматриваются в гл 18

Гла.а 18

ГРАДИЕНТНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

Прямые метюды оптимизации, рассмотренные в гл. 17, требук многократного вычисления значений целевой функции Однако производные целевой функции нигде не нспользуктся. Методы же, рассматриваемые Б данной главе, основаны на применении производных nejienoii функции и (Ф). Основная причина использования производных или

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

Здесь рассматриваются накоторые градиентные методы, применяемые прн отнмизациа схем,

181 метод нлискореишего спуска 1-3

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

Ф„1 -Ф/тК,. (18 1)

VUtФ)ф/VU(Ф)l*J. (J8.2)

т е s, задает нормированный отрицательный градиент иктора текущего значения Ф на ьй итерации Функция определена в (16 8) Длина шага получается в результате одномерного поиска вдоль направления Si.

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

(18 3) (18 4) (18 5)

На первый взгляд кажется, что метод наискорейшего спуска дол лен быть очень эффективным поскольку одномерный поиск в нем каждый раз начинается в «наилучшем» направлении Однако поскольку направление наискорейшего спус ка - свойство локальное, в действительности метод, не является эффективным при решении большинства задач Можно сказать, что его некрФктнЕНОСть является доказательством того, что хорошая локальная стратегия не обязательно хороша г.вдбально В качестве иллюстрации этого приведен рнс !8 1. нч которого

Рнс 18.1. Прииер, в котором ил правление крутого спуска ие прнблн жяет к ммнннуму

видно, что градиентное направление в Ф„ не приближает к мини муму.

Для ускорения сходимости метода наискорейшего спуска предложены многочисленные модификации Одна из них основана на использовании одномерного понска в направлении, заданном формулой

г 2.

(18 6)

вместо обычно используемого направления отрицательного градиента Направления, заданные в (18 6), обычно совпадаки с направлением на минимум, и их использование улучшает сходимость Этот метод носит название метода параллельных касательных (1-3J Приждем процедуру в виде алгоритма

/(Метод парал1ельлых карательных

Фа «-Ф;;Ф начальна и точи.,,

Пол\чнть s используя lt«2

Пол\чить К jrthhhwmihpvkiiiiee I (Ф as]

ф-ф-: >.i

Repeat

Получить s. ксиолыя \\Н 2)

Получить \*, mnhmkhshpypuiee U(* f \s)

Ф = Ф + А,*5

! Ф Фя

Фт ф

Получить к мйнняишрующео (I (Ф as) Ф Ф + Xs

until (до CXOftMMOtTMi

Методы наискорейшего спуска и 11аралле.1ьных касательных называют методами первого порядка, поскольку в них используются производные только первого порядка. Методы второго порядка подраздели ются на два типа, н которых точные значения вторых Производных используются непосредственно илн этн производные используются кос венно, за счет употребления информации предыдущих шагов Методы для этих случаев рассматриваются в разд. 18 2 и 18 3 соответственно

1Й2 обобщенный метод ньютона-РАФСОНА 4

Разложение многомерной функции в ряд Тейлора можно записать следукмцим образом

(/(Ф + ДФ) [/(Ф) -l VU- ДФ+ -ДФН(Ф)4Ф-(- . ,

(18 7)

где Н (ф)- гессиан определенный в (16 9) Рассмотрим точку в ок рестности оптимальвоя точки Фшш-

(18 8)