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

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

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

Правила ввода функций :

Схема алгоритма Пауэлла

пусть x 1 - начальная точка; Δx- выбранная величина шага по оси х .
Шаг 1: Вычислить x 2 =x 1 +Δx.
Шаг 2: Вычислить f(x 1) и f(x 2).
Шаг 3: Если f(x 1)>f(x 2), положить x 3 =x 1 +2Δx, если f(x 1)≤f(x 2), то x 3 =x 1 -Δx.
Шаг 4: Вычислить f(x 3) и найти F min = min{f 1 , f 2 , f 3 }
X min равно точке x i , которая соответствует F min .
Шаг 5: По трем точкам x 1 , x 2 , x 3 вычислить , используя квадратичную аппроксимацию.

а) является ли разность

;
б) является ли разность

,
где ε>0 и δ>0 - заданные точности.
Если условия а) и б) выполняются одновременно, то закончить поиск. Иначе переход на Шаг 7.
Шаг 7: Выбрать "наилучшую" точку (X min или ) и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти на Шаг 4.
Замечание : после пятого шага необходимо провести дополнительную проверку, т.к. точка может находиться за точкой x 3 . В этом случае точка заменяется точкой, координата которой вычисляется c учетом заранее установленной длины шага.
Пусть полученная точка x лежит вне отрезка интерполяции. Смысл здесь заключается в следующем. О характере функции, в общем случае, ничего неизвестно, но при помощи аппроксимации происходит замена ее по трем точкам параболой (на рисунке обозначена пунктиром). Вид параболы полностью определяется выбранными точками. Если точки выбраны неудачно, то минимум параболы может оказаться весьма далеко от минимума функции. Причем, если у функции имеются несколько локальных минимумов, в итоге можно найти не тот минимум, что является ближайшим к начальной точке. Применение же вышеописанного правила предотвращает подобную ситуацию.

Пример . Найти .
Пусть начальная точка 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).

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

Метод Пауэла

Суть метода заключается в следующем (Рассмотрим случай двух переменных).
Выбирается некоторая точка х(0) и выполняется одномерный поиск вдоль произвольного
направления, приводящий в точку х(1) (х(1) – точка минимума функции на выбранном
направлении).
Затем выбирается точка х(2), не лежащая на прямой х(0) – х(1), и осуществляется
одномерный поиск вдоль прямой, параллельной х(0) – х(1).
Находят точку х(3) – точку минимума функции на данном направлении.
Точка х(3) вместе с точкой х(1) определяют направление х(1) – х(3) одномерного поиска,
дающего точку минимума х*.
Направления х(0) – х(2) и х(1) – х(3) являются сопряженными направлениями относительно
матрицы С квадратичной формы Q(x) (C – сопряженные направления).
Точно также сопряженными являются направления х(2)-х(3) и х(1)-х(3).
В рассмотренных построениях для того, чтобы определить сопряженное направление,
требовалось задать две точки и некоторое направление.
Это не слишком удобно для проведения расчетов, поэтому предпочтительнее строить
систему сопряженных направлений, исходя из одной начальной точки.
Это легко осуществить при помощи единичных координатных векторов е(1), е(2), …, е(n).
e(1) = (1, 0, …, 0)T; e(2) = (0, 1, …, 0)T; …; e(n) = (0, 0, …, 1)T.
Проиллюстрируем процедуру построения сопряженных направлений для случая двух
переменных (ее можно обобщить и для n-мерного пространства).

Метод Пауэла

Пусть е(1) = (1, 0)Т; е(2) =(0, 1)Т.
Зададим начальную точку х(00). Произведем одномерный поиск минимума функции f
вдоль направления e(n) – e(2) (n=2), начиная из начальной точки х(00).
Точки прямой, исходящей из х(00) в направлении е(2), задаются формулой
x
= x(00) + he(2).
Вычислим значение h=h0, которому соответствует минимум f(x(00) + h0e(2)).
f(x(00) + h0e(2)) = minh f(x(00) + he(2)).
Положим x(0) = x(00) + h0e(2).
Из точки х(0) выполняем одномерный поиск вдоль направления е(1).
Вычислим значение h1, которому соответствует минимум f(x(0)+h1e(1)).
Положим x(1) = x(0) + h1e(1).
Из точки х(1) выполняем одномерный поиск в направлении е(2).
Вычисляем значение h2, которому соответствует минимум f(x(1)+h2e(2)).
Положим x(2) = x(1) + h2e(2).
Направления (х(2) – х(0)) и е(2) оказываются сопряженными.
Это видно из следующего рисунка.

Метод Пауэла

Можно рассуждать так:
мы выбрали две точки х(00) и х(1) и
из этих точек выполнили одномерный
поиск в направлении е(2).
Соответствующие этим поискам
точки минимума – х(0) и х(2).
Поэтому направление х(0) – х(2)
является
сопряженным
с
(2)
направлением е.
Одномерный
поиск
в
направлении е(2) дает точку минимума
х*.
Поэтому на следующей итерации
проводится одномерный поиск в
направлении х(0) – х(2) и будет получена
точка минимума х*.
В случае квадратичной функции n
переменных оптимальное значение
находится за n итераций при этом
требуется провести n2 одномерных
поисков.

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

1. Задают начальную точку х(00). Выполняют одномерный поиск минимума функции f
вдоль направления p(n) = e(n) = (0, …, 0, 1)T. Величина шага h0 находится из условия f(x(00)
+h0p(n)) = minh f(x(00) +hp(n)). Полученный шаг определяет точку x(0) = x(00) + h0p(n);
k:=1(номер итерации).
2. За начальные направления поиска р(1), р(2), …, р(n) принимают направления осей
координат, т.е. p(i) = e(i) (i = 1, …, n), где е(1) = (1, 0, …, 0)Т, е(2) = (0, 1, …, 0)Т, …, е(n) = (0, …,
0, 1)Т.
3. Из точки х(0) выполняют n одномерных поисков вдоль направлений p(i) (i = 1, …, n).
При этом каждый следующий поиск производится из точки минимума, полученной на
предыдущем шаге. Величина шага hi находится из условия f(x(i-1) + hip(i)) = minh f(x(i-1) +
hp(i)). Полученный шаг определяет точку x(i) = x(i-1) +hip(i).
4. Выбираем новое направление p = x(n) – x(0) и заменяем направления p(1), …, p(n)
соответственно на p(2), …, p(n), p.
5. Из точки x(n) осуществляют одномерный поиск вдоль направления p = p(n) = x(n) – x(0).
Величина шага hn+1 находится из f(x(n) + hn+1p) = minh f(x(n) + hp). Полученный шаг
определяет точку x(n+1) = x(n) + hn+1p; k:=k+1(номер итерации).

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

6. Проверяют выполнение условия k n. Если условие выполняется перейти к п.7, в
противном случае перейти к п.8.
7. а) если целевая функция квадратичная, то поиск прекращается; х* полагается
равным x(n+1) (x* := x(n+1)).
б)если целевая функция не является квадратичной, то проверяют выполнение условия
||x(n) – x(0)|| (- заданная точность) (т.е. изменение по каждой независимой переменной
должно быть меньше, чем заданная точность). Если условие выполняется, то поиск
прекратить; х* полагается равным x(n+1). В противном случае перейти к п.8.
8. Заменяют x(0) на x(n+1) (x(0) := x(n+1)) и принимают эту точку за начальную точку х(0) для
следующей итерации. Переходят к п.3.
Таким образом, в результате выполнения рассмотренной процедуры осуществляется
поочередная замена принятых вначале направлений поиска. В итоге после n итераций они
окажутся взаимно сопряженными.

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

Введение

сопряженный направление пауэлл квадратичный

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

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

Цель данной курсовой работы:

проанализировать и обработать теоретические и экспериментальные данные по теме метод сопряженных направлений;

анализ собранной информации;

сравнительный анализ с другими методами;

разработка программы, реализующая данный метод.

Метод сопряженных направлений. Постановка задачи

Требуется найти безусловный минимум функции 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 =

Метод деформируемого многогранника (метод Нелдера--Мида)

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