Навигация
2.3 Наискорейший спуск
Спускаться можно не только параллельно осям координат. Вдоль любой прямой 
функция зависит только от одной переменной, 
, и минимум на этой прямой можно найти.
Наиболее известным является метод наискорейшего спуска, когда выбирается 
, т. е. направление, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки. Спуск по этому направлению до минимума определяет новое приближение 
. В этой точке снова определяется градиент и делается следующий спуск.
Однако этот метод значительно сложнее спуска по координатам, ибо требуется вычислять производные и градиент и переходить к другим переменным. К тому же, по сходимости наискорейший спуск не лучше спуска по координатам. При попадании траектории в истинный овраг спуск прекращается, а в разрешимом овраге сильно замедляется.
Если функция является положительно определенной квадратичной функцией
, (16)
то формулы наискорейшего спуска приобретают несложный вид. Вдоль прямой 
функция (16) квадратично зависит от параметра 
:
. (17)
Из уравнения 
легко находим ее минимум
, (18)
дающий нам следующую точку спуска:
(19)
направление наискорейшего спуска определяется градиентом квадратичной функции (16):
. (20)
Подставляя это значение в формулы (18) – (19), получим окончательные выражения для вычисления последовательных спусков.
Если воспользоваться разложением всех движений по базису, состоящему из собственных векторов матрицы 
, то можно доказать, что для квадратичной функции метод наискорейшего спуска линейно сходится, причем
, где 
; (21)
здесь 
– собственные значения положительно определенной матрицы (они вещественны и положительны). Если 
, что соответствует сильно вытянутым эллипсам – линиям уровня, то 
и сходимость может быть очень медленной.
Есть такие начальные приближения (рис. 4), когда точно реализуется наихудшая возможная оценка, т. е. в (21) имеет место равенство.
Причины нетрудно понять. Во-первых, в данной точке любую прямую, в том числе невыгодную для спуска, можно сделать направлением градиента, если специально подобрать изменение масштабов по осям. Во-вторых, каждый спуск кончается в точке, где его направление касается линии (поверхности) уровня. Градиент перпендикулярен поверхности уровня. Следовательно, в методе наискорейшего спуска каждый спуск перпендикулярен предыдущему. В двумерном случае это означает, что мы совершаем спуск по координатам, повернутым так, что одна ось параллельна градиенту начальной точки.
Для улучшения метода наискорейшего спуска предлагают «кухонные» поправки к алгоритму – например, совершают по каждому направлению спуск не точно до минимума. Наиболее любопытным представляется такое видоизменение алгоритма. Будем делать по направлению, противоположному градиенту, только бесконечно малый шаг и после него вновь уточнять направление спуска. Это приводит к движению по кривой 
, являющейся решением системы обыкновенных дифференциальных уравнений:
. (22)
Вдоль этой кривой 
, т. е. функция убывает, и мы движемся к минимуму при 
. Уравнение (22) моделирует безынерционное движение материальной точки вниз по линии градиента. Можно построить и другие уравнения – например, дифференциальное уравнение второго порядка, моделирующее движение точки при наличии вязкого трения.
Однако от идеи метода еще далеко до надежного алгоритма. Фактически систему дифференциальных уравнений (22) надо численно интегрировать. Если интегрировать с большим шагом, то численное решение будет заметно отклоняться от линии градиента. А при интегрировании малым шагом сильно возрастает объем расчетов. Кроме того, если рельеф имеет извилистые овраги, то трудно ожидать хорошей сходимости этого метода.
Алгоритмы наискорейшего спуска и всех его видоизменений сейчас недостаточно отработаны. Поэтому метод наискорейшего спуска для сложных нелинейных задач с большим числом переменных (
) редко применяется, но в частных случаях он может оказаться полезным.
Похожие работы
... , Флетчера-Ривса). Методы второго порядка, использующие, кроме того, и информацию о вторых производных функции f (x) (метод Ньютона и его модификации). Метод конфигураций (Хука - Дживса) Следует выделить два этапа метода конфигураций: 1) исследование с циклическим изменением переменных и 2) ускорение поиска по образцам. Исследующий поиск начинается в точке х0, называемой старым базисом. ...
... (x, y) выполняется неравенство: . При этом, т. е. приращение функции > 0. Определение 3: Точки локальных минимума и максимума называются точками экстремума. Условные Экстремумы При отыскании экстремумов функции многих переменных часто возникают задачи, связанные с так называемым условным экстремумом. Это понятие можно разъяснить на примере функции двух переменных. Пусть заданы функция ...
... p и q, получим некоторые наборы (в зависимости от p и q) на которых функция достигает максимума. 3. Решение задачи с использованием метода покоординатного спуска 3.1 Описание метода покоординатного спуска Изложим этот метод на примере функции трех переменных . Выберем нулевое приближение . Фиксируем значения двух координат . Тогда функция будет зависеть только от одной переменной ; ...
... , которые содержат неизвестную функцию, её производные и аргументы. Обыкновенным называется дифференциальное уравнение, в котором неизвестная функция является функцией одной переменной. Если неизвестная функция является функцией многих переменных, то соответствующее уравнение называется дифференциальным уравнением в частных производных. Порядком дифференциального уравнения называется наивысший ...
0 комментариев