Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Численные методы минимизации функции

 

Численное решение задачи минимизации (1), как правило, связано с построением минимизирующей последовательности точек x0, x1, x2,…, xn,…, обладающих свойством

f (xk) < f (xk-1), k =0,1,… (3)

 

Общее правило построения минимизирующей последовательности имеет вид

x k+1= x k+ t k d k, k =0,1,…,

 

где х0 - начальная точка поиска; dk - приемлемое направление перехода из точки xk в точку xk+1, которое обеспечивает выполнение условий (3) и называется направлением спуска; tk - величина шага. Начальная точка поиска задается исходя из физического содержания решаемой задачи и априорных данных о существовании и положении точек экстремума.

При решении вопроса о выборе численного метода рекомендуется оценить поведение линий уровня целевой функции в окрестностях предполагаемой точки экстремума. Число m = L/l, где L и l - максимальное и минимальное собственные значения гессиана функции f в предполагаемой точке экстремума x0 ( характеризующее разброс собственных значений оператора f (x)), называется числом обусловленности гессиана функции f в точке x0. Если m >> 1, то функция f называется плохо обусловленн ой или овражн ой. Овражность, то есть вытянутость линий уровня вдоль одного направления, приводит к тому, что градиентные методы поиска экстремума функции сходятся медленно.

В зависимости от наивысшего порядка частных производных функции f (x), используемых для формирования dk и tk, численные методы принято делить на три группы:

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

Методы первого порядка, использующие информацию о значениях самой функции f (x) и ее первых производных (методы наискорейшего градиентного спуска, дробления шага, Гаусса-Зейделя, Флетчера-Ривса).

Методы второго порядка, использующие, кроме того, и информацию о вторых производных функции f (x) ( метод Ньютона и его модификации).

Метод конфигураций (Хука - Дживса)

Следует выделить два этапа метода конфигураций:

1) исследование с циклическим изменением переменных и 2) ускорение поиска по образцам.

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

Направление от старого базиса к новому задает направление ускорения поиска: в качестве следующей точки минимизирующей последовательности проверяется точка y1= x0+ l (x1- x0). Здесь l - ускоряющий множитель, задаваемый пользователем. Если полученная точка является удачной, то она берется в качестве следующей точки для исследования. В противном случае исследование ведется из точки x1.

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

При решении задачи поиска минимума функции f (x) методом Нелдера-Мида строится последовательность множеств из n +1 точек, которые являются вершинами выпуклого многогранника. На каждом последующем k +1-м шаге из системы точек xi (k), i =1, …, n +1, полученной на k- м шаге, выводится точка xh (k), в которой функция f (x) имеет наибольшее значение (худшая точка). Вместо xh (k) в систему вводится новая точка, выбираемая на отрезке прямой, проходящей через худшую точку и центр тяжести оставшихся n вершин многогранника:

xn +2=  - центр тяжести;

xn +3= xn +2+a (xn +2 - xh)

 

новая точка (“растянутое” отражение наихудшей вершины).

Метод дробления шага.

В данном методе строится релаксационная последовательность точек, т.е. таких точек { xk }, k= 0,1,…, что f (xk) < f (xk-1), k =0,1,…. Точки последовательности { xk } вычисляются по следующему правилу:

xk+1= xk- tkgrad f (xk), k =0,1,… (4)

Начальная точка х0 и начальный шаг t0 задаются пользователем. Величина шага t0 не изменяется до тех пор, пока функция убывает в точках последовательности. Это контролируется путем проверки выполнения условия f (xk+1) - f (xk) <0 (или <-ε). Если условие убывания не выполняется, то величина шага уменьшается, как правило, вдвое, т.е. tk= tk /2.

Метод наискорейшего градиентного спуска

Как и в предыдущем методе, точки релаксационной последовательности { xk }, k= 0,1,… вычисляются по правилу (4). Точка х0 задается пользователем; величина шага tk определяется из условия минимума одномерной функции φ (tk) = f (xk- tk grad f (xk)). Задача минимизации функции φ (tk) может быть решена с использованием необходимого условия минимума =0 с последующей проверкой достаточного условия минимума >0 или с использованием численных методов.

Метод сопряженных направлений (Флетчера - Ривса).

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

Определение. Векторы p и q называются сопряженными относительно матрицы Q, если выполняется равенство pQq =0.

Точки релаксационной последовательности { xk }, k =0,1,… вычисляются по правилу

xk+ 1 = xk- tkdk, k =0,1,…;

dk = - grad f (xk) + β k- 1 dk - 1; (5)

d0= - grad f (x0);

β k-1=║ grad f (xk) ║ 2 grad f (xk- 1 ) ║ 2.

 

Точка х0 задается пользователем; величина шага tk определяется из условия минимума функции φ (t) = f (xk- tdk). Задача минимизации одномерной функции φ (tk) может быть решена с использованием необходимого условия минимума =0 с последующей проверкой достаточного условия минимума >0 или с использованием численных методов. Коэффициент β k- 1 вычисляется из условия сопряженности направлений dk и dk- 1.

Метод Ньютона.

Строится последовательность точек { xk }, k =0,1,…, таких, что , k =0,1,… Точки последовательности { xk } вычисляются по правилу xk+1= xk+ dk, k =0,1,… Точка х0 задается пользователем с учетом знакопостоянства и невырожденности матрицы Гессе в задаваемой начальной точке и близости выбранной точки к предполагаемой точке минимума. Направление спуска определяется для каждого значения k по формуле dk =- H-1 (xk) grad f (xk), где Н - матрица Гессе.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...