2. Методы первого и второго порядков

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

1. Градиентные методы. Метод скорейшего спуска – метод Коши

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

(12.3)

и отбросим член второго порядка и выше.

Наибольшее уменьшение значения функции будет достигнуто при выборе такого направления , которое минимизирует скалярное произведение . Из свойств скалярного произведения следует, что данное произведение примет минимальное значение при .

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

, (12.4)

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

Алгоритм метода Коши

Начальный этап. Выбрать – начальную точку и – параметр окончания счета, положить .

Основной этап.

1. Если , то , остановится.

2. Положить , вычислить , , положить и перейти к шагу 1.

Пример 12.5. Найти минимум функции методом Коши:

.

Начальный этап. Пусть , , , .

Основной этап.

1. Вычислим , так как , переходим к шагу 2.

2. Положить , вычислить , , положить и перейти к шагу 1.

3. Вычислим , так как , переходим к шагу 2.

4. Положить , вычислить , , положить и перейти к шагу 1.

Результаты вычислений приведены в табл. 12.3 и на рис. 12.7. Из таблицы следует, что значение функции становится меньше на 11-й итерации, а значение нормы градиента станет меньше только при , так как значение нормы градиента уменьшается в 5/6 раза каждые две итерации (см. табл. 12.3).

Таблица 12.3

k
1	(- ; )		(-2; 0)	2	0,05	(- ; 1)
2	(- ; 1)		(0; 1)	1	1/6	(- ; )
3	(- ; )		(- ; 0)		0,05	( )
4	( )		(0; )		1/6	( )
5	( )		( )		0,05	( )
6	( )		(0; )		1/6	( ; )
7	( ; )		( ; 0)		0,05	( ; )
	……………	……..	…………	………	……	……
11	( ; )		……..

Скорость сходимости метода Коши (это видно из примера 12.5) является довольно низкой, хотя на каждой итерации обеспечивается дополнение неравенства , причем метод позволяет, как правило, существенно уменьшить значение функции при движении из точек, расположенных на значительном расстоянии от точки минимума, т.е. на начальных шагах процесса, когда второе слагаемое в формуле (12.3), определяющее приращение функции, достаточно велико. Однако вблизи оптимальной (стационарной) точки метод Коши часто работает плохо, потому что шаги по направлению делаются маленькими (уменьшающимися). Это явление называется явлением “зигзага”. Явление “зигзага” и плохую сходимость метода Коши на последних итерациях можно объяснить, если разложение (2.3) для записывать в виде

, (12.5)

где при .

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