1. Исследование функции на безусловный экстремум 3

• Название: 1. Исследование функции на безусловный экстремум 3
• Дата: 20.12.2018
• Размер: 0.69 Mb.
• Имя файла: 1541130846473078.docx
• Тип: Исследование; #61169
• страница: 2 из 6

2. Численные методы безусловной минимизации

Численное решение задачи минимизации (1), как правило, связано с построением минимизирующей последовательности точек x⁰,x¹,x²,…,xⁿ,…, обладающих свойством

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

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

x^k+1=x^k+t_kd^k, k=0,1,....,

где х⁰ начальная точка поиска, d^k приемлемое направление перехода из точки x^k

в точку x^k+1, которое обеспечивает выполнение условий (3) и называется направлением спуска, t_k величина шага. Начальная точка поиска задается, исходя из физического содержания решаемой задачи и априорных данных о наличии и положении точек экстремума.

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

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

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

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

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

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

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

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

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

xⁿ⁺²= - центр тяжести;

xⁿ⁺³= xⁿ⁺²+( 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_kgrad f(x^k), k=0,1,.... (4)

Точка х⁰ задается пользователем; grad f(x^k) – градиент минимизируемой функции, вычисленный в точке x^k; величина шага t₀ задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия

f(x^k+1)-f(x^k) <0 (или <-ε). Если условие убывания не выполняется, величина шага уменьшается, как правило, вдвое, то есть, t_k=t_k/2.

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

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

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

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

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

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

d^k=- grad f(x^k)+β_k-1d^k-1; (4)

d⁰=- grad f(x⁰);

β_k-1=║ grad f(x^k)║²∕║ grad f(x^k-1)║²

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

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

Строится последовательность точек {x^k}, k=0,1,..., таких, что f(x^k)<f(x^k-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), где Н – матрица Гессе.

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

1. 
   Записать необходимые условия экстремума. Аналитически или используя прикладные пакеты найти стационарные точки.
   
2. 
   Проверить выполнение достаточных условий экстремума в найденных стационарных точках. Найти глобальный минимум функции. Оценить обусловленность задачи в точке минимума и “овражность” графика в окрестности точки минимума. Сделать предварительный вывод о работоспособности избранного численного метода.
   
3. 
   Выбрать пакет, в котором будет строиться график. Рекомендации приведены в Приложении. Построить график функции, задавая пределы изменения координат с учетом аналитически найденных точек минимума – максимума.
   
4. 
   Выбрать несколько начальных точек для реализации численного метода. Задать критерий завершения итерационного процесса. Найти минимум. Сравнить результаты с аналитически найденным значением глобального минимума. Исследовать сходимость алгоритма, фиксируя точность определения минимума, количество итераций метода и количество вычислений минимизируемой функции в зависимости от задаваемой точности поиска. Результатом выполнения данного пункта должны быть выводы об объёме вычислений в зависимости от задаваемой точности и начального приближения.
   

Пример выполнения лабораторной работы

Функция: min, x⁰=(-2,-2).

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

Решение.

Примечание: при построении графика используется среда MathCAD 12.1. 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 (требуется дополнительное исследование точки).

Анализ поведения функции в окрестности точки A₀(0;0) показывает, что, придавая х₁ положительное и отрицательное значение при любом х₂, можно получить соответственно положительное и отрицательное значение функции. Таким образом, A₀(0;0) не является ни точкой локального минимума, ни точкой локального максимума.

Н(А₁(1.068;1.668))≈, отрицательно определена, в точке локальный максимум.

Н(А₂(-1.068;-1.668))≈, положительно определена, в точке локальный минимум.

Н(А₃(-0.331;0.848))≈, положительно определена, в точке локальный минимум.

Н(А₄(0.331;-0.848)) ≈, отрицательно определена, в точке локальный максимум.

Точками глобального экстремума являются А₁(1.068;1.668) – глобальный максимум, f (A₁) ≈1.801; А₂(-1.068;-1.668)– глобальный минимум, f (A₂) ≈-1.801.

3. Остальные задания реализованы на языке СИ, для чего написаны классы для работы с векторами и матрицами (CVector и CMatrix) и использующее их приложение. В методе наискорейшего спуска для одномерной минимизации используется метод золотого сечения. Для отыскания собственных чисел матрицы Гессе применяется метод Якоби, для построения обратной матрицы – метод Жордана-Гаусса.

В начале работы программа выводит информацию о стационарных точках:

Stationary dots:

x1 x2 f(x1,x2) Extreme

1.067890 1.667566 1.801131 LOC MAX

-1.067890 -1.667566 -1.801131 LOC MIN

-0.331077 0.848071 -0.144426 LOC MIN

0.331077 -0.848071 0.144426 LOC MAX

GLOBAL MIN: x(-1.067890, -1.667566)

f(x) = -1.801131

GLOBAL MAX: x(1.067890, 1.667566)

f(x) = 1.801131

Затем устанавливается начальная точка x⁰(-2,-2), функция исследуется на выпуклость/вогнутость в этой точке, выводится число обусловленности матрицы Гессе:

x0(-2.000000, -2.000000) Hessian: Alternating sign

f(x0) = -0.398297

cond H(x0) = 4.751665

Таким образом, квадратичная форма, соответствующая матрице Н(-2,-2), является знакопеременной. Функция не является “овражной” в окрестности точки, и допустимо применение метода градиентного спуска.

Далее запускается метод наискорейшего градиентного спуска, и выполняются 2 итерации.


Steepest descent method:

x2(-1.200031, -1.706888) Hessian: Convex

grad_f(x2) = (-0.963083, 0.275166)

f(x2) = -1.741440

В результате 2 итераций мы получили точку, достаточно близкую к точке глобального минимума.

Теперь из точки стартует метод Ньютона с поправкой гессиана. Результат двух итераций:

Newton method:

x2(-2.735431, -2.306328) Hessian: Alternating sign

grad_f(x2) = (-0.110421, 0.031948)

f(x2) = -0.018516

Видно, что метод расходится. Начальная точка выбрана неудачно; увеличение числа итераций приводит к дальнейшему расхождению метода. Это объясняется тем, что метод Ньютона применим в окрестности точки минимума.

Анализируя линии уровня функции, выберем начальную точку ближе к оптимальной. Например, :

x0(-1.000000, -2.000000) Hessian: Convex

f(x0) = -1.471518

cond H(x0) = 3.786885

Newton method:

x2(-1.047041, -1.722604) Hessian: Convex

grad_f(x2) = (0.379214, -0.339841)

f(x2) = -1.787758

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

Теперь возьмем начальную точку еще ближе к , например :

x0(-1.000000, -1.500000) Hessian: Convex

f(x0) = -1.752302

cond H(x0) = 3.857905

Newton method:

x2(-1.067889, -1.667566) Hessian: Convex

grad_f(x2) = (0.000000, 0.000000)

f(x2) = -1.801131

Метод Ньютона достиг точки глобального минимума, об этом говорит практически нулевой вектор-градиент.

Точное значение отличается от найденного на 4.729∙10^-7(по модулю).

Выводы

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

С помощью метода градиентного спуска удалось улучшить целевую функцию без каких-либо дополнительных действий. Метод Ньютона при выборе в качестве начальной точки x⁰(-2,-2) не сошелся. Проблема была решена заменой начальной точки на более подходящую для данного метода. Это позволило за две итерации прийти в точку глобального минимума. Полученные результаты хорошо согласуются с теорией.

Разработанные классы CVector и CMatrix могут применяться в будущих проектах.