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

f(х[k+1]) = f(x[k] – akf’(x[k])) < f(x[k]).

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

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

Градиентные методы. Общие соображения и определения.

Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации

f(x) → min,

(1)

где f: Rm → R, укладываются в следующую грубую схему. Начиная с некоторого x0 Rm, строится последовательность {xn} Rm такая, что

f(xn+1) < f(xn)

(2)

при всех n N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xn к xn+1) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).

Мы будем говорить, что метод, начиная с данного x0 Rm,

а) условно сходится, если последовательность {xn} релаксационна и

f ′(xn) → Θ при n → ∞;

б) сходится, если

xn → x* = argmin f(x) при n → ∞;

в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q [0, 1)

||xn – x*|| ≤ Cqn;

(3)

г) сверхлинейно сходится, если для любого q (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3);

д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q [0, 1) и всех n N

||xn – x*|| ≤ Cq2n.

Если эти свойства выполняются только для x0 достаточно близких к x*, то как всегда добавляется эпитет "локально".

Будем говорить, что на данной последовательности метод сходится с порядком p (или имеет p-ый порядок сходимости), если при некотором C

||xn+1 – x*|| ≤ C||xn – x*||p.

Эвристические соображения, приводящие к градиентным методам.

Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xn}, рекуррентно определяемая формулой

xn+1 = xn – αf ′(xn),

(4)

где α - некоторое положительное число, будет релаксационной.

К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xn. Заменим в шаре B(xn, ε) с центром в точке xn функцию f ее линейным (вернее, афинным) приближением:

f(x) ≈ φ(x) ≝ f(xn) + (f ′(xn), x – xn)

(функция φ аппроксимирует f в окрестности точки xn с точностью o(x – xn)). Разумеется, (линейная) безусловная задача φ(x) → min неразрешима, если f ′(xn) ≠ Θ. В окрестности же B(xn, ε) функция φ имеет точку минимума. Эту точку естественно взять за следующее приближение xn+1.

4.2. Метод парабол

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

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

Обоснованием указанных методов является известная из математического анализа теорема Вейерштрасса об аппроксимации,

согласно которой непрерывную на отрезке функцию можно с любой точностью приблизить на этом отрезке некоторым полиномом.

Для повышения точности аппроксимации можно, во-первых, увеличивать порядок полинома и, во-вторых, уменьшать длину отрезка аппроксимации. Первый путь приводит к быстрому усложнению вычислительных процедур, поэтому на практике используют аппроксимирующие полиномы не выше третьего порядка. В то же время уменьшение отрезка, содержащего точку минимума унимодальной функции, не представляет особого труда.

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

Рис. 1. Иллюстрация к методу парабол

Опишем метод парабол. Рассмотрим унимодальную на отрезке [а; b] функцию f(x), достигающую минимума во внутренней точке этого отрезка. Выберем три точки x1, x2 и х3 отрезка [а; b], для которых выполняются неравенства:

(1)

Из унимодальности f(x) следует, что х* [x1;х3].

Построим квадратный трехчлен

график которого проходит через точки графика функции f(x). Будем считать, что хотя бы одно из неравенств (1) для f(x) является строгим (если то поиск точки х на этом закончен, так как из унимодальности функции f(x) следует, что она достигает минимума в каждой точке отрезка [х1;х3]). Тогда из (1) следует, что ветви параболы направлены вверх, а точка минимума трехчлена q(x) принадлежит отрезку [х1;х3].

Определяя коэффициенты а0, а1 и а2 из системы уравнений

находим:

Точку минимума квадратного трехчлена q(x) вычислим, приравняв его производную к нулю. Получим

(2)

Число из (2) служит очередным приближением метода парабол к х*. Далее описанная процедура повторяется для новых точек х1, х2, х3, удовлетворяющих неравенства (1).

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