2.1.3. Метод Розенброка

Метод Розенброка является итерационной процедурой, имеющей некоторое сходство с исследующим поиском Хука и Дживса. Отличие состоит в том, что с помощью дискретных шагов или одномерной оптимизации поиски осуществляются вдоль системы ортонормированных направлений S₁^(k), …, S_n^(k), полученных при помощи процедуры Грама-Шмидта.

На первой итерации процесс поиска из начального приближения X⁽¹⁾ осуществляется вдоль координатных осей. Результатом этого процесса будет точка X⁽²⁾. После этого происходит смена направлений. Причем единичный вектор направления совпадает с вектором перехода изX⁽¹⁾ в X⁽²⁾, а достраивается ортогонально к. В общем случае набор ортонормированных векторовна (k+1)-м этапе вычисляется при помощи следующих соотношений

;

;

;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

;

,

где ||a_i|| - нормаa_i, являющаяся вектором перехода изX^(k)вX^(k+1)по направлениям.

Векторы a_i рассчитываются по формуле:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

где - величина шага, равная переходу изX^(k)вX^(k+1)по направлениям.

Алгоритм метода Розенброка с минимизацией по направлению.

Начальный этап. Пусть   0 - скаляр, используемый в критерии остановки. Выбрать в качестве координатные направления, начальную точку X⁽¹⁾, положить Y⁽¹⁾ = X⁽¹⁾, k = j = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Найти _j^* - оптимальное решение задачи минимизации f(Y^(j) + _j) и положить Y^(j+1) = Y^(j) + _j^*. Если j  n, то заменить j на j + 1 и вернуться к шагу 1. В противном случае перейти к шагу 2.

Шаг 2. Положить X^(k+1) = Y⁽ⁿ⁺¹⁾. Если ||X^(k+1) - X^(k)||  , то остановиться; в противном случае положить Y⁽¹⁾ = X^(k+1), заменить k на k + 1, положить j = 1 и перейти к шагу 3.

Шаг 3. Построить новое множество линейно независимых и взаимно ортогональных направлений в соответствии с (2.5) и (2.6). Обозначить новые направления через и вернуться к шагу 1.

Алгоритм метода Розенброка с дискретным шагом.

Начальный этап. Выбрать число   0 для остановки алгоритма, коэффициент растяжения   1 и коэффициент сжатия   (-1, 0). Взять в качестве координатные направления и выбрать ₁, …, _n  0 начальную длину шага вдоль каждого из направлений. Выбрать начальную точку X⁽¹⁾, положить Y⁽¹⁾ = X⁽¹⁾, k = j = 1. При этом X^(k) - координаты минимальной точки на k-той итерации, Y^(j) - координаты точки на j-том шаге каждой итерации. Перейти к основному этапу.

Основной этап. Шаг 1. Если f(Y^(j) + _j)  f(Y^(j)), то шаг по j-му направлению считается “успешным”. Положить Y^(j+1) =Y^(j) + _j и заменить _j на _j. Если же f(Y^(j) + _j)  f(Y_j), то шаг считается “неудачным”. Положить Y^(j+1) = Y^(j) и заменить _j на _j. Если j  n, то заменить j на j + 1 и вернуться к шагу 1. В противном случае, т.е. при j = n перейти к шагу 2.

Шаг 2. Если f(Y⁽ⁿ⁺¹⁾)  f(Y⁽¹⁾), т. е. если хотя бы один спуск по направлению при шаге 1 оказался успешным, положить Y⁽¹⁾ = Y⁽ⁿ⁺¹⁾, j = 1 и повторить шаг 1. Пусть f(Y⁽ⁿ⁺¹⁾) = f(Y⁽¹⁾), т.е. каждый из n последних спусков по направлению на шаге 1 был неудачным. Если f(Y⁽ⁿ⁺¹⁾)  f(X^(k)), т.е. по крайней мере один удачный спуск встретился в течении k-й итерации на шаге 1, то перейти к шагу 3. Если f(Y⁽ⁿ⁺¹⁾) = f(X^(k)), т.е. не было не одного удачного спуска по направлению, то остановиться. При этом X^(k) является приближенным оптимальным решением, если |_j|   для всех j. В противном случае положить Y⁽¹⁾ = Y⁽ⁿ⁺¹⁾, j = 1 и перейти к шагу 1.

Шаг 3. Положить X^(k+1) = Y⁽ⁿ⁺¹⁾. Если ||X^(k+1) - X^(k)||  , то остановиться; X^(k+1) - приближенное оптимальное решение. В противном случае вычислить ₁,  …, _n из соотношения построить новые направления, обозначить их через положитьY⁽¹⁾ = X^(k+1), заменить k на k + 1 положить j = 1 и перейти к шагу 1.

Дискретные шаги выбираются вдоль n направлений поиска на шаге 1. Если движение вдоль S_j оказалось успешным, то _j заменяется на _j, если же на этом направлении постигла неудача, то _j заменяется на _j. Так как   0, то неудача приводит к сдвигу в обратном направлении вдоль j-го вектора на следующей реализации шага 1. Шаг 1 повторяется до тех пор, пока неудача будет иметь место при спуске по каждому направлению поиска. В этом случае строятся новые направления поиска.

Пример расчета экстремума функции методом Розенброка с дискретным шагом.

Постановка задачи. Минимизировать f(X) = (x₁ - 2)⁴ + (х₁ - 2х₂)² с точностью =0,01. Эта функция имеет минимум в точке X^* = [2 1]^Т, где f(X) = 0. Выбираем начальное приближение X⁽¹⁾ = [2.5 2.5]^Т и параметры алгоритма: ₁ = ₂ = 0,5;  = 3;  = 0,5; направления начального поиска совпадают с координатными осями = [1 0]^Т, = [0 1]^Т.

Исследующий поиск.

Вычислим f(Y⁽²⁾) в точке 2

Y⁽²⁾ = 

Здесь f(Y⁽²⁾) = 5,0, т.е. имеет место “удача”, поэтому шаг по х₁ увеличивается ₁ = 30,5 =1,5. Затем вычисляем f(Y⁽³⁾) в точке 3

Y⁽³⁾ = 

Здесь f(Y⁽³⁾) = 10,0, т. е. “неудача”, поэтому шаг по х₂ уменьшается и направление изменяется на противоположное ₂ = -0,50,5 = -0,25.

При наличии одной “удачи” поиск продолжаем. Считаем Y⁽¹⁾ = Y⁽³⁾.

Вычисляем f(Y⁽²⁾) в точке 4

Y⁽²⁾ = 

Здесь f(Y⁽²⁾)=39,31, что говорит о “неудаче”, поэтому величина шага уменьшается ₁ = -1,50,5 = -0,75.

Рассчитываем f(Y⁽³⁾) в точке 5

Y⁽³⁾ = 

Здесь f(Y⁽⁵⁾) = 3,25. Следовательно, шаг является успешным, ₂ = 30,25 = 0,75

Поиск продолжается аналогичным образом до 9 точки. На этом первый исследующий поиск заканчивается, т. к. два последних расчета 8 и 9 неудачны. В качестве результата принимается координата [3 1,5] 7 точки, которая обозначается за X⁽²⁾ = Y⁽¹⁾.

Построение новых направлений поиска. Новое направление совпадает с вектором перехода изX⁽¹⁾ в X⁽²⁾, а достраивается ортогонально к. Рассчитаем единичные направленияпо формуле (2.5), а векторыа₁⁽¹⁾ и а₂⁽¹⁾ по формуле (2.6).

Определяем составляющие шага где перехода изX⁽¹⁾ = [2.5 2.5]^Т в X⁽²⁾ = [3 1,5]^Т. =3-2,5=0,5, =1,5-2,5=-1

Находим компоненты векторов

а₁⁽¹⁾ = 0,5;а₂⁽¹⁾ = -1;

Рассчитываем направления и

=[0,45-0,89]^T

b₂⁽¹⁾=;

На этом завершена первая итерация метода. Точка с 10 по 13 соответствуют результатам исследующего поиска на второй итерации. После 16 итераций получается следующий результат: X^(*) = [1,99959 0,99979]; f(X^(*)) = 0,28510^‑13, что указывает на высокую эффективность метода. Результаты расчетов двух итераций метода с использованием табличного процессора EXСEL представлены в таблице 2.3. Траектория поиска приведена на рис.2.3.

Таблица 2.3

Расчет минимума функции f(X) = (x₁ - 2)⁴ + (х₁ - 2х₂)² методом Розенброка.

1. Исследующий поиск
№	x1	x2	s1	s2	f(x)
1	2.50	2.50			6.313
2	3.00	2.50	0.50	0.00	5.000
3	3.00	3.00	0.00	0.50	10.000
4	4.50	2.50	1.50	0.00	39.313
5	3.00	2.25	0.00	-0.25	3.250
6	2.25	2.25	-0.75	0.00	5.066
7	3.00	1.50	0.00	-0.75	1.000
8	3.38	1.50	0.38	0.00	3.715
9	3.00	-1.25	0.00	-2.25	31.250
1. Поворот осей
	x1	x2	||R||	f(x)
	3.00	1.50		1.000
λ	0.50	-1.00
a1	0.50	-1.00	1.118
a2	0.00	-1.00	1.000
b2	-0.4	-0.21	0.452
S1	0.45	-0.89
S2	-0.8854	-0.465
2. Исследующий поиск в новой системе координат
№	x1	x2	s1	s2	f(x)
	3.00	1.50			1.000
1	3.22	1.05	0.22	-0.45	3.492
2	2.56	1.27	-0.44	-0.23	0.097
3	2.45	1.49	-0.11	0.22	0.328
4	1.23	0.57	-1.33	-0.70	0.361

На второй итерации метода реализован исследующий поиск с помощью дискретных шагов в новой системе координат. Из таблицы видно, что на шаге 3 и 4 происходит «неудача». Поэтому оптимальной точкой исследующего поиска будет точка 2 [2.56; 1.27]. В этой точке опять производится поворот координатных осей, и процедура расчета повторяется.