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

Шаг 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 итераций они
окажутся взаимно сопряженными.

Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка x 1 Îd(x*).

Начальный этап

Выбрать ε 1 , ε 2 , h.

Взять 3 точки a, b, c на равных на равных интервалах. Предполагается, что сработал метод Свенна и получен интервал .

Основной этап

Найти аппроксимирующий минимум на 1-й итерации по формуле:

на последующих итерациях по формуле:

Проверить критерии близости двух точек:

;

Если он выполняется, принять и остановиться.

Если не выполняется, то из 2-х точек b и d выбрать «лучшую» - в которой наименьшее значение функции, обозначить её как b, а 2 соседние с ней – a и c. Далее рассмотреть 4 ситуации аналогично ЗС-2.

Положить k=k+1 и вернуться на шаг 1.

Метод Давидона

Начальный этап

Выбрать ε, x 0 , p, α 1

Предполагается, что сработал метод Свенна и получен интервал .

Основной этап

Найти аппроксимирующий минимум, т.е. точку d по формулам:

Проверить КОП: если y ` r ≤ ε , то остановиться, х=a+α r p . Иначе: сократить ТИЛ: если y ` r <0, то , если y ` r >0, то .

Положить k=k+1 и вернуться на шаг 1.

Методы многомерной минимизации

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

x – вектор от которого зависит функция

x0 – стартовая точка

p – направление

L – смещение по направлению

Метод Коши

Метод Коши относится к группе методов градиентного спуска. Градиентные методы – это методы, где на каждом шаге выбирается антиградиентное направление спуска.

Начальный этап

Выбрать x1, e, k.

Основной этап

(1) Найти L как результат минимизации функции по направлению p.

(2)

(1) Вычислить новое значение градиента

(2) Проверить КОП: если , то, иначе на Шаг 1.

Метод Циклического покоординатного спуска

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

Начальный этап

Выбрать x1, e, k=1, l=1.

Основной этап

(1) В качестве направления p выбрать , где ненулевая позиция имеет индекс l.

(2) Найти L как результат минимизации функции по направлению p.

(3)

(4) Если l

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

Где А – симметрическая положительно определенная матрица размера 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, означает, что

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

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

, (7)

Сопряженность связана с ортогональностью. Если Н – единичная матрица, то при
имеем два взаимно перпендикулярных вектора. Соотношение (7) можно трактовать таким образом: матрица Н, примененная к вектору, изменяет его длину и поворачивает на некоторый угол так, что новый вектор
должен быть ортогонален вектору.

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

1) Производится выбор и в этом направлении отыскивается экстремум.

Возьмем вектор с направлениямии. Векторможно выбирать произвольно, поэтому возьмем==1. Вектордает направлениеL 1 .

Проведем через L 1 плоскость перпендикулярную плоскости {x 1 ,x 2 }. Плоскость пересечет экстремальную поверхность у(х 1 , х 2) и выделит на ней экстремальную линию. Определим координаты минимума на этой линии (параболе), для чего вычислим проекции градиента в точке х 0:

,

и по формуле (6) найдем :

Естественно, линия L 1 касается в точке х (1) линии равного уровня функции у.

2) Отыскивается из условия сопряженности
.

Получим сопряженный вектор с проекциями
и
, воспользовавшись формулой (7):

П
олучили одно уравнение с двумя неизвестными. Т.к. нам требуется только направление вектора, а не его длина, то одним из неизвестных можно задаться произвольно. Пусть
=1, тогда
= –4.

3) Из точки х (1) в направлении ищется экстремум.

Сопряженный вектор должен проходить через х (1) . Сделаем шаг в сопряженном направлении:

Величина шага  (1) в х (1) :

,

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

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

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

Классическая задача Лагранжа на условный экстремум (ограничения-равенства).

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

Рассмотрим геометрическую интерпретацию классической задачи. На плоскости {x 1 ,x 2 } построим функцию
, а также линии равного уровня функции
со значениямиN 1 , линияN 3 имеет 2 общих точки с
и они не могут быть решением задачи, т.к.N 3 >N 2 . Остается линия уровняN 2 , которая имеет единственную точку касания с
. Абсолютный минимумN 0 может не принадлежать ограничению
и поэтому не может быть решением задачи. Отсюда ясно и название «условный экстремум», т.е. такой экстремум, который достигается только на заданных ограничениях.

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

Из подобия треугольников можно записать:

–множитель Лагранжа.

или

Составим теперь функцию
следующим образом:

–функция Лагранжа.

Запишем соотношения для нахождения экстремума функции F.

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

В общем случае, число переменных примем за n, а число ограничений заm. Тогда функция Лагранжа запишется в виде:

или в векторной форме

Для решения задачи записывается система уравнений:

, (8)

т.е. для n+mпеременных будем иметьn+mуравнений. Если система совместна, то задача Лагранжа имеет единственное решение.

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

Пример: Покажем технику решения задачи методом Лагранжа.

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

При этом ограничении требуется найти потребляемую мощность насосов
. Пусть коэффициенты равны 1 = 2 =1, К 1 =1, К 2 =1,5. Тогда целевая функция, найти минимум при ограничении:.

Процедура решения:

Составляем функцию Лагранжа

Составляется система уравнений (8):

Записываются Q i черези подставляются в третье выражение:

,
,
,

Тогда координаты экстремума:

,

Пример 2:

Пусть дано последовательное соединение компрессоров.
Задана требуемая степень сжатия:, которую требуется обеспечить при минимуме расхода мощности:

2.

3.
,
, подставляем в выражение для:

,
,
. Из физических соображений положительный корень отбрасываем, поэтому= –0,98.

Тогда координаты экстремума:

,

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