Когда используют градиентный метод. Градиентные методы оптимизации

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

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

Рис. 4.11.

Рис. 4.12.

(двумерный случай)

Вначале выбирают начальную точку Если в одномерном случае (см. подпараграф 4.2.6) из нее можно было

сдвинуться только влево или вправо (см. рис. 4.9), то в многомерном случае число возможных направлений перемещения бесконечно велико. На рис. 4.11, иллюстрирующем случай двух переменных, стрелками, выходящими из начальной точки А, показаны различные возможные направления. При этом движение по некоторым из них дает увеличение значения целевой функции по отношению к точке А (например, направления 1-3), а по другим направлениям приводит к его уменьшению (направления 5-8). Учитывая, что положение точки оптимума неизвестно, считается наилучшим то направление, в котором целевая функция возрастает быстрее всего. Это направление называется градиентом функции. Отметим, что в каждой точке координатной плоскости направление градиента перпендикулярно касательной к линии уровня, проведенной через ту же точку.

В математическом анализе доказано, что составляющие вектора градиента функции у =/(*, х 2 , ..., х п) являются ее частными производными по аргументам, т.е.

&ад/(х 1 ,х 2 ,.= {ду/дху,ду/дх 2 , ...,ду/дх п }. (4.20)

Таким образом, при поиске максимума по методу градиента на первой итерации вычисляют составляющие градиента по формулам (4.20) для начальной точки и делают рабочий шаг в найденном направлении, т.е. осуществляется переход в новую точку -0)

У" с координатами:

1§гас1/(х (0)),

или в векторной форме

где X - постоянный или переменный параметр, определяющий длину рабочего шага, ?і>0. На второй итерации снова вычисляют

вектор градиента уже для новой точки.У, после чего по анало-

гичной формуле переходят в точку х^ > и т.д. (рис. 4.12). Для произвольной к- й итерации имеем

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

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

длина рабочего шага - расстояние между соседними точками х^

их 1 " - окажется пропорциональном модулю вектора градиента. Можно, наоборот, на каждой итерации выбирать X таким, чтобы длина рабочего шага оставалась постоянной.

Пример. Требуется найти максимум функции

у = 110-2(лг, -4) 2 -3(* 2 -5) 2 .

Разумеется, воспользовавшись необходимым условием экстремума, сразу получим искомое решение: х ] - 4; х 2 = 5. Однако на этом простом примере удобно продемонстрировать алгоритм градиентного метода. Вычислим градиент целевой функции:

grad у = {ду/дх-,ду/дх 2 } = {4(4 - *,); 6(5 - х 2)} и выбираем начальную точку

Л*» = {х}°> = 0; 4°> = О}.

Значение целевой функции для этой точки, как легко подсчитать, равно у[х^ j = 3. Положим, X = const = 0,1. Величина градиента в точке

Зс (0) равна grad y|x^j = {16; 30}. Тогда на первой итерации получим согласно формулам (4.21) координаты точки

х 1) = 0 + 0,1 16 = 1,6; х^ = 0 + 0,1 30 = 3.

у(х (1)) = 110 - 2(1,6 - 4) 2 - 3(3 - 5) 2 = 86,48.

Как видно, оно существенно больше предыдущего значения. На второй итерации имеем по формулам (4.22):

• 1,6 + 0,1 4(4 - 1,6) = 2,56;

1. Какие высказывания неверны? Метод Данцига

Ответ: можно отнести к группе градиентных

2. Какие из нижеперечисленных высказываний истинны:

Ответ: Задача ЛП с несовместной системой ограничений называется открытой

3. Какие из перечисленных методов не являются активными

Ответ: золотого сечения

4. Какие из приведенных высказываний верны:

Ответ: задача транспортного типа – частный случай задачи линейного программирования

5. Какие из приведенных утверждений истинны: Метод наименьших квадратов

Ответ: сводится в итоге к решению системы n линейных уравнений при аппроксимации результатов многочленами n-го порядка

6. Какие из указанных методов не являются градиентными

Ответ: симплексный метод (метод Нелдера-Мида)

7. Какие из указанных методов позволяют найти глобальный экстремум полимодальной функции

Ответ: сканирования

8. Какие методы среди перечисленных являются методами покоординатного поиска

Ответ: касательный

9. Отметьте верные утверждения

Ответ: метод простого перебора нельзя использовать при отыскании экстремума согласно процедуре Гаусса-Зайделя

10. Укажите истинное высказывание

Ответ: планом называется любое допустимое решение задачи

11. Укажите неправильное высказывание

Ответ: плоскость, содержащая хотя бы одну угловую точку выпуклого многогранника называется опорной плоскостью этого многогранника

12. Укажите номера правильных утверждений

Ответ: задачи транспортного типа нельзя решать методом Данцига, так как они относятся к задачам дискретного программирования(1). Первоначальный план в симплексном методе получаем приравниваем нулю всех базисных переменных(3)

13. Укажите правильное утверждение?

Ответ: базисное решение задачи ЛП вырожденное, если хотя бы одна из свободных переменных равна нулю

14. Что из нижеследующего неверно:

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

15. Что истинно из высказываний ниже?

Ответ: задача о коммивояжере относится к области дискретного программирования

16. Что истинно из следующего:

Ответ: одна из основных проблем оптимизации – «проблема размерности»

17. Что неверно в приведенных высказываниях?

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

18. Что из приведенных высказываний неверно?

Ответ: задачу ЛП можно решить процедурой упорядоченного перехода от одного плана к другому.

19. Что из предлагаемого истинно

Ответ: внутри области допустимых решений задачи ЛП не может быть экстремум

20. Что ложно из нижеприведенного?

Ответ: Для отыскания экстремума линейной целевой функции симплексным методом необходимо выполнить n-m итераций, n- количество неизвестных задачи, m- число ограничений общего вида

Данное учебное пособие подготовлено на основе курса лекций по дисциплине «Нейроинформатика», читавшегося с 1994 года на факультете Информатики и вычислительной техники Красноярского государственного технического университета.

по данному курсу,

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

Включающий в себя два уровня - уровень запросов компонентов универсального нейрокомпьютера и уровень языков описания отдельных компонентов нейрокомпьютера.

учебный план

задания на лабораторные работы

#AutBody_14DocRoot

#AutBody_15DocRoot

Нейроучебник

#AutBody_16DocRoot

проект стандарта нейрокомпьютера

Данное пособие является электронным и включает в себя программы, необходимые для выполнения лабораторных работ.

Книга:

Разделы на этой странице:

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

1. Вычислить_оценку О2
2. О1=О2
3. Вычислить_градиент
4. Оптимизация шага Пустой_указатель Шаг
5. Вычислить_оценку О2
6. Если О1-О2<Точность то переход к шагу 2

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

Наиболее известным среди градиентных методов является метод наискорейшего спуска. Идея этого метода проста: поскольку вектор градиента указывает направление наискорейшего возрастания функции, то минимум следует искать в обратном направлении. Последовательность действий приведена на рис. 5.

Этот метод работает, как правило, на порядок быстрее методов случайного поиска. Он имеет два параметра - Точность, показывающий, что если изменение оценки за шаг метода меньше чем Точность, то обучение останавливается; Шаг - начальный шаг для оптимизации шага. Заметим, что шаг постоянно изменяется в ходе оптимизации шага.

Рис. 6. Траектории спуска при различных конфигурациях окрестности минимума и разных методах оптимизации.

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

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

1. Создать_вектор В1
2. Создать_вектор В2
3. Шаг=1
4. Вычислить_оценку О2
5. Сохранить_вектор В1
6. О1=О2
7. N=0
8. Вычислить_градиент
9. Оптимизация_шага Пустой_указатель Шаг
10. N=N+1
11. Если N 12. Сохранить_вектор В2
13. В2=В2-В1
14. ШагParTan=1
15. Оптимизация шага В2 ШагParTan
16. Вычислить_оценку О2
17. Если О1-О2<Точность то переход к шагу 5

Рис. 7. Метод kParTan

Одним из простейших антиовражных методов является метод kParTan. Идея метода состоит в том, чтобы запомнить начальную точку, затем выполнить k шагов оптимизации по методу наискорейшего спуска, затем сделать шаг оптимизации по направлению из начальной точки в конечную. Описание метода приведено на рис 7. На рис 6в приведен один шаг оптимизации по методу 2ParTan. Видно, что после шага вдоль направления из первой точки в третью траектория спуска привела в минимум. К сожалению, это верно только для двумерного случая. В многомерном случае направление kParTan не ведет прямо в точку минимума, но спуск в этом направлении, как правило, приводит в окрестность минимума меньшего радиуса, чем при еще одном шаге метода наискорейшего спуска (см. рис. 6б). Кроме того, следует отметить, что для выполнения третьего шага не потребовалось вычислять градиент, что экономит время при численной оптимизации.

Лекция 6.

Градиентные методы решения задач нелинейного программирования.

Вопросы: 1. Общая характеристика методов.

2. Метод градиента.

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

4. Метод Франка-Фулфа.

5. Метод штрафных функций.

1. Общая характеристика методов.

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

Градиентные методы можно разделить на два класса (группы). К первой группе относятся методы, в которых все исследуемые точки принадлежат допустимой области. К таким методам относятся: метод градиента, наискорейшего спуска, Франка-Вулфа и др. Ко второй группе относятся методы, в которых исследуемые точки могут и не принадлежать допустимой области. Общим из таких методов является метод штрафных функций. Все методы штрафных функций отличаются друг от друга способом определения «штрафа».

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

При определении решения градиентными методами итерационный процесс продолжается до тех пор, пока:

Либо grad F(x*) = 0, (точное решение);

где
- две последовательные точки,
- малое число, характеризующее точность решения.

2. Метод градиента.

Представим человека, стоящего на склоне оврага, которому необходимо спуститься вниз (на дно). Наиболее естественным, кажется, направление в сторону наибольшей крутизны спуска, т.е. направление (-grad F(x)). Получаемая при этом стратегия, называемая градиентным методом , представляет собой последовательность шагов, каждый из которых содержит две операции:

а) определение направления наибольшей крутизны спуска (подъема);

б) перемещение в выбранном направлении на некоторый шаг.

Правильный выбор шага имеет существенное значение. Чем шаг меньше, тем точнее результат, но больше вычислений. Различные модификации градиентного метода и состоят в использовании различных способов определения шага. Если на каком-либо шаге значение F(x) не уменьшилось, это означает, что точку минимума «проскочили», в этом случае необходимо вернуться к предыдущей точке и уменьшить шаг, например, вдвое.

Схема решения.

принадлежащей допустимой области

3. Выбор шага h.

x (k+1) = x (k)

«-» - если min.

5. Определение F(x (k +1)) и:

Если
, решение найдено;

Замечание. Если grad F(x (k)) = 0, то решение будет точным.

Пример. F(x) = -6x 1 + 2x 1 2 – 2x 1 x 2 + 2x 2 2
min,

x 1 +x 2 2,x 1 0, x 2 0,= 0,1.

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

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

Схема решения.

1. Определение х 0 = (х 1 ,x 2 ,…,x n),

принадлежащей допустимой области,

и F(x 0), k = 0.

2. Определение grad F(x 0) или –gradF(x 0).

3. Выбор шага h.

4. Определение следующей точки по формуле

x (k+1) = x (k) h grad F(x (k)), «+» - если max,

«-» - если min.

5. Определение F(x (k +1)) и:

Если
, решение найдено;

Если нет:

а) при поиске min: - если F(x (k +1))

Если F(x (k +1)) >F(x (k)) – переход к п. 2;

б) при поиске max: - еслиF(x (k +1)) >F(x (k)) – переход к п. 4;

Если F(x (k +1))

Замечания: 1. Если grad F(x (k)) = 0, то решение будет точным.

2. Преимуществом метода наискорейшего спуска является его простота и

сокращение расчетов, так как grad F(x) вычисляется не во всех точках, что

важно для задач большой размерности.

3. Недостатком является то, что шаги должны быть малыми, чтобы не

пропустить точку оптимума.

Пример. F(x) = 3x 1 – 0,2x 1 2 + x 2 - 0,2x 2 2
max,

x 1 + x 2 7, x 1 0,

x 1 + 2x 2 10, x 2 0.

4. Метод Франка-Вулфа.

Метод используется для оптимизации нелинейной целевой функции при линейных ограничениях. В окрестности исследуемой точки нелинейная целевая функция заменяется линейной функцией и задача сводится к последовательному решению задач линейного программирования.

Схема решения.

1. Определение х 0 = (х 1 ,x 2 ,…,x n), принадлежащей допустимой области, и F(x 0), k = 0.

2. Определение grad F(x (k)).

3. Строят функцию

(min – «-»;max– «+»).

4. Определение max(min)f(x) при исходных ограничениях. Пусть это будет точка z (k) .

5. Определение шага вычислений x (k +1) =x (k) + (k) (z (k) –x (k)), где (k) – шаг, коэффициент, 0 1. (k) выбирается так, чтобы значение функции F(x) было max (min) в точке х (k +1) . Для этого решают уравнение
и выбирают наименьший (наибольший) из корней, но 0 1.

6. Определение F(x (k +1)) и проверяют необходимость дальнейших вычислений:

Если
или grad F(x (k +1)) = 0, то решение найдено;

Если нет, то переход к п. 2.

Пример. F(x) = 4x 1 + 10x 2 –x 1 2 –x 2 2
max,

x 1 +x 2 4, x 1 0,

x 2 2, x 2 0.

5. Метод штрафных функций.

Пусть необходимо найти F(x 1 ,x 2 ,…,x n)
max(min),

g i (x 1 , x 2 ,…,x n) b i , i =
, x j 0, j =.

Функции F и g i – выпуклые или вогнутые.

Идея метода штрафных функций заключается в поиске оптимального значения новой целевой функции Q(x) = F(x) + H(x), которая является суммой исходной целевой функции и некоторой функции H(x), определяемой системой ограничений и называемой штрафной функцией. Штрафные функции строят таким образом, чтобы обеспечить либо быстрое возвращение в допустимую область, либо невозможность выходы из нее. Метод штрафных функций сводит задачу на условный экстремум к решению последовательности задач на безусловный экстремум, что проще. Существует множество способов построения штрафной функции. Наиболее часто она имеет вид:

H(x) =
,

где

- некоторые положительные Const.

Примечание :

Чем меньше , тем быстрее находится решение, однако, точность снижается;

Начинают решение с малых и увеличивают их на последующих шагах.

Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение.

Схема решения.

1. Определение начальную точку х 0 = (х 1 ,x 2 ,…,x n), F(x 0) и k = 0.

2. Выбирают шаг вычислений h.

3. Определяют частные производные и.

4. Определяют координаты следующей точки по формуле:

x j (k +1)
.

5. Если x (k +1) Допустимой области, проверяют:

а) если
- решение найдено, если нет – переход к п. 2.

б) если grad F(x (k +1)) = 0, то найдено точное решение.

Если x (k +1) Допустимой области, задают новое значениеи переходят к п. 4.

Пример. F(x) = – x 1 2 – x 2 2
max,

(x 1 -5) 2 +(x 2 -5) 2 8, x 1 0, x 2 0.

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

Существуют различные способы выбора шага каждый из которых задает определенный вариант градиентного метода.

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

Рассмотрим функцию одной скалярной переменной и выберем в качестве то значение, для которого выполняется равенство

Этот метод, предложенный в 1845 г. О. Коши, принято теперь называть методом наискорейшего спуска.

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

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

Применим метод наискорейшего спуска для минимизации квадратичной функции

с симметричной положительно определенной матрицей А.

Согласно формуле (10.8), в этом случае Поэтому формула (10.22) выглядит здесь так:

Заметим, что

Эта функция является квадратичной функцией параметра а и достигает минимума при таком значении для которого

Таким образом, применительно к минимизации квадратичной

функции (10.24) метод наискорейшего спуска эквивалентен расчету по формуле (10.25), где

Замечание 1. Поскольку точка минимума функции (10.24) совпадает с решением системы метод наискорейшего спуска (10.25), (10.26) может применяться и как итерационный метод решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами.

Замечание 2. Отметим, что где отношение Рэлея (см. § 8.1).

Пример 10.1. Применим метод наискорейшего спуска для минимизации квадратичной функции

Заметим, что Поэтому точное значение точки минимума нам заранее известно. Запишем данную функцию в виде (10.24), где матрица и вектор Как нетрудно видеть,

Возьмем начальное приближение и будем вести вычисления по формулам (10.25), (10.26).

I итерация.

II итерация.

Можно показать, что для всех на итерации будут получены значения

Заметим, что при Таким образом,

последовательность полученная методом наискорейшего спуска, сходится со скоростью геометрической прогрессии, знаменатель которой

На рис. 10.5 изображена именно та траектория спуска, которая была получена в данном примере.

Для случая минимизации квадратичной функции справедлив следующий общий результат .

Теорема 10.1. Пусть А - симметричная положительно определенная матрица и минимизируется квадратичная функция (10.24). Тогда при любом выборе начальною приближения метод наискорейшею спуска (10.25), (10.26) сходится и верна следующая оценка погрешности:

Здесь и Ладо - минимальное и максимальное собственные значения матрицы А.

Отметим, что этот метод сходится со скоростью геометрической прогрессии, знаменатель которой причем если их близки, то мало и метод сходится достаточно быстро. Например, в примере 10.1 имеем и поэтому Если же Ащах, то и 1 и следует ожидать медленной сходимости метода наискорейшего спуска.

Пример 10.2. Применение метода наискорейшего спуска для минимизации квадратичной функции при начальном приближении дает последовательность приближений где Траектория спуска изображена на рис. 10.6.

Последовательность сходится здесь со скоростью геометрической прогрессии, знаменатель которой равен т. е. существенно медленнее,

чем в предыдущем примерю. Так как здесь и полученный результат вполне согласуется с оценкой (10.27).

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

Замечание 2. Для квадратичной целевой функции (10.24) решение задачи одномерной минимизации (10.23) удается найти в виде простой явной формулы (10.26). Однако для большинства других нелинейных функций этого сделать нельзя и для вычисления методом наискорейшего спуска приходится применять численные методы одномерной минимизации типа тех, которые были рассмотрены в предыдущей главе.

2. Проблема "оврагов".

Из проведенного выше обсуждения следует, что градиентный метод сходится достаточно быстро, если для минимизируемой функции поверхности уровня близки к сферам (при линии уровня близки к окружностям). Для таких функций и 1. Теорема 10.1, замечание 1, а также результат примера 10.2 указывают на то, что скорость сходимости резко падает при увеличении величины Действительно, известно, что градиентный метод сходится очень медленно, если поверхности уровня минимизируемой функции сильно вытянуты в некоторых направлениях. В двумерном случае рельеф соответствующей поверхности напоминает рельеф местности с оврагом (рис. 10.7). Поэтому такие функции принято называть овражными. Вдоль направлений, характеризующих "дно оврага", овражная функция меняется незначительно, а в других направлениях, характеризующих "склон оврага", происходит резкое изменение функции.

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

Для ускорения сходимости градиентного метода при минимизации овражных функций разработан ряд специальных "овражных" методов. Дадим представление об одном из простейших приемов. Из двух близких начальных точек совершают градиентный спуск на "дно оврага". Через найденные точки проводят прямую, вдоль которой совершают большой "овражный" шаг (рис. 10.8). Из найденной таким образом точки снова делают один шаг градиентного спуска в точку Затем совершают второй "овражный" шаг вдоль прямой, проходящей через точки . В результате движение вдоль "дна оврага" к точке минимума существенно ускоряется.

Более подробную информацию о проблеме "оврагов" и "овражных" методах можно найти, например, в , .

3. Другие подходы к определению шага спуска.

Как нетрудно понять, на каждой итерации было бы желательно выбирать направление спуска близкое к тому направлению, перемещение вдоль которого приводит из точки в точку х. К сожалению, антиградиент (является, как правило, неудачным направлением спуска. Особенно ярко это проявляется для овражных функций. Поэтому возникает сомнение в целесообразности тщательного поиска решения задачи одномерной минимизации (10.23) и появляется желание сделать в направлении лишь такой шаг, который бы обеспечил "существенное убывание" функции Более того, на практике иногда довольствуются определением значения которое просто обеспечивает уменьшение значения целевой функции.

Главная » Для начинающих » Когда используют градиентный метод. Градиентные методы оптимизации