Методы оптимизации функций многих переменных (стр. 2 из 6)

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

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

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

xⁿ⁺²=

- центр тяжести;

xⁿ⁺³= xⁿ⁺²+a (xⁿ⁺² - x^h)

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

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

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

x^k+1=x^k-t_kgradf (x^k), k=0,1,… (4)

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

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

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

=0 с последующей проверкой достаточного условия минимума >0 или с использованием численных методов.

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

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

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

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

x^k+1=x^k-t_kd^k, k=0,1,…;

d^k= - gradf (x^k) +β_k-1d^{k - 1}; (5)

d⁰= - gradf (x⁰);

β_k-1=║gradf (x^k) ║²∕║gradf (x^k-1) ║².

Точка х⁰ задается пользователем; величина шага t_k определяется из условия минимума функции φ (t) =f (x^k-td^k). Задача минимизации одномерной функции φ (t_k) может быть решена с использованием необходимого условия минимума

=0 с последующей проверкой достаточного условия минимума >0 или с использованием численных методов. Коэффициент β_k-1вычисляется из условия сопряженности направлений d^k и d^k-1.

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

Строится последовательность точек {x^k}, k=0,1,…, таких, что

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

2. Порядок выполнения лабораторной работы

Записать необходимые условия экстремума. Аналитически или используя прикладные пакеты найти стационарные точки.

Проверить выполнение достаточных условий экстремума в найденных стационарных точках. Найти глобальный минимум функции. Оценить обусловленность задачи в точке минимума и овражность графика в окрестности точки минимума. Сделать предварительный вывод о работоспособности избранного численного метода.

Выбрать пакет, в котором будет строиться график. Рекомендации приведены в приложении. Построить график функции, задавая пределы изменения координат с учетом аналитически найденных точек минимума - максимума.

Выбрать несколько начальных точек для реализации численного метода. Задать критерий завершения итерационного процесса. Найти минимум. Сравнить результаты с аналитически найденным значением глобального минимума. Исследовать сходимость алгоритма, фиксируя точность определения минимума, количество итераций метода и количество вычислений минимизируемой функции в зависимости от задаваемой точности поиска. Результатом выполнения данного пункта должны быть выводы об объёме вычислений в зависимости от задаваемой точности и начального приближения.

3. Пример выполнения лабораторной работы^[1]

Функция:

min, x⁰= (-2,-2).

Методы: градиентного спуска и Ньютона.

Решение: 1. Построим график функции и линии уровня (рис.1).

Примечание: при построении графика используется среда MathCAD.

Рис.1. Графики функции

и линий уровня

2. Решим задачу минимизации аналитически.

Система для нахождения стационарных точек из условия равенства нулю градиента имеет вид

Если x₁x₂ =0, тоиз системы следует, что x₁ =0 иx₂ =0.

Первая стационарная точка - A₀ (0; 0).

Если

x₁x₂ ≠0, то

Подставим х₁ в первое уравнение:

Введем замену

:

Обозначим

, .

Получаем остальные стационарные точки:

;

;

;

.

Приближенные числовые координаты найденных точек:

А₀ (0; 0), А₁ (1.068; 1.668), А₂ (-1.068; - 1.668), А₃ (-0.331; 0.848), А₄ (0.331;0.848).

Построим и исследуем на знакоопределенность матрицу Гессе в точках А₀,…, А₄.

;

.

H (A₀ (0; 0)) =0

(требуется дополнительное исследование точки).