Основы теории оптимизации (стр. 76 )

  2) (исследующий поиск) x2 = -4, дадим приращение x1.

  (-3;-4)  f(-3;-4) = 200  (удачно)

фиксируем x1 = -3, дадим приращение x2.

  (-3;-3)  f(-3;-3) = 153  (удачно)

базовая точка x(1) = [-3;-3];  f(x(1)) = 153.

  3) (поиск по образцу)

  xp(2) = x(1)+(x(1)-x(0)) = [-2;-2]

  f(xp(2)) = 68

  4) (исследующий поиск)

  x(2) = [-1;-1]

  f(x(2)) = 17 < f(x(1))  (удачно)

x(2) - базовая точка для проведения посика по образцу.

  5) xp(3) = x(2)+(x(2)-x(1)) = [0;0]  (минимум)

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

Недостатки: алгоритм основан на циклическом движении по координатам. Это может привести к вырождению алгоритма в бесконечную последовательность исследующих поисков без поиска по образцу.

Метод сопряжённых направлений Пауэлла

Ориентирован на исследование квадратичных функций. Подходит также и для других функций после разложения в ряд Тейлора в окрестности точки оптимума.

Основная идея: если квадратичную функцию n переменных привести к виду суммы полных квадратов, то её оптимум может быть найден в результате n одномерных поисков по преобразованным координатным направлениям.

Процедура преобразования квадратичной функции

К виду суммы полных квадратов эквивалентна нахождению такой матрицы преобразования T, которая приводит матрицу квадратичной формы xTCx к диагональному виду. Квадратичная форма Q(x) = xTCx путём преобразования x=Tz приводится к виду:

Q(x) = zTDz,

где D - диагональная матрица.

x = Tz = t1z1+t2z2+...+tNzN,

то есть вместо координат вектора x в стандартной координатной системе используются его координаты в новой системе, задаваемой векторами tj. Поскольку t совпадают с главными осями квадратичной формы, то матрица D диагональна.

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

Метод сопряжённых направлений Пауэлла

Пример.

f(x) = 4x12+3x22-4x1x2+x1

 x2 = z2.

(к сумме полных квадратов)

f(z) = 4z12+2z22+z1+1/2(z2 )

x(0) = [0;0]  t1 = [1;0]  t2 = [1/2;1]

  (столбцы преобразований)

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

f(x(1) = x(0)+l(1)t1) → min

x(1) = x(0)+l(1)t1 = [-1/8;0]

Из x(1) проводим поиск в направлении t2.

f (x(1)+l(2)t2) →min

x(2) = x(1)+l(2)t2 = [-3/16;-1/8]

  Таким образом, остаётся открытым вопрос о построении системы векторов tj, вдоль которой осуществляется поиск. Она называется системой сопряжённых направлений.

Пусть C - симметричная матрица n×n. Направления S(1), S(2), ... , S(r), где r n называются C-сопряжёнными, если они линейно-независимы и выполняются равенства:

  S(i)TCS(j) = 0  i≥j

Для построения системы сопряжённых направлений будем использовать свойства параллельного подпространства.

Пусть задана квадратичная функция f(x), две произвольные, несовпадающие точки x(1) и x(2) и направление d. Если точка y(1) минимизирует функцию f(x(1)+l1d), а точка y(2) минимизирует функцию f(x(2)+l2d), то направление y(2)-y(1) является сопряжённым с d.

Для построения системы сопряжённых направлений лучше использовать [0;0] и систему координатных векторов. Рассмотрим x(0), e(1) = [1,0], e(2) = [0,1]. Найдём значение l(0), которому соответствует минимум

  f(x(0)+l(0)e(1))

  x(1) = x(0)+l(0)e(1)

Найдём l(1), которому соответствует минимум

  f(x(1)+l(1)e(2))

и точку

  x(2) = x(1)+l(1)e(2)

Найдём l(2), которому соответствует минимум

  f(x(2)+l(2)e(1))

и точку

  x(3) = x(2)+l(2)e(1)

x(3)-x(1) сопряжено с e(1). По этим двум направлениям и производим поиск.

Метод сопряжённых направлений Пауэлла

Алгоритм метода.

1. Задать x(0), e(1), e(2), ... , e(п)

2. Минимизировать f(x) при последовательном движении по n+1 направлению. При этом полученная ранее точка минимума берётся в качестве исходной, а направление S(п) используестся как при первом, так и при последнем поиске.

3. Определить новое сопряжённое направление по свойствам параллельного подпространства.

4. Заменить S(1) на S(2) и т. д., S(п) заменить новым сопряжённым направлением и goto 2. Провести всё это п2 раз.

Алгоритм работает, если функция квадратична.

  Пример.

f(x) = 2x13+4x1x23-10x1x2+x22

  1) x(0) = [5;2];  f(x(0)) = 314;

  S(1) = [1;0];  S(2) = [0;1]

2) Найдём l, при котором

f(x(0)+lS(2)) →min

  l= -0.81

x(1) = x(0)+lS(2) = [5;2]-0.81[0;1] = [5;1.19]

f(x(1)) = 250

В направлении S(1):

l: f(x(1)+lS(1)) →min

l= -3.26

x(2) = x(1)+lS(1) = [1.74;1.19]

f(x(2)) = 1.1

  l: f(x(2)+lS(2)) →min

l= -0.098

x(3) = [1.74;1.092]

f(x(3)) = 0.72

3) x(3)-x(1) = S(3) (сопряжённое с x(2))

  S(3) = [-3.26;-0.098]

 

  (пронормировали)

4) S(1) исключаем, S(1) = S(2), S(2) = S(3).

Теперь найдём

l: f(x(3)+lS(2)) →min

l= 0.734

x(4) = x(3)+lS(2) = [1.006;1.07]

f(x(4)) = -2.86

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

7.2. Анализ методов первого и второго порядков

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

,

где   x(k) - текущее приближение к решению;

  S(k)(x) или S(k) - направление поиска;

 α(k) - параметр, характеризующий длину шага в направлении S(k) .

Градиентные методы различаются только способом определения α(k) и S(k). α(k) обычно определяется путём решения задачи оптимизации f(x) в направлении S(k). Направление S(k) зависит от того, как аппроксимируется функция f(x).

Метод Коши

Пусть в точке  требуется определить направление наискорейшего спуска (то есть направление наибольшего локального уменьшения f(x) ). Разложим f(x) в ряд Тейлора в окрестности точки  и отбросим члены второго порядка по ∆х и выше.

Локальное уменьшение f(x) определяется вторым слагаемым, то есть наибольшее уменьшение f(x) будет тогда, когда  будет иметь наибольшую отрицательную величину. Этого можно добиться выбором S(k): , тогда второе слагаемое примет вид: .

Этот случай соответствует наискорейшему локальному спуску .

Недостатки:

·  остаётся вопрос выбора α;

·  вблизи точки минимума медленно сходится, так как →0.

α будем находить путём минимизации функции f(x(k+1)) в направлении -.

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