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

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

Метод Пауэла

Метод Пауэла

Метод Пауэла

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

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

Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка 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

Шаг 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) многих переменных, т.е. найти точку

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

Стратегия поиска

В методе сопряженных направлений (методе Пауэлла ) используется факт, что минимум квадратичной функции может быть найден не более чем за n шагов при условии, что поиск ведется вдоль сопряженных относительно матрицы Гессе направлений. Так как достаточно большой класс целевых функций может быть предоставлен в окрестности точки минимума своей квадратичной аппроксимацией, описанная идея применяется и для неквадратичных функций. Задается начальная точка и направления, совпадающие с координатами. Находится минимум f(x) при последовательном движении по (n + 1) направления с помощью одного из методов одномерной минимизации. При этом полученная ранее точка минимума берется в качестве исходной для поиска по совершенно нового направлению, а направление используется как при первом, так и последнем поиске. Находится новое направление поиска, сопряженное с. Оно проходит через точки, полученные при последнем поиске. Заменяется на, на и т.д. Направление заменяется сопряженным направлением, после чего повторяется поиск по (n+1) направлениям, уже не содержащим старого направления.

Для квадратичных функций последовательностью n2 одномерных поисков приводит к точке минимума (если все операции выполнены точно). Построение сопряженного направления для квадратичной функции при n = 2 изображено на рисунке 1.1. Оно проходит через точки 1 и 3.

Рисунок 1.1 - Построение сопряженного направления для квадратичной функции

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

Шаг 1. Задать начальную точку х 0 , число ε>0 для окончания алгоритма, начальные направления поиска

Положим d0 = dn , i = 0, у0 = х0, k= 0.

Шаг 2. Найти yi+1 = y i +ti di где шаг ti находится в результате поиска ми-нимума функции f(yi+tidi) по ti одним из методов одномерной минимизации.

Шаг 3. Проверить выполнение условий:

а)если i < n -1, положить i= i +1 и перейти к шагу 2;

б)если I = n -1, проверить успешность поиска по n первым направлениям.

Если у n = у, то поиск завершить: х* =yn, иначе положить i=i+1 и перей-ти к шагу 2;

в) если i = n, проверить успешность поиска по n последним направле-ниям. Если y n+1 = у 1, поиск завершить: х* = у n+1, иначе перейти к шагу 4 для построения сопряженного направления.

Шаг 4. Положить хk+1 = уn+1 и проверить условие окончания:

а)если |||хk+1 - хk || | < ε, то поиск завершить: х* = хk+1;

б)иначе положить: d0 = dn = уn+1 - у1 (новое направление);

(исключается старое направление).

Если при этом rang (,...,)= п, то новая система направлений линей-но независима. В этом случае положить: di =di , i = 0,1,...,n; k =k +1, i = 0, у0 = xk+i и перейти к шагу 2.

Если rang(,...,)< n, то новая система направлений линейно зави-сима. Тогда следует продолжать поиск в старых направлениях Для этого поло-жить: di =di , i = 0,1,...,n; у0 = xk+1, k = k + 1, i = 0 и перейти к шагу 2.

Входные данные

Задать начальную точку, к примеру, число ε > 0 для окончания алгоритма, к примеру ε =0,1, начальные направления поиска:

Положить d0 = d2= , i = 0, у0 = х0, k= 0.

Пример поиска минимума функции методом Пауэлла

Пример. Найти минимум функции f(x) = 4(х1 -5)2 +(х2 -6) → min мето-дом Пауэлла.

□ 1. Зададим начальную точку х = (8,9)T, ε=0,1. По-ложим d0=dn= d2 ; у0 = х0 , i=0, k = 0.

Получаем у1 = у0 +t0d0 = (8,9)T + t0(0,1)T = (8,9 + t0)T - Найдем мини-мум функции f(8,9 + t0) = 36 + (3 + t0)2 по t0. Очевидно, t0 = -3, а у1 = (8,6)T.

Имеем i = 0 < 2 = n, поэтому i = i + 1 = 1 и перейдем к шагу 2.

21.Получаем у2 = у1 + t1d1 = (8,6)T + ti(l,0)T = (8 + t1,6)T. Найдем минимум функции f(8 + t1 , 6) = 4(3 +t1)2 по t1. Очевидно, он достигается при t1 =-3. Тогда у2 =

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

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

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

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

,

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