Метод покоординатного спуска

В самом простом варианте спуск осуществляется покоординатно, т.е. в качестве очередного направления спуска выбирается направление одной из координатных осей. Рассмотрим некоторые особенонсти этого метода на примере функции трех переменных Ф(x,y,z). Выберем нулевое приближение (x0,y0,z0). Фиксируем значения двух координат y0,z0 и рассмотрим функцию f1(x)=Ф(x,y0,z0). Используя любой известный метод одномерной минимизации, найдем минимум функции f1(x) и обозначим его x1. Геометрически это будет означать, что мы сделали шаг из точки (x0,y0,z0) в точку (x1,y0,z0) по направлению, параллельному оси x:   Затем из точки (x1,y0,z0) сделаем шаг по направлению, параллельному оси y, т.е. рассмотрим функцию f2(y)=Ф(x0,y,z0), найдепм ее минимум и обозначим его через y1. Второй шаг приводит нас в точку (x1,y1,z0). Наконец, третий шаг - спуск параллельно оси z приведет нас в точку (x1,y0,z1), завершая тем самым цикл спусков. Если теперь повторять циклы спуска вновь и вновь, то в некоторых случаях можно спуститься на самое дно. Но бывают ситуации, когда такой метод не работает, - например, такая, как показано на следующем рисунке:   В ситуации, изображенной на этом рисунке, линии уровня образуют истинный овраг. И как только мы попали на дно оврага, никакой дальнейший спуск по направлениям координат невозможен несмотря на то, что минимума мы еще не достигли. В таких ситуациях говорят, что метод спуска по координатам не сходится к минимуму. В случае разрешимого оврага метод коорлдинатного спуска сходится, но очень медленно. Метод спуска по координатам несложен и программируется очень легко. Однако сходится он медленно, а при наличии оврагов - очень плохо. Поэтому его используют обычно в качестве первой попытки при поиске минимума. Пусть f(x1,x2,...,xn) - функция n переменных. Цикл с номером k+1 состоит из n шагов. На первом шаге производится спуск по координате x1:   т.е. решается задача минимизации функции одной переменной x1. На втором шаге производят спуск по координате x2:   т.е. ищется минимум функции одной переменной x2. Аналогично осуществляют остальные шаги. Но последнем n-том шаге   В результате находят очередное (k=1)-тое приближение. Различие между разными вариантами реализации метода координатного спуска заключается в выборе в характере выбора параметров счета, - таких как скорость уменьшения величины шага спуска от цикла к циклу, критерии останова и др. В примере приведены три варианта программ, реализующих описанный выше подход.

Метод градиентного спуска

Отличие между различными методами спуска заключается в выборе направления спуска. В самом простом варианте спуск осуществляется покоординатно, т.е. в качестве очередного направления спуска выбирается направление одной из координатных осей. Однако гораздо более выгодно осуществлять спуск в направлении, противоположном направлению наискорейшего возрастания функции, которое, как известно, определяется вектором-градиентом функции f(x1, x2,…, xn):   Это направление в литературе иногда называют направлением антиградиента. Соответствующий итерационный процесс может быть описан выражением вида   или, в координатной форме,   В качестве критерия останова вычислительного процесса можно использовать одно из двух условий: 1) условие малости приращения аргумента   условие малости градиента   Здесь ε и γ - заданные малые величины. Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага аk. В методе градиентного спуска с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг аk обеспечит убывание функции, т. е. выполнение неравенства

Метод наискорейшего спуска

При методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг аk обеспечит убывание функции, т. е. выполнение неравенства   Однако это может привести к необходимости проводить неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума (зацикливанию). Из-за сложности получения необходимой информации для выбора величины шага методы с постоянным шагом применяются на практике редко. Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется. Рассмотрим применяемые на практике варианты таких методов. При использовании метода наискорейшего спуска на каждой итерации величина шага аk выбирается из условия минимума функции f(x) в направлении спуска, т. е.   Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции   Алгоритм метода наискорейшего спуска Задаются координаты начальной точки x^(0) В точке x^(k), k = 0, 1, 2,... вычисляется значение градиента f'(x^(k)) Определяется величина шага ak, путем одномерной минимизации по а функции   Определяются координаты точки x^(k+1)=x^(k)−akf'(x^(k)) Проверяются условия останова итерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Критерии окончания итераций могут быть следующие где ε1, ε2, ε3 − заданные положительные числа. Иногда требуют одновременного выполнения двух и даже трех критериев. К сожалению, надежные критерии окончания счета, которые были бы применимы к широкому классу задач и гарантировали достижение нужной точности, пока неизвестны. По сходимости, метод наискорейшего спуска ничем не отличается от метода спцуска по координатам: при попавдании траектории спуска в истинный овраг счет останавливается, а в разрешимом овраге сильно замедляется. В некоторых случаях величина шага нормируется во модулю градиента, в результате чего в расчетные формулы входит не значения компонент вектора-градиента, а направляющие косинусы этих компонент. В других случаях скорость спуска, наоборот, увеличивается на каждой итерации для того, чтобы "побыстрее добежать" до дна.

Метод спуска c ускорением

Для улучшения метода наискорейшего спуска предлагают самые разнообразные поправки к алгоритму: например, совершают по каждому направлению спуск не точно до минимума. В некоторых случаях по направлению антиградиента делается только один маленький шаг, после чего меняют направление спуска. Это приводит к движению по некоторой кривой r(t), являющейся решением системы обыкновенных дифференциальных уравнений dr/dt=−gradФ(r(t)). Вдоль этой кривой dФ/dt=dФ/dr dr/dt=−(gradФ)^2<0, т.е. функция гарантированно убывает. Недостатком такого метода является необходимость дополнительного интегрирования системы дифференциальных уравнений, что сильно отягощает алгоритм. В более упрощенном варианте шаг может увеличиваться на каждой итерации на некоторую заданную величину до тех пор, пока не будет нарушено условие   После этого пересчитывается градиент и направление спуска изменяется, причем шаг опять начинает увеличиваться от некоторой начального значения.

Метод Ньютона

Введем обозначения: пусть f(x) функция n-переменных: x1,x2,...,xn, то есть, в этой записи x - это следующий вектор: x={x1,x2,...,xn}^T. Пусть, далее, x^(k+1) - вектор (k+1)-го приближения или (k+1)-ая итерация. Разложим функцию f(x) в ряд Тейлора вблизи точки x^(k+1). Тогда, ограничиваясь первыми двумя членами разложения, получим: где Необходимое условие экстремума функции многих переменных f'(x^(k+1))=0 приводит к следующему условию (дифференцируем правую часть разложения): f'(x^(k+1))+f''(x^(k+1))· (x−x^(k))=0 или Полученное выражение представляет собой систему линейных алгебраических уравнений относительно неизвестного вектора x, которую можно решить любым известным численным методом (Гаусса, по формулам Крамера и др.). Отсюда следует следующая итерационная формула для (k+1) приближения: x^(k+1)=x^(k)+αkp^(k), где векторp^(k)=x−x^(k+1) задает ньютоновское направление, а αkзадает шаг. При αk=1 рассматриваемый метод в точности совпадает с методом Ньютона решения систем нелинейных уравнений, примененным к решению системы f'(x)=0. Отсюда - название метода. Метод Ньютона обладает квадратичной сходимостью, что позволяет использовать простой практический критерий окончания счета: |x^(k+1)−x^(k)|<ε

Другие методы

12.4.7.1. Метод оврагов В случае, овражного рельефа функции иногда применяют специальный метод спуска по дну оврага- овражный метод. В соответствии с этим методом, выбирают два расположенных рядом начальных приближения: ρ0 и ρ1. Их этих точек делают спуск (например, по координатам), не требуя высокой точности сходимости. В итоге попадают в точки r0 и r1   После этого проводят через две точки r0 и r1 прямую линию − приблизительную линию дна оврага ρ2=r1±(r2− r1)h, где h>0 − овражный шаг. Направление движения в сторону убывания функции выбирается за счет выбора знака в этом выражении: знак "+" выбирается при Ф(r1)<Ф(r0), в противном случае выбирается знак минус. Поскольку точка ρ2 не лежит на дне оврага (дно не является прямой линией), она лежит на склоне. Из нее снова опускаемся на дно, получая в итоге точку r2, после чего процесс "путешествия" по дну оврага продолжается до тех пор, пока значение функции Ф убывает. В случае, когда станет Ф(rn+1)>Ф(rn), процесс следует прекратить и rn+1 не использовать. Метод оврагов рассчитан на то, чтобы пройти по дну оврага и выйти в котловину вблизи минимума. В этой котловине значение минимума лучше уточнять другими методами.

12.4.7.2. Метод слепого поиска Методы спуска плохо работают на неупорядоченном рельефе. Если локальных экстремумов много, то спуск из одного начального приближения может сойтись только к одному локальному минимуму, не обязательно абсолютному. В этих случаях иногда применяют метод слепого поиска. В соответствии с методом слепого (случайного) поиска предполагают, что все локальные минимумы лежат в некоторой ограниченной области; линейным преобразованием координат помещают ее внутрь единичного n-мерного куба. Выбирают в этом кубе N=(5÷20)n случайных точек с использованием генератора случайных чисел, и из каждой их них осуществляют спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью. Затем среди всех выявленных локальных минимумов выбираются те, которые представляют инетрес, и в них производится окончательный счет с требуемой точностью.

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

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