Лабораторная работа: Методы оптимизации функций многих переменных

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

Направление от старого базиса к новому задает направление ускорения поиска: в качестве следующей точки минимизирующей последовательности проверяется точка 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^{n +2} =- центр тяжести;

x^{n +3} = x^{n +2} +a (x^{n +2} - 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_k gradf ( 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_k gradf ( x^k )). Задача минимизации функции φ ( t_k ) может быть решена с использованием необходимого условия минимума =0 с последующей проверкой достаточного условия минимума >0 или с использованием численных методов.

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

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

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

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

x^{k + 1} = x^k - t_k d^k , k =0,1,…;

d^k = - gradf ( x^k ) + β_{k- 1} d^{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).