Обзор градиентных методов в задачах математической оптимизации. Градиентные методы оптимизации
При оптимизации методом градиента оптимум исследуемого объекта ищут в направлении наиболее быстрого возрастания (убывания) выходной переменной, т.е. в направлении градиента. Но прежде чем сделать шаг в направлении градиента, необходимо его рассчитать. Градиент можно рассчитать либо по имеющейся модели
моделирование динамический градиентный полиномиальный
где - частная производная по i-му фактору;
i, j, k - единичные векторы в направлении координатных осей факторного пространства, либо по результатам n пробных движений в направлении координатных осей.
Если математическая модель статистического процесса имеет вид линейного полинома, коэффициенты регрессии b i которого являются частными производными разложения функции y = f(X) в ряд Тейлора по степеням x i , то оптимум ищут в направлении градиента с некоторым шагом h i:
пкфв н(Ч)= и 1 р 1 +и 2 р 2 +…+и т р т
Направление корректируют после каждого шага.
Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Рассмотрим одну из модификаций метода градиента - метод крутого восхождения.
Метод крутого восхождения, или иначе метод Бокса-Уилсона, объединяет в себе достоинства трех методов - метода Гаусса-Зейделя, метода градиентов и метода полного (или дробного) факторного экспериментов, как средства получения линейной математической модели. Задача метода крутого восхождения заключается в том, чтобы шаговое движение осуществлять в направлении наискорейшего возрастания (или убывания) выходной переменной, то есть по grad y(X). В отличии от метода градиентов, направление корректируется не после каждого следующего шага, а при достижении в некоторой точке на данном направлении частного экстремума целевой функции, как это делается в методе Гаусса-Зейделя. В точке частного экстремума ставится новый факторный эксперимент, определяется математическая модель и вновь осуществляется крутое восхождение. В процессе движения к оптимуму указанным методом регулярно проводиться статистический анализ промежуточных результатов поиска. Поиск прекращается, когда квадратичные эффекты в уравнении регрессии становятся значимыми. Это означает, что достигнута область оптимума.
Опишем принцип использования градиентных методов на примере функции двух переменных
при наличии двух дополнительных условий:
Этот принцип (без изменения) можно применить при любом числе переменных, а также дополнительных условий. Рассмотрим плоскость x 1 , x 2 (Рис. 1). Согласно формуле (8) каждой точке соответствует некоторое значение F. На Рис.1 линии F = const, принадлежащие этой плоскости, представлены замкнутыми кривыми, окружающими точку M * , в которой F минимально. Пусть в начальный момент значения x 1 и x 2 соответствуют точке M 0 . Цикл расчета начинается с серии пробных шагов. Сначала величине x 1 дается небольшое приращение; в это время значение x 2 неизменно. Затем определяется полученное при этом приращение величины F, которое можно считать пропорциональным значению частной производной
(если величина всегда одна и та же).
Определение частных производных (10) и (11) означает, что найден вектор с координатами и, который называется градиентом величины F и обозначается так:
Известно, что направление этого вектора совпадает с направлением наиболее крутого возрастания величины F. Противоположное ему направление - это «наискорейший спуск», другими словами, наиболее крутое убывание величины F.
После нахождения составляющих градиента пробные движения прекращаются и осуществляются рабочие шаги в направлении, противоположном направлению градиента, причем величина шага тем больше, чем больше абсолютная величина вектора grad F. Эти условия осуществляются, если величины рабочих шагов и пропорциональны полученным ранее значениям частных производных:
где б - положительная константа.
После каждого рабочего шага оценивается приращение величины F. Если оно оказывается отрицательным, то движение происходит в правильном направлении и нужно двигаться в том же направлении M 0 M 1 дальше. Если же в точке M 1 результат измерения показывает, что, то рабочие движения прекращаются и начинается новая серия пробных движений. При этом определяется градиент gradF в новой точке M 1 , затем рабочее движение продолжается по новому найденному направлению наискорейшего спуска, т. е. по линии M 1 M 2 , и т.д. Этот метод называется методом наискорейшего спуска/крутого восхождения.
Когда система находится вблизи минимума, показателем чего является малое значение величины
происходит переключение на более «осторожный» метод поиска, так называемый метод градиента. От метода наискорейшего спуска он отличается тем, что после определения градиента gradF делается лишь один рабочий шаг, а затем в новой точке опять начинается серия пробных движений. Такой метод поиска обеспечивает более точное установление минимума по сравнению с методом наискорейшего спуска, между тем как последний позволяет быстрее приблизиться к минимуму. Если в процессе поиска точка М доходит до границы допустимой области и хотя бы одна из величин М 1 , М 2 меняет знак, метод меняется и точка М начинает двигаться вдоль границы области.
Эффективность метода крутого восхождения зависит от выбора масштаба переменных и вида поверхности отклика. Поверхность со сферическими контурами обеспечивает быстрое стягивание к оптимуму.
К недостаткам метода крутого восхождения следует отнести:
1. Ограниченность экстраполяции. Двигаясь вдоль градиента, мы основываемся на экстраполяции частных производных целевой функции по соответствующим переменным. Однако форма поверхности отклика может изменяться и необходимо изменять направление поиска. Другими словами, движение на плоскости не может быть продолжительным.
2. Трудность поиска глобального оптимума. Метод применим для отыскания только локальных оптимумов.
Метод релаксации
Алгоритм метода заключается в отыскании осевого направления, вдоль которого целевая функция уменьшается наиболее сильно (при поиске минимума). Рассмотрим задачу безусловной оптимизации
Для определения осевого направления в начальной точке поиска из области определяются производные , , по всем независимым переменным. Осевому направлению соответствует наибольшая по модулю производная .
Пусть – осевое направление, т.е. 
.
Если знак производной отрицательный, функция убывает в направлении оси, если положительный – в обратном направлении:
В точке вычисляют . По направлению убывания функции производится один шаг, определяется и в случае улучшения критерия шаги продолжаются до тех пор, пока не будет найдено минимальное значение по выбранному направлению. В этой точке вновь определяются производные по всем переменным, за исключением тех, по которой осуществляется спуск. Снова находится осевое направление наиболее быстрого убывания , по которому производятся дальнейшие шаги и т.д.
Эту процедуру повторяют до тех пор, пока не достигается оптимальная точка, при движении из которой по любому осевому направлению дальнейшего убывания не происходит. На практике критерием окончания поиска служит условие
которое при превращается в точное условие равенства нулю производных в точке экстремума. Естественно условие (3.7) может быть использовано только в том случае, если оптимум лежит внутри допустимой области изменения независимых переменных . Если же оптимум попадает на границу области , критерий типа (3.7) непригоден и вместо него следует применять положительности всех производных по допустимым осевым направлениям.
Алгоритм спуска для выбранного осевого направления может быть записан так
(3.8)
где -значение варьируемой переменной на каждом шаге спуска;
Величина k+1 шага, которая может изменяться в зависимости от номера шага:
– функция знака z;
Вектор точки, в которой последний раз производилось вычисление производных ;
Знак “+” в алгоритме (3.8) принимается при поиске max I, а знак “-” – при поиске min I.Чем меньше шаг h., тем больше количество вычислений на пути движения к оптимуму. Но при слишком большой величине h вблизи оптимума может возникнуть зацикливание процесса поиска. Вблизи оптимума необходимо, чтобы выполнялось условие h Простейший алгоритм изменения шага h состоит в следующем. В начале спуска задается шаг , равный например, 10% от диапазона d; изменения с этим шагом производится спуск по выбранному направлению до тез пор, пока выполняется условие для двух последующих вычислений При нарушении условия на каком-либо шаге направление спуска на оси изменяется на обратное и спуск продолжается из последней точки с уменьшенной вдвое величиной шага. Формальная запись этого алгоритма следующая: В результате использования такой стратегии ша спуска будет уменьшатся в районе оптимума по данному направлению и поиск по направлению можно прекратить, когда станет меньше E. Затем отыскивается новое осевое направление начальный шаг для дальнейшего спуска, обычно меньший пройденного вдоль предыдущего осевого направления. Характер движения в оптимуме в данном методе показан на рисунке 3.4. Рисунок 3.5 – Траектория движения к оптимуму в методе релаксации Улучшение алгоритма поиска по данному методу может быть достигнуто путем применения методов однопараметрической оптимизации. При этом может быть предложена схема решения задачи: Шаг 1. – осевое направление, Шаг 2. – новое осевое направление; Метод градиента
В этом методе используется градиент функции . Градиентом функции в точке Рисунок 3.6 – Градиент функции Направление градиента – это направление наиболее быстрого возрастания функции (наиболее крутого “склона” поверхности отклика). Противоположное ему направление (направление антиградиента) – это направление наибыстрейшего убывания (направление наискорейшего “спуска” величин ). Проекция градиента на плоскость переменных перпендикулярна касательной к линии уровня , т.е. градиент ортогонален к линиям постоянного уровня целевой функции (рис. 3.6). Рисунок 3.7 – Траектория движения к оптимуму в методе градиента В отличие от метода релаксации в методе градиента шаги совершаются в направлении наибыстрейшего уменьшения (увеличения) функции . Поиск оптимума производится в два этапа. На первом этапе находятся значения частных производных по всем переменным , которые определяют направление градиента в рассматриваемой точке. На втором этапе осуществляется шаг в направлении градиента при поиске максимума или в противоположном направлении – при поиске минимума. Если аналитическое выражение неизвестно, то направление градиента определяется поиском на объекте пробных движений. Пусть начальная точка. Дается приращение величина , при этом . Определяют приращение и производную Аналогично определяют производные по остальным переменным. После нахождения составляющих градиента пробные движения прекращаются и начинаются рабочие шаги по выбранному направлению. Причем величина шага тем больше, чем больше абсолютная величина вектора . При выполнении шага одновременно изменяются значения всех независимых переменных. Каждая из них получает приращение, пропорциональное соответствующей составляющей градиента или в векторной форме где – положительная константа; “+” – при поиске max I; “-” – при поиске min I. Алгоритм градиентного поиска при нормировании градиента (деление на модуль) применяется в виде Определяет величину шага по направлению градиента. Алгоритм (3.10) обладает тем достоинством, что при приближении к оптимуму длина шага автоматически уменьшается. А при алгоритме (3.12) стратегию изменения можно строить независимо от абсолютной величины коэффициента. В методе градиента каждый разделяется один рабочий шаг, после которого вновь вычисляются производные, определяется новое направление градиента и процесс поиска продолжается (рис. 3.5). Если размер шага выбран слишком малым, то движение к оптимуму будет слишком долгим из-за необходимости вычисления в очень многих точках. Если же шаг выбран слишком большим, в район оптимума может возникнуть зацикливание. Процесс поиска продолжается до тех пор, пока , , не станут близки к нулю или пока не будет достигнута граница области задания переменных. В алгоритме с автоматическим уточнением шага величину уточняют так, чтобы изменение направления градиента в соседних точках и
Критерии окончания поиска оптимума: где Поиск завершается при выполнении одного из условий (3.14) – (3.17). Недостатком градиентного поиска (так же и рассмотренных выше методов) является то, что при его использовании можно обнаружить только локальный экстремум функции . Для отыскания других локальных экстремумов необходимо производить поиск из других начальных точек. Задачи оптимизации с нелинейными или трудно вычислимыми соотношениями, определяющими критерий оптимизации и ограничения, являются предметом нелинейного программирования. Как правило, решения задач нелинейного программирования могут быть найдены лишь численными методами с применением вычислительной техники. Среди них наиболее часто пользуются градиентными методами (методы релаксации, градиента, наискорейшего спуска и восхождения), безградиентными методами детерминированного поиска (методы сканирования, симплексный и др.), методами случайного поиска. Все эти методы применяются при численном определении опти-мумов и достаточно широко освещены в специальной литературе. В общем случае значение критерия оптимизации R
может рассматриваться как функция R
(х ь хь
..., х п),
определенная в л-мерном пространстве. Поскольку не существует наглядного графического изображения я-мерного пространства, воспользуемся случаем двумерного пространства. Если R
(л ь х 2)
непрерывна в области D,
то вокруг оптимальной точки M°(xi°, х г °)
можно провести в данной плоскости замкнутую линию, вдоль которой значение R
= const. Таких линий, называемых линиями равных уровней, вокруг оптимальной точки можно провести множество (в зависимости от шага Среди методов, применяемых для решения задач нелинейного программирования, значительное место занимают методы поиска решений, основанные на анализе производной по направлению оптимизируемой функции. Если в каждой точке пространства скалярная функция нескольких переменных принимает вполне определенные значения, то в данном случае имеем дело со скалярным полем (поле температур, поле давлений, поле плотностей и т.д.). Подобным образом определяется векторное поле (поле сил, скоростей и т.д.). Изотермы, изобары, изохроны и т.д. - все это линии (поверхности) равных уровней, равных значений функции (температуры, давления, объема и т.д.). Поскольку от точки к точке пространства значение функции меняется, то становится необходимым определение скорости изменения функции в пространстве, то есть производной по направлению. Понятие градиента широко используется в инженерных расчетах при нахождении экстремумов нелинейных функций. Градиентные методы относятся к численным методам поискового типа. Они универсальны и особенно эффективны в случаях поиска экстремумов нелинейных функций с ограничениями, а также когда аналитическая функция неизвестна совсем. Сущность этих методов заключается в определении значений переменных, обеспечивающих экстремум функции цели, путем движения по градиенту (при поиске max)
или в противоположном направлении (min).
Различные градиентные методы отличаются один от другого способом определения движения к оптимуму. Суть заключается в том, что если линии равных уровней R{xu x i)
характеризуют графически зависимость R(x\jc?),
то поиск оптимальной точки можно вести по-разному. Например, изобразить сетку на плоскости х\, хг
с указанием значений R
в узлах сетки (рис. 2.13). Затем можно выбрать из узловых значений экстремальное. Путь этот не рациональный, связан с большим количеством вычислений, да и точность невелика, так как зависит от шага, а оптимум может находиться между узлами. Численные методы
Математические модели содержат соотношения, составленные на основе теоретического анализа изучаемых процессов или полученные в результате обработки экспериментов (таблиц данных, графиков). В любом случае мате матическая модель лишь приближенно описывает реальный процесс. Поэтом} вопрос точности, адекватности модели является важнейшим. Необходимости приближений возникает и при самом решении уравнений. До недавних пор модели, содержащие нелинейные дифференциальные уравнения или диффе ренциальные уравнения в частных производных, не могли быть решены ана литическими методами. Это же относится к многочисленным классам небе рущихся интегралов. Однако разработка методов численного анализа позво лила необозримо раздвинуть границы возможностей анализа математических моделей, особенно это стало реальным с применением ЭВМ. Численные методы используются для приближения функций, для реше ния дифференциальных уравнений и их систем, для интегрирования и диффе ренцирования, для вычисления числовых выражений. Функция может быть задана аналитически, таблицей, графиком. При вы полнении исследований распространенной задачей является приближение функции аналитическим выражением, удовлетворяющим поставленным уело виям. При этом решаются четыре задачи: Выбор узловых точек, проведение экспериментов при определенных значениях (уровнях) независимых переменных (при неправильном выборе шага изменения фактора либо «пропустим» характерную особенность изучаемого процесса, либо удлиним процедуру и повысим трудоемкость поиска закономерности); Выбор приближающих функций в виде многочленов, эмпирических формул в зависимости от содержания конкретной задачи (следует стремиться к максимальному упрощению приближающих функций); Выбор и использование критериев согласия, на основе которых находятся параметры приближающих функций; Выполнение требований заданной точности к выбору приближающей функции. В задачах приближения функций многочленами используются три класса Линейная комбинация степенных функций (ряд Тейлора, многочлены Лагранжа, Ньютона и др.); Комбинация функций соз пх, ш их
(ряды Фурье); Многочлен, образуемый функциями ехр
(-а, г). При нахождении приближающей функции используют различные критерии согласия с экспериментальными данными. Градиентный метод и его разновидности относятся к самым распространенным методам поиска экстремума функций нескольких переменных. Идея градиентного метода заключается в том, чтобы в процессе поиска экстремума (для определенности максимума) двигаться каждый раз в направлении наибольшего возрастания целевой функции. Градиентный метод предполагает вычисление первых производных целевой функции по ее аргументам. Он, как и предыдущие, относится к приближенным методам и позволяет, как правило, не достигнуть точки оптимума, а только приблизиться к ней за конечное число шагов. Рис. 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): Градиентные методы Градиентные методы безусловной оптимизации используют только первые производные целевой функции и являются методами линейной аппроксимации на каждом шаге, т.е. целевая функция на каждом шаге заменяется касательной гиперплоскостью к ее графику в текущей точке. На k-м этапе градиентных методов переход из точки Xk в точку Xk+1 описывается соотношением: где k - величина шага, k - вектор в направлении Xk+1-Xk. Методы наискорейшего спуска Впервые такой метод рассмотрел и применил еще О. Коши в XVIII в. Идея его проста: градиент целевой функции f(X) в любой точке есть вектор в направлении наибольшего возрастания значения функции. Следовательно, антиградиент будет направлен в сторону наибольшего убывания функции и является направлением наискорейшего спуска. Антиградиент (и градиент) ортогонален поверхности уровня f(X) в точке X. Если в (1.2) ввести направление то это будет направление наискорейшего спуска в точке Xk. Получаем формулу перехода из Xk в Xk+1: Антиградиент дает только направление спуска, но не величину шага. В общем случае один шаг не дает точку минимума, поэтому процедура спуска должна применяться несколько раз. В точке минимума все компоненты градиента равны нулю. Все градиентные методы используют изложенную идею и отличаются друг от друга техническими деталями: вычисление производных по аналитической формуле или конечно-разностной аппроксимации; величина шага может быть постоянной, меняться по каким-либо правилам или выбираться после применения методов одномерной оптимизации в направлении антиградиента и т.д. и т.п. Останавливаться подробно мы не будем, т.к. метод наискорейшего спуска не рекомендуется обычно в качестве серьезной оптимизационной процедуры. Одним из недостатков этого метода является то, что он сходится к любой стационарной точке, в том числе и седловой, которая не может быть решением. Но самое главное - очень медленная сходимость наискорейшего спуска в общем случае. Дело в том, что спуск является "наискорейшим" в локальном смысле. Если гиперпространство поиска сильно вытянуто ("овраг"), то антиградиент направлен почти ортогонально дну "оврага", т.е. наилучшему направлению достижения минимума. В этом смысле прямой перевод английского термина "steepest descent", т.е. спуск по наиболее крутому склону более соответствует положению дел, чем термин "наискорейший", принятый в русскоязычной специальной литературе. Одним из выходов в этой ситуации является использование информации даваемой вторыми частными производными. Другой выход - изменение масштабов переменных. линейный аппроксимация производная градиент Метод сопряженного градиента Флетчера-Ривса В методе сопряженного градиента строится последовательность направлений поиска, являющихся линейными комбинациями, текущего направления наискорейшего спуска, и, предыдущих направлений поиска, т.е. причем коэффициенты выбираются так, чтобы сделать направления поиска сопряженными. Доказано, что и это очень ценный результат, позволяющий строить быстрый и эффективный алгоритм оптимизации. Алгоритм Флетчера-Ривса 1. В X0 вычисляется. 2. На k-ом шаге с помощь одномерного поиска в направлении находится минимум f(X), который и определяет точку Xk+1. где - произвольная константа. Преимуществом алгоритма Флетчера-Ривса является то, что он не требует обращения матрицы и экономит память ЭВМ, так как ему не нужны матрицы, используемые в Ньютоновских методах, но в то же время почти столь же эффективен как квази-Ньютоновские алгоритмы. Т.к. направления поиска взаимно сопряжены, то квадратичная функция будет минимизирована не более, чем за n шагов. В общем случае используется рестарт, который позволяет получать результат. Алгоритм Флетчера-Ривса чувствителен к точности одномерного поиска, поэтому при его использовании необходимо устранять любые ошибки округления, которые могут возникнуть. Кроме того, алгоритм может отказать в ситуациях, где Гессиан становится плохо обусловленным. Гарантии сходимости всегда и везде у алгоритма нет, хотя практика показывает, что почти всегда алгоритм дает результат. Ньютоновские методы Направление поиска, соответствующее наискорейшему спуску, связано с линейной аппроксимацией целевой функции. Методы, использующие вторые производные, возникли из квадратичной аппроксимации целевой функции, т. е. при разложении функции в ряд Тейлора отбрасываются члены третьего и более высоких порядков. где - матрица Гессе. Минимум правой части (если он существует) достигается там же, где и минимум квадратичной формы. Запишем формулу для определения направления поиска: Минимум достигается при Алгоритм оптимизации, в котором направление поиска определяется из этого соотношения, называется методом Ньютона, а направление - ньютоновским направлением. В задачах поиска минимума произвольной квадратичной функции с положительной матрицей вторых производных метод Ньютона дает решение за одну итерацию независимо от выбора начальной точки. Классификация Ньютоновских методов Собственно метод Ньютона состоит в однократном применении Ньютоновского направления для оптимизации квадратичной функции. Если же функция не является квадратичной, то верна следующая теорема. Теорема 1.4. Если матрица Гессе нелинейной функции f общего вида в точке минимума X* положительно определена, начальная точка выбрана достаточно близко к X* и длины шагов подобраны верно, то метод Ньютона сходится к X* с квадратичной скоростью. Метод Ньютона считается эталонным, с ним сравнивают все разрабатываемые оптимизационные процедуры. Однако метод Ньютона работоспособен только при положительно определенной и хорошо обусловленной матрицей Гессе (определитель ее должен быть существенно больше нуля, точнее отношение наибольшего и наименьшего собственных чисел должно быть близко к единице). Для устранения этого недостатка используют модифицированные методы Ньютона, использующие ньютоновские направления по мере возможности и уклоняющиеся от них только тогда, когда это необходимо. Общий принцип модификаций метода Ньютона состоит в следующем: на каждой итерации сначала строится некоторая "связанная" с положительно определенная матрица, а затем вычисляется по формуле Так как положительно определена, то - обязательно будет направлением спуска. Процедуру построения организуют так, чтобы она совпадала с матрицей Гессе, если она является положительно определенной. Эти процедуры строятся на основе некоторых матричных разложений. Другая группа методов, практически не уступающих по быстродействию методу Ньютона, основана на аппроксимации матрицы Гессе с помощью конечных разностей, т.к. не обязательно для оптимизации использовать точные значения производных. Эти методы полезны, когда аналитическое вычисление производных затруднительно или просто невозможно. Такие методы называются дискретными методами Ньютона. Залогом эффективности методов ньютоновского типа является учет информации о кривизне минимизируемой функции, содержащейся в матрице Гессе и позволяющей строить локально точные квадратичные модели целевой функции. Но ведь возможно информацию о кривизне функции собирать и накапливать на основе наблюдения за изменением градиента во время итераций спуска. Соответствующие методы, опирающиеся на возможность аппроксимации кривизны нелинейной функции без явного формирования ее матрицы Гессе, называют квази-Ньютоновскими методами. Отметим, что при построении оптимизационной процедуры ньютоновского типа (в том числе и квази-Ньютоновской) необходимо учитывать возможность появления седловой точки. В этом случае вектор наилучшего направления поиска будет все время направлен к седловой точке, вместо того, чтобы уходить от нее в направлении "вниз". Метод Ньютона-Рафсона Данный метод состоит в многократном использовании Ньютоновского направления при оптимизации функций, не являющихся квадратичными. Основная итерационная формула многомерной оптимизации используется в этом методе при выборе направления оптимизации из соотношения Реальная длина шага скрыта в ненормализованном Ньютоновском направлении. Так как этот метод не требует значения целевой функции в текущей точке, то его иногда называют непрямым или аналитическим методом оптимизации. Его способность определять минимум квадратичной функции за одно вычисление выглядит на первый взгляд исключительно привлекательно. Однако это "одно вычисление" требует значительных затрат. Прежде всего, необходимо вычислить n частных производных первого порядка и n(n+1)/2 - второго. Кроме того, матрица Гессе должна быть инвертирована. Это требует уже порядка n3 вычислительных операций. С теми же самыми затратами методы сопряженных направлений или методы сопряженного градиента могут сделать порядка n шагов, т.е. достичь практически того же результата. Таким образом, итерация метода Ньютона-Рафсона не дает преимуществ в случае квадратичной функции. Если же функция не квадратична, то Сама по себе стратегия не различает, к какой именно стационарной точке (минимума, максимума, седловой) приближается поиск, а вычисления значений целевой функции, по которым можно было бы отследить, не возрастает ли функция, не делаются. Значит, все зависит от того, в зоне притяжения какой стационарной точки оказывается стартовая точка поиска. Стратегия Ньютона-Рафсона редко используется сама по себе без модификации того или иного рода. Методы Пирсона Пирсон предложил несколько методов с аппроксимацией обратного гессиана без явного вычисления вторых производных, т.е. путем наблюдений за изменениями направления антиградиента. При этом получаются сопряженные направления. Эти алгоритмы отличаются только деталями. Приведем те из них, которые получили наиболее широкое распространение в прикладных областях. Алгоритм Пирсона № 2. В этом алгоритме обратный гессиан аппроксимируется матрицей Hk, вычисляемой на каждом шаге по формуле В качестве начальной матрицы H0 выбирается произвольная положительно определенная симметрическая матрица. Данный алгоритм Пирсона часто приводит к ситуациям, когда матрица Hk становится плохо обусловленной, а именно - она начинает осцилировать, колеблясь между положительно определенной и не положительно определенной, при этом определитель матрицы близок к нулю. Для избежания этой ситуации необходимо через каждые n шагов перезадавать матрицу, приравнивая ее к H0. Алгоритм Пирсона № 3. В этом алгоритме матрица Hk+1 определяется из формулы Hk+1 = Hk + Траектория спуска, порождаемая алгоритмом, аналогична поведению алгоритма Дэвидона-Флетчера-Пауэлла, но шаги немного короче. Пирсон также предложил разновидность этого алгоритма с циклическим перезаданием матрицы. Проективный алгоритм Ньютона-Рафсона
Пирсон предложил идею алгоритма, в котором матрица рассчитывается из соотношения H0=R0, где матрица R0 такая же как и начальные матрицы в предыдущих алгоритмах. Когда k кратно числу независимых переменных n, матрица Hk заменяется на матрицу Rk+1, вычисляемую как сумма Величина Hk(f(Xk+1) - f(Xk)) является проекцией вектора приращения градиента (f(Xk+1)-f(Xk)), ортогональной ко всем векторам приращения градиента на предыдущих шагах. После каждых n шагов Rk является аппроксимацией обратного гессиана H-1(Xk), так что в сущности осуществляется (приближенно) поиск Ньютона. Метод Дэвидона-Флетчера-Пауэла Этот метод имеет и другие названия - метод переменной метрики, квазиньютоновский метод, т.к. он использует оба эти подхода. Метод Дэвидона-Флетчера-Пауэла (ДФП) основан на использовании ньютоновских направлений, но не требует вычисления обратного гессиана на каждом шаге. Направление поиска на шаге k является направлением где Hi - положительно определенная симметричная матрица, которая обновляется на каждом шаге и в пределе становится равной обратному гессиану. В качестве начальной матрицы H обычно выбирают единичную. Итерационная процедура ДФП может быть представлена следующим образом: 3. Одномерным поиском (обычно кубической интерполяцией) вдоль направления определяется k, минимизирующее функцию. 4. Полагается. 5. Полагается. 6. Определяется и. Если Vk или достаточно малы, процедура завершается. 9. Увеличить k на единицу и вернуться на шаг 2. Метод эффективен на практике, если ошибка вычислений градиента невелика и матрица Hk не становится плохо обусловленной. Матрица Ak обеспечивает сходимость Hk к G-1, матрица Bk обеспечивает положительную определенность Hk+1 на всех этапах и в пределе исключает H0. В случае квадратичной функции т.е. алгоритм ДФП использует сопряженные направления. Таким образом, метод ДФП использует как идеи ньютоновского подхода, так и свойства сопряженных направлений, и при минимизации квадратичной функции сходится не более чем за n итераций. Если оптимизируемая функция имеет вид, близкий к квадратичной функции, то метод ДФП эффективен за счет хорошей аппроксимации G-1(метод Ньютона). Если же целевая функция имеет общий вид, то метод ДФП эффективен за счет использования сопряженных направлений.
(3.9)
; , если ;
называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам (рис. 6.5)
.
, (3.10)
, (3.11)
; (3.12)
(3.13)
; (3.16)
; (3.17)
– норма вектора.Градиентные методы оптимизации
