Методы оптимизации (стр. 10 из 11)

(9)

где интервал [a,b]задается пользователем.

Если функция

достаточно сложна, то возможна ее замена полиномом второй или третьей степени и тогда шаг может быть определен из условия при выполнении условия .

При численном решении задачи определения величины шага степень близости найденного значения

к оптимальному значению , удовлетворяющему условиям , , зависит от задания интервала [a,b]и точности методов одномерной минимизации.

Построение последовательности {х_k} заканчивается в точке х_k, для которой

, где - заданное число, или при (М - предельное число итераций), или при двукратном одновременном выполнении двух неравенств , , где - малое положительное число.

Вопрос о том, может ли точка х_kрассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного исследования, которое описано ниже.

Сходимость

Утверждение. Пусть функция f(x) дважды непрерывно дифференцируема и сильно выпукла на Rⁿ, а ее матрица Гессе Н(х) удовлетворяет условию Липшица

.

Тогда последовательность {х_k} сходится независимо от выбора начальной тонки х₀ к точке минимума х_* с квадратичной скоростью

,

где т - оценка наименьшего собственного значения матрицы.

Замечание. Сходимость к точке минимума метода Ньютона-Рафсона гарантируется независимо от выбора начального приближения лишь для сильно выпуклых функций. Поэтому при практическом использовании метода Ньютона-Рафсона следует:

а) анализировать матрицу Гессе

на выполнение условия >0,k= 0,1,..., и заменять формулу на формулу метода градиентного спуска в случае его невыполнения;

б) производить анализ точки х_kс целью выяснения, является ли она найденным приближением искомой точки х_*.

Процедура решения задачи

1. Используя алгоритм Ньютона-Рафсона, построить точку х_k, в которой выполняется по крайней мере один критерий окончания расчетов.

2. Так как

, то осуществить проверку выполнения достаточных

условий минимума

>0. Если условие выполнено, то точка х_kможет рассматриваться как найденное приближение точки минимума х_*. Проверку выполнения достаточных условий минимума можно заменить проверкой функции f(x) на выпуклость.

Пример 2.2. Найти локальный минимум функции

.

□ I. Определение точки х_k, в которой выполняется по крайней мере один критерий окончания расчетов.

1. Зададим х₀,

М: х₀ = (0,5; 1)^Т, ; М=10. Найдем градиент функции в произвольной точке и матрицу Гессе .

2. Положим k= 0.

3⁰. Вычислим

: = (3; 2,5)^Т.

4⁰. Проверим выполнение условия

: = 3,9 > 0,1.

Переходим к шагу 5.

5⁰. Проверим выполнение условия

: k =0 <10. Переходим к шагу 6.

6⁰. Вычислим

: .

7⁰. Вычислим

: .

8⁰. Проверим выполнение условия

>0. Так как , , то согласно критерию Сильвестра > 0.

Поэтому найдем

.

9⁰. Определим:

.

10⁰. Определим

из условия .

Получаем

.

Из условия

находим = 1. При этом , т.е. найденная величина шага обеспечивает минимум функции .

11°. Вычислим

: .

12°. Проверим выполнение условий

, :

= 1,12 > 0,15; = 2 > 0,15.

Положим k =1 и перейдем к шагу 3.

3¹. Вычислим

: .

4¹. Проверим выполнение условия

: = 0 < 0,1. Расчет

окончен: х_*= х₁.

II. Анализ точки х₁.

Точка х_* = (0;0)^T - точка локального и одновременно глобального минимума f(x).

На рис. 9траектория спуска изображена штрихпунктирной линией. ■

Заключение

В результате проделанной работы можно сделать следующие выводы:

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

2. Многие алгоритмы решения задач с ограничениями включают минимизацию без ограничений как некоторый этап.

3. Различные методы спуска отличаются друг от друга способами выбора направления спуска и длины шага вдоль этого направления.

4. Среди всех наиболее употребительных методов методы второго порядка требуют для получения результата с заданной точностью наименьшего числа шагов (итераций).