Методы оптимизации композиционных систем, страница 11

(5.2.1) возможно лишь в редких случаях. Цоэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями, которые, накапливаясь, могут привести к тому, что векторы р перестанут указывать направление убывания функции и сходимость метода мОжет нарушиться. Поэтому на практике в методе сопряженных градиентов через N шагов производят обновление алгоритма, полагая /?„_iV = 0,/и = 1,2,.... Номера mN называют моментами обновления метода (рестарта). Часто принимают N = п - размерности пространства Е_а. Если

N- 1, то получается частный случай метода сопряженных градиентов - метод наискорейшего спуска.

Опишем алгоритм метода сопряженных градиентов. Шаг 0. Задать парамечр точности в > 0, выбрать х° е Е_п, найти

/'ИШаг 1, Принять к = 0, р° = -f{x°).

Шаг 2. Решить задачу одномерной минимизации

f(x^k +ар^к)-> min, а > 0, т.е. найти а = а_к.

Шаг 3. Принять х^ш = х^к+а_кр^к и вычислить                         Проверить условие достижения точности:             1 < £. Если оно выполняется, то принять х° = я**¹, f'{x°) = /'(jc*⁺¹) и закончить поиск, иначе - перейти к шагу 4.

Шаг 4. Проверить условие к + ] = п. Если оно выполняется, то принять л-⁰ = x^k+l, f\x°)= f\x^k+l) и перейти к шагу 1 (рестарт), иначе - перейти к шагу 5.

Шаг 5. Вычислить коэффициент fi_k по формуле (5.19) и найти новое  направление  поиска   р^м --f'\x^k*^l)+p_kp^k.  Принять

к = к + 1 и перейти к шагу 2.

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

Пример 5.4. Методом сопряженных градиентов найти точку минимума функции J (х) = 4х² + 2>х\ - Ах_хх₂ + х_] из начальной точки х° = (0,0).

ШагО. Принимаем е = 0.01,х° = (0,0), найдем /'(x°)=(l,0).

Шаг 1. Принимаем к = 0, р° = -f{x°)=(-1,0). Шаг 2. Решим задачу одномерной минимизации

Дс° +ap^l))—> min . Получим а₀ = - (для нахождения а₀ можно

8

было воспользоваться формулой (5.4).

( 1   1     i \ ( О

Щаг 3. Найдем х¹ = х° + а₀р° = - -, 0 и f\x^l )=\0,- . ТочV   о   J                   V

ность не достигнута, перейдем к шагу 4.

Шаг 4. Условие к+1 = п не выполняется, перейдем к шагу 5.

Шаг 5. Найдем коэффициент Д, = -- и новое направление спус_Р^]=~г(х>)+ру =

Итерация 2.

Шаг 2. Решим задачу одномерной минимизации

/(л-¹ -f а/?¹)—> min. Получим а, = -

ШагЗ. Найдем *² = я¹ + щр^х = [ - ~,-\ | и /'(х²) = (0,0) - заV 16   ъ)

дача решена точно.

Таким образом, х = х². Решение получено в результате двух итераций метода сопряженных градиентов, поскольку целевая функция квадратична в Е₂ и одномерные задачи минимизации на шаге 2 алгоритма решены точно.

6. Многомерная минимизация при наличии ограничений

6.1. Задачи математического программирования

Многие практические задачи оптимизации сводятся к математическим моделям вида

f(x)-»min(max), xell,                                                        (6.1)

где допустимое множество U не совпадает со всем пространством Е_а. В этих случаях говорят об условной минимизации функции п переменных. В большинстве случаев допустимое множество U определяется ограничениями-равенствами и (или) неравенствами, т.е. рассматривается задача

/(*)-> mm(max), хеЕ„,                                                        (6.2)

&(х)<0,                                                                                    (6.3)

&(х)=0, /€/₂,                                                                           (6.4)

где /;,/₂ е {l,...,w} - заданные множества индексов. Соотношения (6.2) - (6.4) представляют собой запись условий так называемой задачи математического программирования. Отметим несколько важных частных видов таких задач.