Метод сопряженных направлений. Метод сопряженных направлений нулевого порядка
Описание алгоритма
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:
приводится к виду сумма полных квадратов
то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде:
вдоль направлений, называемых -сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнить одномерных поисков.
Шаг 1. Задать исходные точки, и направление. В частности, направление может совпадать с направлением координатной оси;
Шаг 2. Произвести одномерный поиск из точки в направлении получить точку, являющуюся точкой экстремума на заданном направлении;
Шаг 3. Произвести одномерный поиск из точки в направлении получить точку;
Шаг 4. Вычислить направление;
Шаг 5. Провести одномерный поиск из точки (либо) в направлении c выводом в точку.
Нахождение минимума целевой функции методом сопряжённых направлений Пауэлла.
Целевая функция:
Начальная точка:
Значение целевой функции в этой точке:
Шаг 1. Зададим исходные точки S(1) и S(2):
S(1) = S(2) =
Шаг 2. Найдем значение, при [Х(0)+2S(2)]. Произвольная точка на луче из точки Х(0) в направлении S(2) определяется как
Х = Х(0) + S(2) = [-9;-10] +
откуда X 1 = -9 X 2 = - 10
Отсюда находим:
X(1) = [-9;-10] + 15.5 = [-9;5.5]
Аналогично найдем значение, при [Х(1)+S(1)].
Х = Х(1) + S(1) = [-9;5.5] +
откуда X1 = -9 X2 =5.5
Подставляя эти значения в целевую функцию, получаем
Дифференцируем это выражение по и приравниваем нулю:
Отсюда находим:
X(2) = [-9;5.5] + 10.5 =
Также найдем значение, при [Х(2)+2S(2)].
Х = Х(2) + S(2) = +
откуда X 1 = 3 X 2 = 5.5+
Подставляя эти значения в целевую функцию, получаем
Дифференцируем это выражение по и приравниваем нулю:
Отсюда находим:
X(3) = -6 =
Шаг 3. Положим
S(3) = X(3) - X(1) =
Направление S(3) оказывается сопряженным с направлением S(2). Поскольку N = 2, то оптимизация вдоль направления S(3) дает искомый результат. Шаг 4. Найдем такое значение, при
X = X(3) + = +
X 1 = 3+ 12 X 2 = -0.5 -6
Х(4) = +0.0278* =
Таким образом, получили точку х= T , значение функции в которой f(x) = -3,778, совпадает со стационарной точкой.
Вывод: метод сопряженных направлений Пауэлла обеспечивает высокоточный при малом количестве итераций по сравнению с предыдущими методами.
Графическое пояснение метода сопряженных направлений Пауэлла:
Методы прямого поиска являются удобными при простых целевых функциях, или когда необходимо найти оптимум с невысокой степенью точности. Но требуют больших затрат времени и вычислительных ресурсов, из-за большого числа проводимых итераций: метод поиска по симплексу - 15 итераций, метод Хука-Дживса - 5 итераций, метод сопряженных направлений Пауэлла - 4 итерации.
Метод деформируемого многогранника (метод Нелдера--Мида)
Данный метод состоит в том, что для минимизации функции п переменных f(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому вектору х. Вычисляются значения целевой функции f(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершина х[h]. Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точка х[q] с меньшим значением целевой функции, чем в вершине х[h] (Рис. 7.6). Затем исключается вершина х[h]. Из оставшихся вершин и точки x[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.
Геометрическая интерпретация метода деформируемого многогранника
Метод Нелдера-Мида.
Пусть - некоторая точка 5-мерного пространства, которая лежит в окрестности минимума. В этом пространстве зададим симплекс (правильный 6-вершинный многогранник), одна из вершин которого лежит в т. . Метод Нелдера-Мида на каждом шаге реали-зует исключение из симплекса точки с самым большим значением функции, заменяя ее некоторой “лучшей” точкой. В результате нахо-дится точка, для которой значение функции минимально (с заданной точностью).
Алгоритм метода реализует следующую последовательность действий.
Вводится симплекс, координаты которого заданы таблицей (одна из вершин в начале координат)
Если, то, в частности, для имеем
Расположение симплекса показано на рис. 7.7.
Легко убедиться в том, что если координаты вершины симплекса задавать в соответствии с матрицей, то расстояние между любыми двумя верши-нами симплекса всегда будет равно выбранной константе t независимо от размерности задачи n. Действительно, расстояние между любой вершиной, и вершиной равно
С другой стороны, расстояние между любой парой вершин,также равно t.
Действительно,
Зададим начальную точку поиска вектором. Перенесем исходный симплекс таким образом, чтобы вершина, находившаяся в начале координат, оказалась в точке. Получим матрицу
Вычислим значения оптимизируемой функции в точках и перенумеруем точки так, чтобы выполнялись неравенства
Найдем координаты центра тяжести фигуры, получающейся в результате удаления вершины
Осуществим отражение вершины относительно центра тяжести. Получим точку. Если то получится зеркальное отражение. Сравним теперь между собой значения. Возможны следующие варианты:
В этом случае выполняется растяжение и отыскивается точка. Параметр обычно принимают равным 1.5. Полученная точка V заменяет, если В противном случае для замены используется точка.
В этом случае реализуется отражение. Точка заменяет.
В этом случае осуществляется сжатие и отыскивается точка. Параметр обычно принимают равным 0.5. Полученная точка заменяет.
При этом осуществляется редукция (уменьшение размера симплекса с подтягиванием всех вершин к). Координаты вершины нового симплекса рассчитываются по формуле
Критерий останова:
Критерий останова является составным. При этом его компоненты имеют различный вес в зависимости от того, каков характер оптимизируемой функции в окрестности экстремума. Если в районе экстремума оптимизируемая функция изменяется по типу ""глубокая впадина"", то больший вклад в численное значение критерия вносит первое слагаемое, а второе при этом быстро уменьшается. Напротив, если оптимизируемая функция изменяется по типу ""пологое плато"", то первое слагаемое быстро становится малым, и поэтому второе слагаемое вносит больший вклад в величину критерия.
Модификация метода Нелдера-Мида. Описанный классический вариант построения алгоритма Нелдера-Мида обладает конструктивным недостатком, который состоит в следующем. Предположим, что оптимизируемая функция двух переменных имеет вид глубокого оврага с очень пологим дном. Тогда может случиться так, что симплекс, который в рассматриваемом случае представляет собой треугольник, двумя вершинами ляжет на дно оврага, а третья вершина окажется на склоне оврага. При этом на очередном шаге произойдет переброс этой вершины на другой склон, а затем редукция или сжатие симплекса. Если склон оврага крутой, то эта процедура повторится много раз, в результате чего симплекс сожмется и может сработать критерий останова, хотя до точки минимума еще может быть очень далеко. Естественное усовершенствование алгоритма состоит в следующем. После срабатывания критерия останова целесообразно над центром тяжести сжавшегося симплекса построить новый, размеры и ориентация которого соответствуют исходному.
Пусть координаты центра тяжести симплекса образуют вектор
Найдем теперь координаты точки такой, что центр тяжести симплекса с длиной ребра, равной t, использующего вершину в качестве начальной, совпадал бы с.
Матрица координат указанного симплекса имеет вид:
Координаты центра тяжести этого симплекса образуют вектор
Теперь координаты точки найдем из равенства
Подставляя вычисленные значения в (7.1), получим требуемый симплекс, используя который продолжим процедуру поиска минимума. Эту процедуру считаем законченной, если после очередного сжатия алгоритм приведет в точку, расстояние от которой до точки предыдущего сжатия не превосходит некоторого, достаточно малого.
"Метод сопряженных направлений"
Введение
сопряженный направление пауэлл квадратичный
Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходиться заниматься в повседневной жизни. Термином оптимизация в литературе обозначает процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или оптимального решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.
Цель данной курсовой работы:
проанализировать и обработать теоретические и экспериментальные данные по теме метод сопряженных направлений;
анализ собранной информации;
сравнительный анализ с другими методами;
разработка программы, реализующая данный метод.
Метод сопряженных направлений. Постановка задачи
Требуется найти безусловный минимум функции 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 =
Шаг 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.
В заключение изучения приближенных методов поиска экстремума ФМП без ограничений рассмотрим метод сопряженных направлений, который завоевывает на практике все большую популярность.
Сначала дадим
понятие сопряженности. Пусть имеем два
направления, которые характеризуются
векторами
и
.
Направления
и
называют сопряженными по отношению к
некоторой положительно определенной
матрице Н, если выполняется соотношение
,
(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.
Тогда координаты экстремума:
,
Как видно из приведенных примеров при решении задачи Лагранжа получаем в общем случае систему нелинейных уравнений, которую подчас трудно решить аналитически. Поэтому целесообразно применять приближенные методы решения задачи Лагранжа.
Загрузка...
