Численные методы безусловной оптимизации. Метода параллельных касательных, метод Пауэлла

Описание алгоритма

Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:

приводится к виду сумма полных квадратов

то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.

В методе Пауэлла поиск реализуется в виде:

вдоль направлений, называемых -сопряженными при линейной независимости этих направлений.

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

Шаг 1. Задать исходные точки, и направление. В частности, направление может совпадать с направлением координатной оси;

Шаг 2. Произвести одномерный поиск из точки в направлении получить точку, являющуюся точкой экстремума на заданном направлении;

Шаг 3. Произвести одномерный поиск из точки в направлении получить точку;

Шаг 4. Вычислить направление;

Шаг 5. Провести одномерный поиск из точки (либо) в направлении c выводом в точку.

Нахождение минимума целевой функции методом сопряжённых направлений Пауэлла.

Целевая функция:

Начальная точка:

Значение целевой функции в этой точке:

Шаг 1. Зададим исходные точки S(1) и S(2):

S(1) = S(2) =

Шаг 2. Найдем значение, при [Х(0)+2S(2)]. Произвольная точка на луче из точки Х(0) в направлении S(2) определяется как

Х = Х(0) + S(2) = [-9;-10] +

откуда X 1 = -9 X 2 = - 10

Отсюда находим:

X(1) = [-9;-10] + 15.5 = [-9;5.5]

Аналогично найдем значение, при [Х(1)+S(1)].

Х = Х(1) + S(1) = [-9;5.5] +

откуда X1 = -9 X2 =5.5

Подставляя эти значения в целевую функцию, получаем

Дифференцируем это выражение по и приравниваем нулю:

Отсюда находим:

X(2) = [-9;5.5] + 10.5 =

Также найдем значение, при [Х(2)+2S(2)].

Х = Х(2) + S(2) = +

откуда X 1 = 3 X 2 = 5.5+

Подставляя эти значения в целевую функцию, получаем

Дифференцируем это выражение по и приравниваем нулю:

Отсюда находим:

X(3) = -6 =

Шаг 3. Положим

S(3) = X(3) - X(1) =

Направление S(3) оказывается сопряженным с направлением S(2). Поскольку N = 2, то оптимизация вдоль направления S(3) дает искомый результат. Шаг 4. Найдем такое значение, при

X = X(3) + = +

X 1 = 3+ 12 X 2 = -0.5 -6

Х(4) = +0.0278* =

Таким образом, получили точку х= T , значение функции в которой f(x) = -3,778, совпадает со стационарной точкой.

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

Графическое пояснение метода сопряженных направлений Пауэлла:

Методы прямого поиска являются удобными при простых целевых функциях, или когда необходимо найти оптимум с невысокой степенью точности. Но требуют больших затрат времени и вычислительных ресурсов, из-за большого числа проводимых итераций: метод поиска по симплексу - 15 итераций, метод Хука-Дживса - 5 итераций, метод сопряженных направлений Пауэлла - 4 итерации.

Этот метод основан на последовательном применении процедуры оценивания с использованием квадратичной аппроксимации.

Назначение сервиса . Онлайн-калькулятор предназначен для нахождения минимума функции методом Пауэлла (см. также калькулятор для двух переменных). Решение оформляется в формате Word .

Правила ввода функций :

Схема алгоритма Пауэлла

Пример . Найти .
Пусть начальная точка x 1 =1 и длина шага Δx=1.
Критерии останова:

Замечание. Оба критерия должны выполняться одновременно.
Итерация 1:
Шаг 1: x 2 =x 1 + Δx =2
Шаг 2: f(x 1)=18; f(x 2)=16
Шаг 3: f(x 1)>f(x 2), следовательно x 3 =1+2 = 3;
Шаг 4: f(x 3)=23.33;F min =16; X min =x 2 .
Шаг 5:

Вычислим :

Шаг 6: Проверка на окончание поиска:
а) . Критерий останова не выполняется, следовательно поиск продолжается. Переход на Шаг 7.
Шаг 7: Выбираем как "наилучшую" точку, а x 1 =1, x 2 =2 – как точки, которые ее окружают. Обозначим эти точки в естественном порядке и переходим к Шагу 4.
Итерация 2:
Шаг 4: x 1 =1; f 1 =18; x 2 =1.714, f 2 =15.21 = F min ;
X min = x 2 = 1.714, x 3 = 2; f 3 = 16
Шаг 5:


Шаг 6: Проверка на окончание поиска: а) .
Первый критерий останова не выполняется. Переход на Шаг 7.
Шаг 7: Выбираем как "наилучшую" точку, а x 1 = 1, x 2 = 1,714 – как точки, которые ее окружают. Обозначим эти точки в естественном порядке и переходим к Шагу 4.
Итерация 3:
Шаг 4:
x 1 = 1, f 1 = 18; x 2 = 1.65; f 2 = 15.142; = F min ; X min = x 2 = 1.65
x 3 = 1.174; f 3 = 15.21
Шаг 5:


Шаг 6: Проверка на окончание поиска:
а) б)
Оба критерия останова выполняются, следовательно, поиск закончен.
Ответ: (точное решение x=1.5874).

Рассмотрим задачу о нахождении максимума квадратичной функции

где и – -мерные векторы евклидова пространства , – положительно определенная квадратичная форма, задаваемая матрицей .

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

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

1. Рассмотрим сначала процесс, отнюдь не являющийся алгоритмом для нахождения минимума квадратичной функции, но из которого легко следуют весьма эффективные алгоритмы – метод сопряженных градиентов и метод параллельных касательных.

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

Найдем точку , в которой достигается условный максимум функции на прямой . Продолжим это построение по индукции. Пусть уже построено -мерное гиперпространство и в нем найдена точка , в которой функция достигает условного максимума.

Обозначим градиент функции в точке . Примем, далее, за гиперпространство пространство, натянутое на и прямую, проходящую через в направлении . Пространство состоит из векторов вида

где , а скаляр пробегает значения от до .

Наконец, – это точка, в которой достигает условного максимума на пространстве . Таким образом, получаем такие последовательности:

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

,

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

2. Из анализа известно, что если гладкая функция достигает условного экстремума на некотором гиперпространстве в точке , то градиент функции в этой точке ортогонален гиперпространству. Применительно к нашему построению отсюда следует, что ортогонален всякому вектору вида , где и принадлежат , т. е.

при . (16.2)

В частности, векторы и при принадлежат в силу (16.1), откуда

а следовательно, и вообще

При . (16.3)

Отсюда следует, что если , то вектор невыразим линейно через и поэтому пространство имеет размерность на 1 большую, чем .

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

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

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

3. Для обоснования этого положения установим следующие факты. Обозначим через вектор , т. е. смещение от условного максимума в , к условному максимуму .

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

. (16.5)

Отсюда ясно, что и (16.4) верно. Из (16.5) также следует, что

б) Векторы и при ортогональны относительно матрицы , т. е.

При . (16.6)

Поскольку матрица симметрична,

.

.

После очевидного преобразования получим

Окончательно,

в) Система векторов линейно независима, т. е. не существует чисел , не все из которых равны нулю, таких, что

В самом деле, предположим противное, и пусть, например, . Тогда

где положено

Умножая справа и слева это равенство на , получим в силу (16.6)

но это невозможно, поскольку (утверждение а)) и квадратичная форма положительно определена.

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

. (16.7)

Это утверждение можно доказать и непосредственно по индукции. Для утверждение очевидно, так как всякая точка прямой может быть представлена и в виде , если учесть, что , так же как и , лежит на этой прямой и . В общем случае предположим, что (16.7) верно для , т. е. всякий вектор вида может быть заменен поиском максимума на плоскости или на прямой.

Шаг 1. Задать начальную точку х (0) и систему N линейно независимых направлений; возможен случай, когда s (i) = e (i) i = 1, 2, 3,..., N.

Шаг 2. Минимизировать f(x) при последовательном движении по (N +1) направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s (N) используется как при первом, так и последнем поиске.

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

Ш а г 4. Заменить s (l) на s (2) и т. д. Заменить s (N) сопряженным направлением. Перейти к шагу 2.

Для того чтобы применить изложенный метод на практике, его необходимо дополнить процедурами проверки сходимости и линей­ной независимости системы направлений. Проверка линейной неза­висимости особенно важна в тех случаях, когда функция f(x) не является квадратичной .

Из способа построения алгоритма следует, что в случае, когда целевая функция квадратична и обладает минимумом, точка минимума находится в результате реализации N циклов, включающих шаги 2, 3 и 4, где N - количество переменных. Если же функция не является квадратичной, то требуется более чем N циклов. Вместе с тем можно дать строгое доказательство того, что при некотором предположении метод Пауэлла сходится к точке локального мини­мума с суперлинейной скоростью (см. данное ниже определение).

Скорость сходимости. Рассматриваемый метод позволяет построить последовательность точек х (k) , которая сходится к решению x*. Метод называется сходящимся, если неравенство

≤ 1, где (3.39)

= x – х* , (3.40)

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

, (3.41)

где С - постоянная величина. Из формулы (3.39) следует, что при r = 1имеет место неравенство С ≤ 1. Если r = 1или r = 2, то алгоритм характеризуется линейной или квадратичной скоростью сходимости соответственно. При r = 1и С = 0 алгоритм характеризуется суперлинейной скоростью сходимости.

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

Найти точку минимума функции

f(x) = 2x + 4x x – 10x x + x ,

если задана начальная точка х (0) = T , в которой f (x (0)) = 314.

Шаг 1. s (1) = T , s (2) = T .

Шаг 2. (а) Найдем такое значение λ, при котором

f (x (0) + λs (2)) → min.

Получим: λ* - 0,81, откуда

x (l) = T - 0,81 T = T , f (x (l)) = 250.

(б) Найдем такое значение λ, при котором f (x (1) + λs (1)) → min.

λ* = – 3,26, x (2) = T , f (x (2)) = 1.10.

(в) Найдем такое значение λ, при котором f (x (2) + λs (2)) → min.

λ* = – 0.098, x (3) = T , f (x (3)) = 0.72.

Шаг 3. Положим s (3) = х (3) - x (1) = [-3.26,-0.098] T . После нормировки получим

s (3) = = [– 0,99955, – 0,03] T .

Положим s (1) = s (2) , s (2) = s (3) и перейдем к шагу 2 алгоритма.

Шаг 4. Найдем такое значение λ, при котором f (x (3) + λs (2)) → min.

λ* = – 0.734, x (4) = T , f (x (4)) = – 2,86.

Примечание. Если бы f(x) была квадратичной функцией, то полученная точка являлась бы решением задачи (если пренебречь ошибкой округления). В данном случае итерации следует продолжить до получения решения.

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

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

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

Градиентные методы

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

f(x) = 2x + 4x x – 10x x + x

Рис. 3.13. Решение задачи из примера 3.6 по методу сопряженных направлений Пауэлла.

С другой стороны, при использовании даже самых эффективных прямых методов для получения решения иногда требуется чрезвычайно большое количество вычислений значений функции. Это обстоятельство наряду с совершенно естественным стремлением реализовать возможности нахождения стационарных точек [т. е. точек, удовлетворяющих необходимому условию первого порядка (3.15а)] приводит к необходимости рассмотрения методов, основанных на использовании градиента целевой функции. Указанные методы носят итеративный характер так как компоненты градиента оказываются нелинейными функция­ми управляемых переменных.

Далее везде предполагается, что f(х), f(x) и f(x) существуют и непрерывны. Методы с использованием как первых, так и вторых производных рассматриваются лишь кратко и главным образом в их связи с более полезными методами. Особое внимание уделяется подробному изложению методов сопряженных градиентов, в основе которых лежит введенное выше понятие сопряженности направлений, и так называемых квазиньютоновских методов, которые анало­гичны методу Ньютона, но используют лишь информацию о первых производных. Предполагается, что компоненты градиента могут быть записаны в аналитическом виде или с достаточно высокой точ­ностью вычислены при помощи численных методов. Кроме того, рассматриваются способы численной аппроксимации градиентов." Все описываемые методы основаны на итерационной процедуре реализуемой в соответствии с формулой

x = x + α s (x ) (3.42)

где x - текущее приближение к решению х*; α - параметр характеризующий длину шага; s (x ) = s - направление поиска в N-мерном пространстве управляемых переменных x i , i = 1, 2, 3,..., N .Способ определения s(x) и α на каждой итерации связан с особенностями применяемого метода. Обычно выбор α осуществляется путем решения задачи минимизации f(x) в направлении s (x ). Поэтому при реализации изучаемых методов необходимо использовать эффективные алгоритмы одномерной минимизации.

3.3.1. Метод Коши

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

f(x) = f ()+ f() ∆x+ … (3.43)

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

s () = – f(), (3.44)

и второе слагаемое примет вид

–α f () f ().

Рассмотренный случай соответствует наискорейшему локальному спуску. Поэтому в основе простейшего градиентного метода лежит формула

x = x – α f (x ), (3.45)

где α - заданный положительный параметр. Метод обладает двумя недостатками: во-первых, возникает необходимость выбора подходящего значения α, и, во-вторых, методу свойственна медленная сходимость к точке минимума вследствие малости f в окрестности этой точки.

Таким образом, целесообразно определять значение α на каждой итерации

x = x – α f (x ), (3.46)

Значение α вычисляется путем решения задачи минимизации f (x (k +1)) вдоль направления f (x ) с помощью того или иного метода одномерного поиска. Рассматриваемый градиентный метод носит название метода наискорейшего спуска, или метода Коши, поскольку Коши первым использовал аналогичный алгоритм для решения систем линейных уравнений.

Поиск вдоль прямой в соответствии с формулой (3.46) обеспечивает более высокую надежность метода Коши по сравнению с про­стейшим градиентным методом, однако скорость его сходимости при решении ряда практических задач остается недопустимо низкой. Это вполне объяснимо, поскольку изменения переменных непосредственно зависят от величины градиента, которая стремится к нулю в окрестности точки минимума, и отсутствует механизм ускорения движения к точке минимума на последних итерациях. Одно из глав­ных преимуществ метода Коши связано с его устойчивостью. Метод обладает важным свойством, которое заключается в том, что при достаточно малой длине шага итерации обеспечивают выполнение неравенства

f (x ) ≤ f (x ). (3.47)

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

Пример 3.7. Метод Коши

Рассмотрим функцию

f(x) = 8x + 4x x + 5x

и используем метод Коши для решения задачи ее минимизации.

Решение. Прежде всего вычислим компоненты градиента

= 16x + 4x , = 10x + 4x .

Для того чтобы применить метод наискорейшего спуска, зададим начальное приближение

x (0) = T

и с помощью формулы (3.46) построим новое приближение

x = x -α f (x )

f (x) = 8x + 4x x + 5x

Рис. 3.14. Итерации по методу Коши с использованием метода квадратичной интерполяции.

Таблица 3.1. Результаты вычислений по методу Коши

Выберем α таким образом, чтобы f (x (1)) → min.; α = 0,056. Следовательно, x (1) = [– 1,20, 2.16] T Далее найдем точку

x = x – α f (x ),

вычислив градиент в точке x и проведя поиск вдоль прямой.

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

Несмотря на то что метод Коши не имеет большого практического значения, он реализует важнейшие шаги большинства градиентных методов. Блок-схема алгоритма Коши приведена на рис. 3.15. Заметим, что работа алгоритма завершается, когда модуль градиента или модуль вектора ∆x становится достаточно малым.

Рис. 3.15. Блок-схема метода Коши.

3.3.2. Метод Ньютона

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

Опять разложим целевую функцию в ряд Тейлора

f(x)=f(x )+ f(x ) ∆x+½∆x f(x )∆x+O(∆x³).

Отбрасывая все члены разложения третьего порядка и выше, полу­чим квадратичную аппроксимацию f(x):

(x; x ) = f(x ) + f(x ) T ∆x + ½∆x f(x )∆x, (3.48)

где (x; x ) - аппроксимирующая функция переменной х, построенная в точке x . На основе квадратичной аппроксимации функции f(х) сформируем последовательность итераций таким образом, чтобы во вновь получаемой точке x градиент аппроксимирующей функции обращался в нуль. Имеем

(x; x ) = + f(x )+ f(x ) = 0, (3.49)

Метод ПауэлаМетод ориентирован на решение задач с квадратичными целевыми функциями, т.е.
функциями вида:
f(x) = a + bTx + 1/2xTCx,
где Q(x) = xTCx – квадратичная форма.
Т.к. в окрестности точки оптимума любую нелинейную функцию можно аппроксимировать
квадратичной функцией (поскольку линейный член разложения Тейлора обращается в нуль),
то метод может быть применен и для нелинейной целевой функции общего вида.
Метод Пауэлла использует свойство квадратичной функции, заключающееся в том, что
любая прямая, которая проходит через точку минимума функции х*, пересекает под равными
углами касательные к поверхностям равного уровня функции в точках пересечения.

Метод Пауэла

Метод Пауэла

Метод Пауэла

Алгоритм метода Пауэлла

Алгоритм метода Пауэлла