Алгоритм метода сопряженных направлений пауэлла. Метод пауэлла полиномиальной аппроксимации

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

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

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

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

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) верно для , т. е. всякий вектор вида может быть заменен поиском максимума на плоскости или на прямой.

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

Определение . Пусть - симметрическая матрица порядка
. Векторы
называются
- сопряженными, если они линейно независимы и выполняется условие
при
.

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

В качестве матрицы
можно взять матрицу Гессе

.

В качестве одного из направлений выберем
. Тогда направление
должно удовлетворять равенству

.

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

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

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

Утверждение. Пусть задана квадратичная функция
, две произвольные точки
и направление S ..Если точка является точкой минимума функции
вдоль направления S из точки , а- точкой минимума функции вдоль направления S из точки
, то направление
сопряжено с направлением S .

Алгоритм.

Шаг 1. Задать начальную точку и систему линейно независимых направлений
(они первоначально могут совпадать с направлениями координатных осей). Минимизировать функцию
при последовательном движении по направлениям; используя какой-либо одномерный поиск; и полученную ранее точку минимума взять в качестве исходной.

Шаг 2. Выполнить дополнительный шаг
, соответствующий полному перемещению на шаге 1. Вычислить точку
(рис 12). Проверить критерий (*) включения нового направления в систему сопряженных направлений.

Шаг 3. Пусть – наибольшее уменьшение целевой функции в одном из направлений
:

и является направлением, соответствующим.

Если выполняются условия

(*)

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

Шаг 4. Если условия не выполняются, то минимизировать функцию
вдоль направления
. Точку этого минимума взять в качестве начальной на следующем этапе. На этом этапе использовать систему направлений

т.е. направление заменить на, которое поместить в последний столбец матрицы направлений.

Шаг 5. Если
, то минимум найден. В противном случае выполнить шаг 1.

Пример. Щелкнув по значку, откроется Mathcad документ метода сопряженных направлений, в котором можно выполнить вычисления.

Минимизация функции

методом сопряженных направлений

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

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

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

Шаг 1. Задать начальную точку x o и систему N линейно независимых направлений s i ; целесообразно принять s i = e i , i=1,2,...,N.

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

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

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Если целевая функция квадратична и обладает минимумом, то точка минимума находится в результате реализации N циклов, включающих шаги 2-4. Здесь N - число переменных. Если же функция W(x) не является квадратичной, то требуется более чем N циклов.

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

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

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

x k+1 = x k + a k s(x k), (13.9)

x k - текущее приближение к решению x * ;

a k - параметр, характеризующий длину шага,

s(x k) - направление поиска в N - мерном пространстве управляемых переменных x i , i = 1, 2,..., N.

Способ определения a k и s(x k) на каждой итерации связан с особенностями применяемого метода. Обычно выбор a k осуществляется путем решения задачи минимизации W(x) в направлении s(x k). Поэтому при реализации градиентных необходимо использовать эффективные алгоритмы одномерной минимизации.

Простейший градиентный метод

В основе метода лежит следующая итерационная модификация формулы (13.9):

x k+1 = x k - a DW(x k), (13.10)

a - заданный положительный коэффициент;

DW(x k) - градиент целевой функции первого порядка.

Недостатки:

· необходимость выбора подходящего значения a;

· медленная сходимость к точке минимума ввиду малости DW(x k) в окрестности этой точки.

Метод наискорейшего спуска

Свободен от первого недостатка простейшего градиентного метода, т.к. a k вычисляется путем решения задачи минимизации DW(x k) вдоль направления DW(x k) с помощью одного из методов одномерной оптимизации

x k+1 = x k - a k DW(x k). (13.11)

Данный метод иногда называют методом Коши.

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

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

Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле

x k+1 = x k - D 2 W(x k) -1 DW(x k). (13.12)

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

x k+1 = x k - a k D 2 W(x k) -1 DW(x k), (13.13)

a k - параметр, выбираемый таким образом, чтобы W(x k+1)®min.

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

Метод Пауэла

Суть метода заключается в следующем (Рассмотрим случай двух переменных).
Выбирается некоторая точка х(0) и выполняется одномерный поиск вдоль произвольного
направления, приводящий в точку х(1) (х(1) – точка минимума функции на выбранном
направлении).
Затем выбирается точка х(2), не лежащая на прямой х(0) – х(1), и осуществляется
одномерный поиск вдоль прямой, параллельной х(0) – х(1).
Находят точку х(3) – точку минимума функции на данном направлении.
Точка х(3) вместе с точкой х(1) определяют направление х(1) – х(3) одномерного поиска,
дающего точку минимума х*.
Направления х(0) – х(2) и х(1) – х(3) являются сопряженными направлениями относительно
матрицы С квадратичной формы Q(x) (C – сопряженные направления).
Точно также сопряженными являются направления х(2)-х(3) и х(1)-х(3).
В рассмотренных построениях для того, чтобы определить сопряженное направление,
требовалось задать две точки и некоторое направление.
Это не слишком удобно для проведения расчетов, поэтому предпочтительнее строить
систему сопряженных направлений, исходя из одной начальной точки.
Это легко осуществить при помощи единичных координатных векторов е(1), е(2), …, е(n).
e(1) = (1, 0, …, 0)T; e(2) = (0, 1, …, 0)T; …; e(n) = (0, 0, …, 1)T.
Проиллюстрируем процедуру построения сопряженных направлений для случая двух
переменных (ее можно обобщить и для n-мерного пространства).

Метод Пауэла

Пусть е(1) = (1, 0)Т; е(2) =(0, 1)Т.
Зададим начальную точку х(00). Произведем одномерный поиск минимума функции f
вдоль направления e(n) – e(2) (n=2), начиная из начальной точки х(00).
Точки прямой, исходящей из х(00) в направлении е(2), задаются формулой
x
= x(00) + he(2).
Вычислим значение h=h0, которому соответствует минимум f(x(00) + h0e(2)).
f(x(00) + h0e(2)) = minh f(x(00) + he(2)).
Положим x(0) = x(00) + h0e(2).
Из точки х(0) выполняем одномерный поиск вдоль направления е(1).
Вычислим значение h1, которому соответствует минимум f(x(0)+h1e(1)).
Положим x(1) = x(0) + h1e(1).
Из точки х(1) выполняем одномерный поиск в направлении е(2).
Вычисляем значение h2, которому соответствует минимум f(x(1)+h2e(2)).
Положим x(2) = x(1) + h2e(2).
Направления (х(2) – х(0)) и е(2) оказываются сопряженными.
Это видно из следующего рисунка.

Метод Пауэла

Можно рассуждать так:
мы выбрали две точки х(00) и х(1) и
из этих точек выполнили одномерный
поиск в направлении е(2).
Соответствующие этим поискам
точки минимума – х(0) и х(2).
Поэтому направление х(0) – х(2)
является
сопряженным
с
(2)
направлением е.
Одномерный
поиск
в
направлении е(2) дает точку минимума
х*.
Поэтому на следующей итерации
проводится одномерный поиск в
направлении х(0) – х(2) и будет получена
точка минимума х*.
В случае квадратичной функции n
переменных оптимальное значение
находится за n итераций при этом
требуется провести n2 одномерных
поисков.

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

1. Задают начальную точку х(00). Выполняют одномерный поиск минимума функции f
вдоль направления p(n) = e(n) = (0, …, 0, 1)T. Величина шага h0 находится из условия f(x(00)
+h0p(n)) = minh f(x(00) +hp(n)). Полученный шаг определяет точку x(0) = x(00) + h0p(n);
k:=1(номер итерации).
2. За начальные направления поиска р(1), р(2), …, р(n) принимают направления осей
координат, т.е. p(i) = e(i) (i = 1, …, n), где е(1) = (1, 0, …, 0)Т, е(2) = (0, 1, …, 0)Т, …, е(n) = (0, …,
0, 1)Т.
3. Из точки х(0) выполняют n одномерных поисков вдоль направлений p(i) (i = 1, …, n).
При этом каждый следующий поиск производится из точки минимума, полученной на
предыдущем шаге. Величина шага hi находится из условия f(x(i-1) + hip(i)) = minh f(x(i-1) +
hp(i)). Полученный шаг определяет точку x(i) = x(i-1) +hip(i).
4. Выбираем новое направление p = x(n) – x(0) и заменяем направления p(1), …, p(n)
соответственно на p(2), …, p(n), p.
5. Из точки x(n) осуществляют одномерный поиск вдоль направления p = p(n) = x(n) – x(0).
Величина шага hn+1 находится из f(x(n) + hn+1p) = minh f(x(n) + hp). Полученный шаг
определяет точку x(n+1) = x(n) + hn+1p; k:=k+1(номер итерации).

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

6. Проверяют выполнение условия k n. Если условие выполняется перейти к п.7, в
противном случае перейти к п.8.
7. а) если целевая функция квадратичная, то поиск прекращается; х* полагается
равным x(n+1) (x* := x(n+1)).
б)если целевая функция не является квадратичной, то проверяют выполнение условия
||x(n) – x(0)|| (- заданная точность) (т.е. изменение по каждой независимой переменной
должно быть меньше, чем заданная точность). Если условие выполняется, то поиск
прекратить; х* полагается равным x(n+1). В противном случае перейти к п.8.
8. Заменяют x(0) на x(n+1) (x(0) := x(n+1)) и принимают эту точку за начальную точку х(0) для
следующей итерации. Переходят к п.3.
Таким образом, в результате выполнения рассмотренной процедуры осуществляется
поочередная замена принятых вначале направлений поиска. В итоге после n итераций они
окажутся взаимно сопряженными.

Высокая скорость сходимости метода Ньютона обусловлена тем, что он минимизирует квадратичную функцию

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

Оказывается, что указаным свойством обладает система взаимно сопряженных относительно матрицы А направлений

Пусть А – симетрическая положительно определенная матрица размера .

Определение 2.1. Векторы (направления) иназываются сопряженными (относительно матрицы А), если они отличны от нуля и. Векторы (направления)называются взаимно сопряженными (относительно матрицы А), если все они отличны от нуля и. (2.3)

Лемма 3.1. Пусть векторы являются взаимно сопряженными. Тогда они линейно независимы.

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

Рассмотрим задачу минимизации на R n функции 2.1. Будем решать ее методом 2.2. Если векторы , взаимно сопряжены, то метод 3.2 можно назвать методом сопряженных направлений. Однако обычно это название употребляется лишь для тех методов, в которых именно стремление добится условия взаимной сопряженности определяет выбор направлений. К выполнению того же самого условия может привести и реализация совершенно новой идеи.

Теорема 3.1. Если векторы h k в методе 2.2 взаимно сопряжены, k =0,1,…, m -1 , то для функции f , заданой формулой 2.1,

, (2.4)

где – линейное подпространство, натянутое на указанные векторы.

Доказательство. С учетом 2.2 и определения 2.1 имеем

(2.5)

Используя это равенство, получаем

(2.6)

Следствие. Если векторы h k в методе 2.2 взаимно сопряженны, k =0,1,…, n -1 , то для функции f , заданной формулой 2.1, и произвольной точки

Таким образом, метод 2.2 позволяет найти точку минимума квадратичной функции 2.1 не более чем за n шагов.

2.2. Метод сопряженных направлений нулевого порядка.

Алгоритм состоит из последовательности циклов, k -й из которых определяется начальной точкой t 0 (k ) и направлениями минимизации p 0 (k ), p 1 (k ), …, p n -1 (k ) . На нулевом цикле в качестве t 0 (0), выбирается произвольная точка , в качествеp 0 (0), p 1 (k ), …, p n -1 (k ) – направления координатных осей.

Очередной k -й цикл состоит в последовательном решении одномерных задач

Тем самым определяется шаг из точки в точку

где итаковы, что

После завершения k -го цикланачальная точка и направления минимизации (k +1) -го цикла определяются по формулам

Критерием остановки может служить выполнение неравенства , где– заранее выбраное малое положительное число.

Теорема 3.2. Если векторы в методе 2.5-2.7 отличны от нуля, то для функцииf , заданой формулой 2.1

Доказательство. Учитывая следствие из теоремы 3.1, достаточно показать, что векторы взаимно сопряжены. Пусть. Предположив, что векторывзаимно сопряжены, докажем, что векторсопряжен с векторами.

Заметим, что и, стало быть, точкаt n (k ) , согласно формулам 2.5, получена из точки t n - k (k ) с помощью последовательности одномерных минимизаций вдоль направлений . Это, в силу теоремы 2.1, означает, что