г) Метод покоординатного спуска: m=1, h = ej, j=k (mod n). Шаги делаются по координатным осям, выбирае­мым в циклическом порядке:

(11)

При этом

Рассмотрим задачу поиска минимума функции f(x): \mathbb{R}^n \to \mathbb{R} , записываемую в виде:

f(x) \to \min_{x \in \mathbb{R}^n}

В этой постановке описан метод покоординатного спуска, решающий поставленную задачу. Также приведена теорема сходимости метода покоординатного спуска.

Алгоритм

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

Рис. 3. Иллюстрация метода

Вход: функция f: Rn→ R

Выход: найденная точка оптимума х

Инициализация некоторым значением x0 Rn Повторять:
    для i=1,..,n фиксируем значения всех переменных кроме xi, получая одномерную функцию f(xi) проводим одномерную оптимизацию по переменной xi, любым методом одномерной оптимизации если выполен критерий останова (варианты описаны ниже), то возвращаем текущее значение x=(x1,…,xn).

Критерий останова

Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях. Некоторые из них:

||x^{[k+1]}-x^{[k]}||\leq\eps ||f(x^{[k+1]})-f(x^{[k]})||\leq\eps

Здесь x^{[k]} \in \mathbb{R}^n- значение, полученное после k-го шага оптимизации. ε - наперед заданное положительное число.

Сходимость метода

Рис.2

Рис. 4

Легко убедится, что существуют функции, когда метод координатного спуска не приводит даже в локальный оптимум.

Пусть линии уровня образуют истинный овраг (рис. 4), когда спуск по любой координате приводит на <<дно>> оврага, а любое движение по следующей координате (пунктирная линия) ведет на подъем. Никакой дальнейший спуск по координатам в данном случае невозможен, хотя минимум еще не достигнут.

НЕ нашли? Не то? Что вы ищете?

Теорема о сходимости метода покоординатного спуска.

Для простоты рассмотрим функцию двух переменных f(x,y). Выберем некоторое начальное приближение (x0,y0) и проведем линию уровня через эту точку. Пусть в области G, ограниченной этой линией уровня, выполняются неравенства, означающий положительную определенность квадратичной формы:

f_{xx}''\geq

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

Пример. Для исследования сходимости метода покоординатного спуска была выбрана функция:

f(x_1,x_2)=(x_1-1)^2+(x_2-1)^2-x_0*x_1.

Начальное приближение - точка (10,10). Использован критерий останова:

||f(x^{[k+1]})-f(x^{[k]})||\leq 10^{-5}

Для решения одномерных задач оптимизации использован метод золотого сечения.

Метод получил точность 1e-8 за 7 итераций. Отсюда можно сделать вывод, что метод координатного спуска сходится неплохо на примерах, для которых он применим.

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

Метод координатного спуска является простым в реализации методом оптимизации. Главным недостатком метода является его ограниченная применимость.

д) Метод случайного покоординатного спуска: m=1, h =ej, где j принимает значения 1, ..., п с равной вероятностью. Шаг делается, как и выше, по координатным осям, но они вы­бираются в случайном порядке.

е) Метод случайного поиска: m=1, h — случайный вектор, равномерно распределенный на единичной сфере. Здесь движе­ние производится по случайному направлению, а знак и вели­чина шага определяются разностным отношением:

(12)

Сходимость всех методов гарантируется условием αk→0.

Скорость сходимости зависит от гладкости f(x) и способа выбора αk. С точки зрения погрешностей вычисления выгодно брать αk большим. Так как чем меньше αk, тем больше влияние ошибок округления при вычислении разностных отношений (в (1) приходится вычислять разность двух близких чисел и де­лить на малое число; это всегда связано с потерей точности). Однако для больших αk ухудшается точность аппроксимации (лемма 1). Можно показать, что можно обеспечить в описанных выше методах сходимость со скоростью геометрической прогрессии, если

где q <1 — некоторое число.

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

(13)

а γk выбирается из условия скорейшего спуска:

(14)

Сравним три способа выбора sk:

- симметричная разностная аппроксимация градиента

(15)

(последнее равенство в силу (5));

- покоординатный спуск

(16)

- случайный поиск

(17)

где hk — равномерно распределенный на единичной сфере век­тор. Таким образом, (14), (15) совпадает с методом наискорейшего спуска, а (14), (16) хорошо известен в линейной алгебре как метод Гаусса — Зейделя.

Соотношение скоростей сходимости методов зависит от раз­личных причин; приведем несколько крайних случаев. Если А = I, то (14), (15) и (14), (16) приводят к решению за 1 шаг, тогда как метод случайного поиска сходится в среднеквадратич­ном не быстрее некоторой геометрической прогрессии. Если то метод (14), (16) конечен, тогда как (14), (15) — нет. Наконец, если задача плохо обусловлена (), то можно показать, что метод случайного поиска схо­дится быстрее градиентного (с учетом разницы в числе вычис­лений f(x) на одной итерации методов). Грубо говоря, для таких задач случайное направление в среднем лучше указывает на решение, чем антиградиент. Метод Гаусса — Зейделя имеет еще один резерв ускорения сходимости — если заменить в нем γk на αγk, 1<α<2 (так называемая сверхрелаксация), то оказы­вается, что в ряде случаев сходимость резко улучшается.

В целом можно рекомендовать в классе поисковых методов описанного типа метод покоординатного спуска как по его про­стоте, так и по скорости сходимости.

5.3. Интерполяция кубическими сплайнами

Постановка математической задачи

Одной из основных задач оптимизации является задача об интерполяции функций. Пусть на отрезке a\le \x\le \b задана сетка

\omega=\{x_i:x_0=a<x_1<\cdots<x_i<\cdots<x_n=b\}

и в её узлах заданы значения функции y(x), равные

y(x_0)=y_0,\cdots,y(x_i)=y_i,\cdots,y(x_n)=y_n.

Требуется построить интерполянту — функцию f(x), совпадающую с функцией y(x) в узлах сетки:

f(x_i)=y_i, i=0,1,\cdots,n. ( 1 )

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

Интерполируюшие функции f(x), как правило строятся в виде линейных комбинаций некоторых элементарных функций:

f(x)=\sum_{k=0}^N {c_k\Phi_k(x)},

где \{\Phi_k(x)\}— фиксированный линейно независимые функции, c_0, c_1, \cdots, c_n— не определенные пока коэффициенты.

Из условия (1) получаем систему из n+1 уравнений относительно коэффициентов {ck}:

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97