Асимптотические направления. асимптоты

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

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

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

Нетрудно проверить, что все аксиомы нормы при этом выполнены. Определение (31) означает, что под скалярным произведением двух векторов х и у теперь подразумевается величина Векторы, ортогональные в смысле этого скалярного произведения

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

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

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

Докажем, что взаимно сопряженные векторы линейно-независимы.

Из равенства следует , что противоречит положительной определенности матрицы.

Это противоречие доказывает наше утверждение. Значит, система сопряженных векторов является базисом в -мерном пространстве. Для данной матрицы имеется бесчисленное множество базисов, состоящих из взаимно сопряженных векторов.

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

Подставляя это выражение в правую часть формулы (30), преобразуем ее с учетом сопряженности базиса (33) к следующему виду:

Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (34). Это означает, что движение по одному из сопряженных направлений меняет только один член суммы (35), не затрагивая остальных.

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

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

б) Сопряженный базис можно построить способом параллельных касательных плоскостей.

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

Для этого воспользуемся выражением (35), где в сумме оставим только один член:

и положим . Отсюда следует уравнение, которому удовлетворяет точка минимума:

Пусть на какой-нибудь другой прямой, параллельной первой, функция принимает минимальное значение в точке гг; тогда аналогично найдем Вычитая это равенство из (36), получим

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

Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору . Для этого достаточно провести две прямые, параллельные и найти на каждой прямой минимум квадратичной формы (30). Вектор соединяющий эти минимумы, сопряжен Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа.

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

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

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

Из точки снова совершим по последним направлениям спуск, который приведет в точку Этот спуск означает точное нахождение минимума во второй плоскости, параллельной первой плоскости. Следовательно, направление сопряжено последним векторам базиса.

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

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

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

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

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

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

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

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

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

Метод сопряженных направлений является, по-видимому, наиболее эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа - «плато»-, и при большом числе переменных - до двух десятков.

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

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

Аналогично, точка t 0 (k ) получена из точки t n - k +1 (k ) помощью последовательности одномерных минимизаций вдоль тех же направлений, и поэтому

Доказываемое утверждение теперь непосредственно следует с леммы 2.2 так как .

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

Опишем модификацию метода 2.5-2.7, приводящую к эффективному алгоритму минимизации.

После завершения k -го цикла проверяется выполнение неравенств . Если хотя бы одно с них выполнено, то производится остановка. В противном случае проверяется выполнение неравенства

, (2.16)

Если оно выполнено, то направления минимизации (k +1) -го цикла остаются прежними, т. е.

Если нет, то направления минимизации (k +1) -го цикла определяется по формулам

В обоих случаях начальная точка (k +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.

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

,

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

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

• (3.12)
• (где r есть n-мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется точно к минимуму за конечное число шагов.

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

Определение (3.13) означает, что под скалярным произведением двух векторов x и у теперь подразумевается величина (х, Ау). Векторы, ортогональные в смысле этого скалярного произведения

(х, Ау) = 0 (3.14)

называют сопряженными (по отношению к данной матрице А).

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

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

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

Пусть имеется некоторая система попарно сопряженных векторов х i . Нормируем каждый из этих векторов в смысле нормы (3.14), тогда соотношения между ними примут вид

Докажем, что взаимно сопряженные векторы линейно-независимы. Из равенства

что противоречит положительной определенности матрицы. Это противоречие доказывает наше утверждение. Значит, система n-сопряженных векторов является базисом в n-мерном пространстве. Для данной матрицы имеется бесчисленное множество базисов, состоящих из взаимно сопряженных векторов.

Пусть нашли некоторый спряженный базис х i , 1 in. Выберем произвольную точку r 0 . Любое движение из этой точки можно разложить по сопряженному базису

Подставляя это выражение в правую часть формулы (3.12), преобразуем ее с учетом сопряженности базиса (3.15) к следующему виду:

Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (3.16). Это означает, что движение по одному из сопряженных направлений х i меняет только один член суммы (3.17), не затрагивая остальных.

Совершим из точки r 0 поочередные спуски до минимума по каждому из сопряженных направлений x i . Каждый спуск минимизирует свой член суммы (3.17), так что минимум квадратичной функции точно достигается после выполнения одного цикла спусков, то есть за конечное число действий.

Сопряженный базис можно построить способом параллельных касательных плоскостей.

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

ц(б) = Ф(r 0) + б 2 + б (x, 2Аr 0 + b),

и положим (dц/dб) б-0 = 0. Отсюда следует уравнение, которому удовлетворяет точка минимума:

(х, 2Аr 0 + b) = 0. (3.18)

Пусть на какой-нибудь другой прямой, параллельно первой, функция принимает минимальное значение в точке r 1 ;тогда аналогично найдем (х, 2Аr 1 + b) = 0. Вычитая это равенство из (3.18), получим

(х, А(r 1 r 0)) = 0. (3.19)

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

Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору х. Для этого достаточно провести две прямые, параллельные х, и найти на каждой прямой минимум квадратичной формы (3.12). Вектор r 1 r 0 , соединяющий эти минимумы, сопряжен х. Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа.

Пусть имеются две параллельные m-мерные плоскости, порожденные системой сопряженных векторов х i , 1 imn. Пусть квадратичная функция достигает своего минимального значения на этих плоскостях соответственно в точках r 0 и r 1 . Аналогичными рассуждениями можно доказать, что вектор r 1 r 0 , соединяющий точки минимума, сопряжен всем векторам х i . Следовательно, если задана неполная система сопряженных векторов х i , то этим способом всегда можно построить вектор r 1 r 0 , сопряженный всем векторам этой системы.

Рассмотрим один цикл процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние m векторов взаимно сопряжены, а первые n-m векторов не сопряжены последним. Найдем минимум квадратичной функции (3.12) в какой-нибудь m-мерной плоскости, порожденной последними mвекторами базиса. Поскольку эти векторы взаимно сопряжены, то для этого достаточно произвольно выбрать точку r 0 и сделать из нее спуск поочередно по каждому из этих направлений (до минимума). Точку минимума в этой плоскости обозначим через r 1 .

Теперь из точки r 1 сделаем поочередный спуск по первым n - m векторам базиса. Этот спуск выведет траекторию из первой плоскости и приведет ее в некоторую точку r 2 . Из точки r 2 снова совершим по последним m направлениям спуск, который приведет в точку r 3 . Этот спуск означает точное нахождение минимума во второй плоскости, параллельной первой плоскости. Следовательно, направление r 3 - r 1 сопряжено последним m векторам базиса.

Если одно из несопряженных направлений в базисе заменить направлением r 3 - r 1 , то в новом базисе уже m + 1 направление будет взаимно сопряжено.

Начнем расчет циклов с произвольного базиса; для него можно считать, что m=1. Описанный процесс за один цикл увеличивает на единицу число сопряженных векторов в базисе. Значит, за n - 1 цикл все векторы базиса станут сопряженными, и следующий цикл приведет траекторию в точку минимума квадратичной функции (3.12).

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

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

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

Метод сопряженных направлений является, по-видимому, наиболее эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа - «плато», и при большом числе переменных - до двух десятков.

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

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

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

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

.

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

.

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

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

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

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

Алгоритм.

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

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

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

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

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

(*)

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

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

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

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

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

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

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

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

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

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