Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Скачать файл

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

−1 4

f (x

)

= −1 4 = −0,25 .

−

1 4

;

2-я итерация:

−1 4

)

|| f (x1 ) || ≈ 0,35 ;

1 4

−1 4

λ −1

(2)

1 4

;

−1 4 − λ

(λ +1)

−

2λ2

−2λ −4

′

f (λ) =

(4λ −2) =

0 → λ =

;

−1 8

f (x

) = −0,281.

−3 8

3-я итерация:

1 8

f (x

|| f (x

) || ≈ 0,18 ;

) =

1 8

−

(λ +

−1 8

1 8

x (3) =

− λ

;

−3 8

1 8

(λ +

−

f (λ) = 4λ2 − 2λ −18 , 64

f ′(λ) = 641 (8λ − 2) = 0 → λ = 14 ;

	3		−5 32				3
x	3				,	f (x	3	) = −0,2852 .
x		=			,	f (x		) = −0,2852 .
		−13 32
4-я итерация:
	3		−1 32						3
f (x	3					\|\| f (x			3	) \|\| ≈ 0,044	< ε .
f (x		) =	1 32	,		\|\| f (x				) \|\| ≈ 0,044	< ε .
			1 32
						61

Как видим, условие точности решения задачи выполнено; окончательно имеем:

	*		3		−5 32			*
x	*	= x	3			,	f (x	*	) = −0,2852 ,
x		= x		≈	−13 32	,	f (x		) = −0,2852 ,
					−13 32

что, с заданной степенью точности совпадает истинным решением задачи.

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

Метод сопряженных градиентов является частным случаем метода сопряженных направлений.

Вновь предположим, что f (x) – квадратичная функция вида

f (x) = a + x тb + 12 x тQx ,

где Q – положительно определенная матрица, которая в данном

случае совпадает с матрицей Гессе.

В том случае, если f (x) не является квадратичной, то Q также

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

Существуют различные варианты метода сопряженных градиентов. Одним из них является метод Флетчера – Ривса.

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

антиградиент в направление Sk , которое является	Q -сопря-
женным с ранее найденными направлениями.
Эти направления вырабатываются следующим образом:
S0 = − f (x0 ),
Sk = − f (xk ) + βk −1Sk −1 ,	(1.10)
62

λ* −

k 1

где коэффициент βk −1 выбирается так, чтобы сделать Sk						Q -сопря-
женным с Sk −1 . Иначе говоря, из условия
0 =< Sk ,QSk−1 >= − < f (xk ),QSk−1 > +βk−1 < Sk−1,QSk−1 >.
Отсюда		< f (xk ),QSk−1		>
	βk−1 =				.	(1.11)
		< Sk−1,QSk−1	>

Точка xk	находится с помощью		одномерного			поиска в
направлении Sk	из точки xk−1 , т.е.
где	xk = xk −1 + λ*k −1Sk −1 ,					(1.12)

λ*k −1	= arg(min f (xk −1 + λk −1Sk −1 )) .
	λk −1

Можно показать, что вырабатываемые с помощью данной процедуры направления S0 , S1 ,..., Sk являются Q -сопряженными.

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

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

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

f (x) = Qx + b .

Тогда, принимая во внимание итерационное соотношение (1.12), можно записать

f (xk ) − f (xk−1 ) = Q(xk − xk−1 ) = λ*k−1QSk−1 .

(1.13)

Откуда получаем

QSk −1 = f (xk ) − f (xk −1 ) .

Подставим полученное выражение в формулу (1.11) для βk −1 :

βk −1 = < f (xk ), f (xk ) − f (xk−1 ) > ,

или, раскрывая скалярные произведения и производя несложные операции, получим

βk−1 = < f (xk ), f (xk ) > −< f (xk ), f (xk−1 ) > .

<Sk−1, f (xk ) > − < Sk−1, f (xk−1 ) >

Рассмотрим каждый из занумерованных членов.

2-й член. Так как xk – точка минимума на направлении Sk −1 , то

градиент в этой точке ортогонален к направлению поиска (рис. 1.26). Откуда получаем:

< Sk−1, f (xk ) >= 0 .

Рис. 1.26. Ортогональность градиента f (xk ) и

направления S k −1

3-й член. Подставим вместо Sk −1 его выражение, определяемое формулой (3.10). Тогда получим

< Sk −1, f (xk−1 ) >=< − f (xk−1 ), f (xk −1 ) > +βk −2 < Sk −2 , f (xk −1 ) > .

Очевидно, что второе слагаемое равно нулю как скалярное произведение двух ортогональных векторов. Таким образом,

< Sk−1, f (xk−1 ) >= − < f (xk−1 ), f (xk −1 ) > .

1-й член. Выразим f (xk −1 ) в соответствии с формулой (1.10), тогда получим

< f (xk ), f (xk −1 ) >=< f (xk ),−Sk−1 +βk−2 Sk−2 >=

= − < f (xk ), Sk−1 > +βk −2 < f (xk ), Sk−2 > .

Разрешим (1.13) относительно f (xk ) и подставим в последнее выражение. Тогда получим:

< f (x ), f (x − ) >= β − < f (x − ) + λ* − QS − , S − >=

k k 1 k 2 k 1 k 1 k 1 k 2

= β − < f (x − ), S − > +β − λ* − < QS − , S − >.

k 2 k 1 k 2 k 2 k 1 k 1 k 2

Легко заметить, что получили сумму двух скалярных произведений ортогональных векторов. Таким образом,

< f (xk ), f (xk −1 ) >= 0 .

Это означает, что векторы f (xk ), f (xk−1 ) ортогональны. Вообще можно показать, что все градиенты f (x0 ), f (x1 ), ...,f (xk ) взаимно ортогональны.

Итак, в окончательном виде имеем

βk −1

< f (xk ), f (xk ) >

f (xk )

< f (xk−1 ), f (xk−1 )

f (xk −1 )

Последнюю формулу можно применять для неквадратичных функций, так как в нее не входит матрица Q .

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

xk −1 − x* ≤ c xk − x* 2 , c > 0 .

1.3.3.Методы второго порядка

1.3.3.1.Метод Ньютона (метод Ньютона – Рафсона)

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

Источник: https://studfile.net/preview/16708738/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)