Промышленность \ Физикохимия и механика композиционных материалов

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

шагу 1.

Пример 5.3.

Рассмотрим функцию f(x) - xf +100х2 и используем метод наискорейшего спуска для решения задачи ее минимизации из начальной точки х° =(l; l).


2х1 и-^- = 200л-7 дх*

Найдем компоненты градиента

df

и гессиан 2    О

дх.

А =

О  200

at = —

Величину шага исчерпывающего спуска найдем по формуле

(5 АО)

<-W) '

Результаты вычислений приведены в табл. 5.1.

Таблица 5.1

Номер итерации

А

4

А?)

|/'И

0

1

1

101.

200

1

9.9-1 (У1

-9.9-10"5

9.8-10"1

1.98

2

9.7-10 3

97-Ю"3

9.5-10"3

1.94

3

9.6-10"3

-9.6-10"7

9.2-I.0"5

1.92-10"2

53. Метод сопряженных градиентов

До сих пор в итерационной процедуре (5.1) в качестве направления убывания функции f(x) мы использовали направление антиградиента рк = -/'(**). Однако такой выбор направления убывания не всегда бывает удачным. В частности, для плохо обусловленных задач минимизации направление антиградиента в точке хк может значительно отличаться от направления к точке минимума х . В результате траектория приближения к точке минимума имеет зигзагообразный характер (см. пример 2 разд. 5.1).

Опишем метод, позволяющий получить сопряженные направления для квадратичной функции f(x) с применением ее

производных

В этом методе используют итерационный процесс

хк+1=хк + акрк,к = 0,1,...;*° € К,!7р° =-/{/>),           (5.11)

в котором величину шага ак находят из условия исчерпывающего спуска по направлению рк. После вычисления очередной точки хк+\ it=0,1,... новое направление поиска pk+l определяют по формуле

^=_Г(^)+д/д=0Л,..,                                                                   (5-12)

где коэффициенты Д выбирают так, чтобы при минимизации квадратичной функции f(x) с положительно определенной матрицей А получалась последовательность А - ортогональных векторов р ,/?',... .

Из условия Lipk+X,рк) = ® имеем

Напомним, что для квадратичной функции шаг исчерпывающего спуска по направлению р

а,. = —

</'И/>

(5.14)


Можно показать, что процесс (5.11) (5.14) минимизации квадратичной функции с положительно определенной симметрической матрицей А дает: точки х°,...ух* и векторы р°,...,/>* такие, что если /'(х')фО при 0<i<k<n-\, то векторы р°9...9рк А - ортогональны, а градиенты f'(x°),..., f'(x') взаимно ортогональны.

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

С учетом взаимной ортогональности градиентов f'(x') и условий исчерпывающего спуска по направлениям рк можно упростить выражения (5.13) и (5.14). Выразим числитель дроби (5.14)

</'(** ]рк) = {fix1 \ - f'{xk ) + Д_, - ркА) =

-wt+^sh'^wi     (515)

Умножив обе части равенства (5.11) слева на матрицу А и прибавив к ним по вектору Ь, получим

/V)-ГИ+МР* ■                                                                                                                           (5Л6)

С учетом формулы (5.16) упростим числитель в выражении (5.13) для Д следующим образом:

(Ar(S*\,?).(f{S"W)у                                       /     «*

В результате выражения для вычисления ак и Д примут вид

(5.18)

ш

а,

A-£V4-                                                                    <519>

Выражение (5.19) для коэффициента Д не содержит в явном виде матрицу А квадратичной функции. Поэтому метод сопряженных градиентов можно применять и для минимизации неквадратичных функций. В этом случае итерационный процесс метода описывают соотношения:

хш=хк +акРк\ х° е Еп, р° = - f'(x°\ к. =0,1,..., (5.20) f(xk + акрк)= mm f(xk + арк\ £ =0,1,...,                      (5.21)

!/'И

А =

рш =                                к = 0,1,...,                                      (5.22)

к-\, 2,....                                                     (5.23)

Скачать файл