Основы теории оптимизации (стр. 35 )

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

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

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

Шаг 1. Выбрать точки х1, х2, х3 удовлетворяющие условиям (1).

Перейти к шагу 2.

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

Шаг 3. Проверка на окончание поиска. Сравнить модуль разности значений на данной и предыдущей итерациях ∆ с числом ε. Если |∆|≤ε, то поиск завершить, полагая х* ≈ , f*≈ f (х), иначе - перейти к шагу 4.

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

Шаг 5. Определить новую тройку чисел х1, х2, х3 . Присвоить f(x1), f(x2) и f(x3) соответствующие значения f(x), найденные ранее. Перейти к шагу 2.

Пример. Метод парабол

Решить задачу с точностью

Итерация 1

Шаг 1. Выберем точки: х1=0,25, х2 =0,5, х3 =0,75. Функция принимает в этих точках значения, соответственно f1 = 0,7817, f 2 = 0,6690, f 3 = 0,7888, удовлетворяющие неравенствам (1). Переходим к шагу 2.

Шаг 2. По формуле (56) находим =0,4968. Переходим к шагу 4.

Шаг 4. Вычисляем: f () = 0,6694 . Переходим к шагу 5.

Шаг 5. На данной итерации имеем

следовательно, Поэтому полагаем х2 = = 0,4968,

а точки х2, х3 и значения f (х) в них не изменяются. Переходим к следующей итерации, начиная с шага 2.

Итерация 2

Шаг 2. Находим: = 0,5224 . Переходим к шагу 3.

Шаг 3. поэтому переходим к шагу 4.

Шаг 4. Вычисляем: f ()= 0,6676 . Переходим к шагу 5.

Шаг 5. На этой итерации

поэтому полагаем:

а точка х3 и значение f(х3) остаются прежними. Переходим к следующей итерации.

Итерация 3

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

Шаг 3.

Определяем т. е. требуемая точность достигнута. Поэтому полагаем

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

Численное решение задачи минимизации, как правило, связано с построением минимизирующей последовательности точек x0,x1,x2,…,xn,…, обладающих свойством

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

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

x k+1=x k+t kd k, k=0,1,…,

где х0 - начальная точка поиска; dk - приемлемое направление перехода из точки xk в точку xk+1, которое обеспечивает выполнение условий (3) и называется направлением спуска; tk - величина шага. Начальная точка поиска задается исходя из физического содержания решаемой задачи и априорных данных о существовании и положении точек экстремума.

4.3. Градиентный метод как классический метод оптимизации

1. Эвристические соображения. Проанализируем один из наиболее важных в идейном отношении метод безусловной оптимизации – градиентный. Это метод, редко применяемый на практике в «чистом виде», служит моделью для построения более реалистических алгоритмов. На примере дан­ного метода будет подробно разобран вопрос о сходимости — будут даны различные доказательства сходимости, описана общая техника построения доказательств, обсуждены соотно­шения между теоретическими результатами о сходимости и практическим использованием метода.

Предположим, что в любой точке х можно вычислить гра­диент функции f(x). В такой ситуации наиболее простым ме­тодом минимизации f(x) является градиентный, в котором, на­чиная с некоторого начального приближения х0, строится ите­рационная последовательность

(1)

где параметр γk≥0 задает длину шага. К методу (1) можно прийти из разных соображений.

Во-первых, при доказательстве необходимых условий экстре­мума можно использовать то обстоятельство, что если в точке х условие экстремума не выполняется ((x) ≠ 0), то значение функции можно уменьшить, перейдя к точке х —τ(x) при достаточно малом τ > 0. Итеративно применяя этот прием, приходим к методу (1).

Во-вторых, в точке хk дифференцируемая функция f(x) при­ближается линейной с точно­стью до членов порядка о(х-хk). Поэтому можно искать ми­нимум аппроксимации fk(x) в окрестности хk. Например, можно задаться некоторым εk и решить вспомогательную задачу

(2)

Ее решение естественно принять за новое приближение xk+1. Можно остаться в окрестности хk и иначе, добавив к fk(x) «штраф» за отклонение от хk. Например, можно решить вспомо­гательную задачу

(3)

и ее решение взять в качестве xk+1. Читателю предоставляется убедиться в том, что решение задач (2), (3) задается форму­лой (1).

В-третьих, можно в точке хk выбрать направление локаль­ного наискорейшего спуска, т. е. то направление для которого достигается минимум f'(xk; у). Используя фор­мулу

f'(x; у)=φ′(0)=( f(x), y )

для производной по направлению, получаем

(4)

Таким образом, направление наискорейшего спуска проти - воположно направлению градиента.

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

2. Сходимость. Рассмотрим простейший вариант градиентно­го метода, в котором γk ≡γ:

(5)

Нас будет интересовать поведение этого метода при различных предположениях относительно f(x) и γ.

Теорема 1. Пусть f(x) дифференцируема на Rn, градиент f(x) удовлетворяет условию Липшица:

(6)

f(x) ограничена снизу:

(7)

и γ удовлетворяет условию

(8)

Тогда в методе (5) градиент стремится к 0: