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

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

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

, (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.

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

,

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

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

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

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

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

Шаг 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)