Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

* ) Из формул (2.14) и (2.18) следует приблизительно одинаковая эффективность обоих методов деления отрезка пополам. В табл. 2.5 представлены значения (N) для второго из них

2.2.3. МЕТОД ПАРАБОЛ

Поиск точки минимума методами исключения отрезков основан на сравнении значений функции в двух точках. При таком сравнении раз­ности значений f (x) в этих точках не учитываются, важны только их знаки.Учесть информацию, содержащуюся в относительных изменениях значенийf (x) в пробных точках, позволяют методы полиномиальной ап­проксимации, основная идея которых состоит в том, что для функции f (x) строится аппроксимирующий многочлен, и его точка минимума слу­жит приближением к х*. Для эффективного использования этих мето­дов на функцию f (x), кроме унимодальности, налагается дополнительное требование достаточной гладкости (по крайней мере, непрерывности).Обоснованием указанных методов является известная из матема­тического анализа теорема Вейерштрасса об аппроксимации [4], согласно которой непрерывную на отрезке функцию можно с любой точностью приблизить на этом отрезке некоторым полиномом .Для повышения точности аппроксимации можно, во–первых, увеличивать порядок полинома и, во–вторых, уменьшать длину отрезка аппроксимации. Первый путь приводит к быстрому усложнению вы­числительных процедур, поэтому на практике используются аппрок­симирующие полиномы не выше треть­его порядка. В то же время уменьшить отрезок, содержащий точку минимума унимодальной функции, не представляет особого труда.В простейшем методе полиномиальной аппроксимации – методе парабол используются полиномы второго порядка. На каждой итерации этого метода строят квадратный трехчлен, график которого (парабола) проходит через три выбранные т очки графика функции f (x) (рис. 2.8).Рис. 2.8. Опишем метод парабол. Рассмотрим унимодальную на отрезке [а; b] функцию f (x), достигающую минимума во внутренней точке этого отрезка. Выберем три точки х₁, х₂ и х

---

₃ отрезка [а; b], для которых выполняются неравенства:х₁ < х₂ < х₃ , f (x₁)  f (x₂)  f (x₃). ^*(2.19)Из унимодальности f (x) следует, что х*  [х₁; х₃]. Построим квадратный трехчлен q(x) = а₀ + a₁(x–x₁) + a₂(x–x₁)(x–x₂),график которого проходит через точки (x₁,f (x₁)), (x₂,f (x₂)) (x₃,f (x₃)) графика функции f (x). Будем считать, что если хотя бы одно из неравенств (2.19) дляf (x_i) является строгим (если f (x₁)=f (x₂) =f (x₃), то поиск точки х* на этом закончен, так как из унимодальности функции f (x) следует, что она достигает минимума в каждой точке отрезка [х₁; х₃]). Тогда из (2.19) следует, что ветви искомой параболы направлены вверх, а точка минимума трехчлена q(x) принадлежит отрезку [х₁; х₃].Определяя коэффициенты а₀, a₁ и a₂ из системы уравнений:q(x₁) = f (x₁) = f ₁ ;q(x₂) = f (x₂) = f ₂ ;q(x₃) = f (x₃) = f ₃ ,где q(x) = а₀ + a₁(x–x₁) + a₂(x–x₁)(x–x₂).находим , , .Точку минимума квадратного трехчлена q(x) вычислим, приравняв его производную к нулю. Получим(2.20)Число из (2.20) служит очередным приближением метода парабол к х*. Далее описанная процедура повторяется для новых точек x₁,x₂,x₃,удовлетворяющих неравенствам (2.19).Выбрать эти точки среди x₁,x₂

---

,x₃, и можно с помощью перехода от исходного к новому отрезку [x₁; x₃], содержащему точку х*, ме­тодом исключения отрезков. Для этого перехода используют проб­ные точки x₂ и и сравнивают значенияf (x) в этих точках *⁾. Начало и конец нового отрезка, а также пробная точка, попавшая на него, образуют тройку точек, обладающих свойством (2.19).

Заметим, что на каждой итерации метода парабол, кроме первой, определяется только одно новое значениеf (x).

Условием окончания поиска служит близость к нулю разности  чисел , найденных на данной и предыдущей итерациях, т.е. неравенство ||  , где – заданное число, характеризующее точность определения х*.

Перечислим основные шаги алгоритма метода парабол.

Шаг 1. Выбрать точки x₁,x₂,x₃, удовлетворяющие условиям (2.19). Перейти к шагу 2.

Шаг 2. Найти по формуле (2.20). На первой итерации перейти к шагу 4, на остальных – к шагу 3.

Шаг 3. Проверка на окончание поиска. Сравнить модуль разно­сти значений на данной и предыдущей итерациях  с числом . Если ||  , то поиск завершить, полагая х*  , f  *  f (x), иначе – перейти к шагу 4.

Шаг 4. Вычислить значение f ( ). Перейти к шагу 5.

Шаг 5. Определить новую тройку чисел x₁,x₂,x₃. Присвоить f (x₁), f (x₂) иf (x₃) соответствующие значенияf (x) найденные ранее. Пе­рейти к шагу 2.
Пример 2.8. Метод парабол.

Решить задачуf (x) =х⁴ + е^–x min, х [0; 1] с точностью ||   = 0,0025.
Итерация 1.

---

Шаг 1. Выберем точки х₁ = 0,25, х₂ = 0,5, х₃, = 0,75. Функция принимает в этих точках значения, соответственно f ₁ = 0,7827, f ₂ = 0,6690, f ₃ = 0,7888, удовлетворяющие неравенствам (2.19). Переходим к шагу 2.Шаг 2. По формуле (2.20) находим: = 0,4968. Переходим к шагу 4.Шаг 4. Вычисляемf ( ) = 0,6694. Переходим к шагу 5.Шаг 5. На данной итерации имеем: x₁ < <x₂ <x₃, f ( ) > f (x₂), сле­довательно, x*[ ; x₃]. Поэтому полагаем: x₁ = =0,4968, f (x₁) =f ( ) = 0,6694, а точки х₂ , x₃ и значенияf (x) в них не изменяются. Переходим к сле­дующей итерации, начиная с шага 2. Итерация 2 .Шаг 2. Находим = 0.5224. Переходим к шагу 3.Шаг 3.  =0.4968–0,5224= 0,026 > 0,0025, поэтому переходим к шагу 4.Шаг 4. Вычисляемf ( ) =0,6676. Переходим к шагу 5.Шаг 5. На этой итерации x₁ <x₂ < <x₃, f (x₂) > f ( ), поэтому x*[x₂; x₃] и полагаем x₁ =x₂ = 0,5, f (x₁) =f (x₂) = 0,6690, x₂ = = 0,5524, f (x₂) = f ( ) = 0,6676, а точка x₃ и значение f (x₃) остаются прежними. Пере­ходим к следующей итерации.Итерация 3.Ш а г 2. Находим

---

= 0,5248. Переходим к шагу 3.

Ш а г 3. Определяем  =0,5224–0,5248=0,0024 < 0,0025, т.е. требуемая точность достигнута. Поэтому полагаем х* = = 0,525.

Отметим, что в результате пяти вычислений f (x) точка х* была найдена с весьма высокой точностью (сравните с точным до четвертого знака значе­нием х*= 0,5283 )

---