Метод сопряженных направлений
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
"Метод сопряженных направлений"
Введение
сопряженный направление пауэлл квадратичный
Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходиться заниматься в повседневной жизни. Термином оптимизация в литературе обозначает процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или оптимального решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.
Цель данной курсовой работы:
проанализировать и обработать теоретические и экспериментальные данные по теме метод сопряженных направлений;
анализ собранной информации;
сравнительный анализ с другими методами;
разработка программы, реализующая данный метод.
Метод сопряженных направлений. Постановка задачи
Требуется найти безусловный минимум функции f(x) многих переменных, т.е. найти точку
Определение. Пусть H - симметрическая матрица размера n x n. Векторы называются H-сопряженными или просто сопряженными, если при всех .
Стратегия поиска
В методе сопряженных направлений (методе Пауэлла [Powell M.J.D.] ) используется факт, что минимум квадратичной функции может быть найден не более чем за 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 =