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

Рис. 1.14. Блок-схема метода покоординатного спуска с удвоением шага

Задача 2. Найти методом покоординатного спуска с одномерной минимизацией по каждой координате минимум функции

f (x) = x12 + x22 − 4x1 +5

с точностью ε = 0,01.

41

Решение. Схему решения задачи можно представить в виде следующей последовательности действий.

Выберем начальную точку с координатами: x10 =1, x20 =1.

Значение целевой функции, соответствующее этой точке f 0 = 4 .

Цикл k = 0 . Итерация i =1:

Итерация i = 2 :

x1 = 2;

x2 −меняется,

необходимо найти min{f (x2 ) = x22 +1}.

x2

Из условия экстремума:

∂∂xf2 = 2x2 = 0 → x2 = 0 .

x1 − меняется;

x2 = 0.

42

Очевидно, целевая функция в этом случае принимает вид:

{ f (x1 ) = x12 − 4x1 +5}.

Минимум этой функции достигается при x1 = 2 , а само

Линии уровня, соответствующие рассматриваемой функции приведены на рис. 1.15.

Рис. 1.15. Линии уровня функции

f (x) = x12 + x22 −4x1 +5

1.3.1.2. Метод ортонормальных направлений (метод Розенброка)

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

43

Рассмотрим процедуры, выполняемые на k -м цикле метода. Пусть в начале цикла имеется точка x0k , числа λ1 , λ2 , …, λn –

x0k остается без изменений, а величина λ1 умножается на число β

x0k и совокупность шагов λ1 , λ2 , …, λn тоже новая. Затем снова

βλ1 в зависимости от того, успешным или неуспешным был шаг до

этого.

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

Второй этап цикла состоит в выборе исходных данных для следующего цикла.

В качестве начальной точки следующего цикла x0k +1 берется последняя успешная точка.

В качестве шагов λi , i =1, n, – последние получившиеся значения. После этого выбираются новые направления.

44

Строится система векторов:

здесь Λi – алгебраическая сумма длин успешных шагов по i-му

направлению.

Если изобразить условно направления на плоскости, то получим схему, показанную на рис. 1.16.

Рис. 1.16. Графическое представление метода Розенброка на одной из итераций

Как видно из рисунка, вектор q1 соединяет точку, в которой

процесс находился в начале цикла, с точкой, в которую он попал в конце цикла.

Данная система векторов q1 ,…, qn ортогонализируется с

помощью процедуры Грама – Шмидта.

В качестве начального (первого) направления принимается q1

(так как это направление располагается вдоль предполагаемого гребня функции).

Процедура ортогонализации Грама – Шмидта. Пусть имеем n

векторов q1 , …, qn . Необходимо получить n единичных