Градиентные методы

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

На 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.

• 3. Вычисляются f(Xk+1) и.
• 4. Направление определяется из соотношения:

• 5. После (n+1)-й итерации (т.е. при k=n) производится рестарт: полагается X0=Xn+1 и осуществляется переход к шагу 1.
• 6. Алгоритм останавливается, когда

где - произвольная константа.

Преимуществом алгоритма Флетчера-Ривса является то, что он не требует обращения матрицы и экономит память ЭВМ, так как ему не нужны матрицы, используемые в Ньютоновских методах, но в то же время почти столь же эффективен как квази-Ньютоновские алгоритмы. Т.к. направления поиска взаимно сопряжены, то квадратичная функция будет минимизирована не более, чем за 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 обычно выбирают единичную. Итерационная процедура ДФП может быть представлена следующим образом:

• 1. На шаге k имеются точка Xk и положительно определенная матрица Hk.
• 2. В качестве нового направления поиска выбирается

3. Одномерным поиском (обычно кубической интерполяцией) вдоль направления определяется k, минимизирующее функцию.

4. Полагается.

5. Полагается.

6. Определяется и. Если Vk или достаточно малы, процедура завершается.

• 7. Полагается Uk = f(Xk+1) - f(Xk).
• 8. Матрица Hk обновляется по формуле

9. Увеличить k на единицу и вернуться на шаг 2.

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

Матрица Ak обеспечивает сходимость Hk к G-1, матрица Bk обеспечивает положительную определенность Hk+1 на всех этапах и в пределе исключает H0.

В случае квадратичной функции

т.е. алгоритм ДФП использует сопряженные направления.

Таким образом, метод ДФП использует как идеи ньютоновского подхода, так и свойства сопряженных направлений, и при минимизации квадратичной функции сходится не более чем за n итераций. Если оптимизируемая функция имеет вид, близкий к квадратичной функции, то метод ДФП эффективен за счет хорошей аппроксимации G-1(метод Ньютона). Если же целевая функция имеет общий вид, то метод ДФП эффективен за счет использования сопряженных направлений.

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

Известны различные методы решения задачи оптимизации. Одним из наиболее широко применяемых является метод градиента, называемый также методом Бокса-Уилсона и методом крутого восхождения.

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в фак­торном пространстве изо­бражены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремаль­ное значение функции от­клика у ext .

Если мы выбе­рем какую-либо точку фак­торного пространства в ка­честве исходной (х 1 0 , х 2 0), то наикратчайший путь к вершине функции откли­ка из этой точки – это путь, по кривой, касательная к которой в каждой точке совпадает с нормалью к кривой уровня, т.е. это путь в направлении гради­ента функции отклика.

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и опреде­лить истинное направление градиента.

Согласно методу градиента в какой-то части факторного пространства выбирается исходная точка (исходные уровни) х 1 0 , х 2 0 . Относительно этих исходных уровней строится сим­метричный двухуровневый план эксперимента. Причем интер­вал варьирования выбирается настолько малым, чтобы ли­нейная модель оказалась адекватной. Известно, что любая кривая на достаточно малом участке может быть аппрокси­мирована линейной моделью.

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

и проверяется ее адекватность.

Если для выбранного интервала варьирования линейная мо­дель оказалась адекватной, то может быть определено на­правление градиента:

Таким образом, направление градиента функции отклика определяется значениями коэффициентов регрессии. Это означает, что мы будем двигаться в направлении градиента, если из точки с координатами ( ) перейдем в точку с координатами:

где m – положительное число, определяющее величину шага в на­правлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав ве­личину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .

Затем делаем шаг в направлении градиента, т.е. осу­ществляем опыт в точке с координатами . Если значе­ние функции отклика возросло по сравнению с ее значением в исходном уровне, делаем еще шаг в направлении градиен­та, т.е. осуществляем опыт в точке с координатами:

Движение по градиенту продолжаем до тех пор, пока функция отклика не начнет уменьшаться. На рис. 4.3 движение по градиенту соответствует прямой, вы­ходящей из точки (х 1 0 , х 2 0). Она постепенно отклоняется от истинного направления градиента, показанного штриховой линией, вследствие нелинейности функции отклика.

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

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

фи­циент , значит, область экстремума функции откли­ка (область оптимума) еще не достигнута. Определяется новое направление градиента и начинается движение к обла­сти оптимума.

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

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

1) исходные уровни факторов (х j 0) следует выбирать воз­можно ближе к точке оптимума, если есть какая-то априор­ная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значе­ние интервала варьирования, при котором функция отклика остается значимой;

3) значение шага (т ) при движении по градиенту выбирают таким образом, чтобы наибольшее из произведений не превышало разности верхнего и нижнего уровней факто­ров в нормированном виде

.

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

Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.

Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .

Описание [ | ]

Усовершенствования [ | ]

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

Для функций, близких к квадратичным, эффективным является метод сопряжённых градиентов .

Применение в искусственных нейронных сетях [ | ]

Метод градиентного спуска с некоторой модификацией широко применяется для обучения перцептрона и в теории искусственных нейронных сетей известен как метод обратного распространения ошибки . При обучении нейросети типа «персептрон» требуется изменять весовые коэффициенты сети так, чтобы минимизировать среднюю ошибку на выходе нейронной сети при подаче на вход последовательности обучающих входных данных. Формально, чтобы сделать всего один шаг по методу градиентного спуска (сделать всего одно изменение параметров сети), необходимо подать на вход сети последовательно абсолютно весь набор обучающих данных, для каждого объекта обучающих данных вычислить ошибку и рассчитать необходимую коррекцию коэффициентов сети (но не делать эту коррекцию), и уже после подачи всех данных рассчитать сумму в корректировке каждого коэффициента сети (сумма градиентов) и произвести коррекцию коэффициентов «на один шаг». Очевидно, что при большом наборе обучающих данных алгоритм будет работать крайне медленно, поэтому на практике часто производят корректировку коэффициентов сети после каждого элемента обучения, где значение градиента аппроксимируются градиентом функции стоимости, вычисленном только на одном элементе обучения. Такой метод называют стохастическим градиентным спуском или оперативным градиентным спуском . Стохастический градиентный спуск является одной из форм стохастического приближения. Теория стохастических приближений даёт условия сходимости метода стохастического градиентного спуска.

Ссылки [ | ]

• J. Mathews. Module for Steepest Descent or Gradient Method. (недоступная ссылка)

Литература [ | ]

• Акулич И. Л. Математическое программирование в примерах и задачах. - М. : Высшая школа, 1986. - С. 298-310.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. - М. : Мир, 1985.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М. : Энергоатомиздат, 1972.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М. : МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М. : МИФИ, 1980.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М. : Наука, 1970. - С. 575-576.
• С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. - Нижний Новгород: Издательство Нижегородского Университета, 2007. - С. 357-363.

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

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

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) и появляется желание сделать в направлении лишь такой шаг, который бы обеспечил "существенное убывание" функции Более того, на практике иногда довольствуются определением значения которое просто обеспечивает уменьшение значения целевой функции.

Градиентные методы оптимизации

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

В общем случае значение критерия оптимизации R может рассматри­ваться как функция R (х ь хь ..., х п), определенная в л-мерном пространстве. Поскольку не существует наглядного графического изображения я-мерного пространства, воспользуемся случаем двумерного пространства.

Если R (л ь х 2) непрерывна в области D, то вокруг оптимальной точки M°(xi°, х г °) можно провести в данной плоскости замкнутую линию, вдоль ко­торой значение R = const. Таких линий, называемых линиями равных уровней, вокруг оптимальной точки можно провести множество (в зависимости от шага

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

Понятие градиента широко используется в инженерных расчетах при на­хождении экстремумов нелинейных функций. Градиентные методы относятся к численным методам поискового типа. Они универсальны и особенно эффек­тивны в случаях поиска экстремумов нелинейных функций с ограничениями, а также когда аналитическая функция неизвестна совсем. Сущность этих мето­дов заключается в определении значений переменных, обеспечивающих экс­тремум функции цели, путем движения по градиенту (при поиске max) или в противоположном направлении (min). Различные градиентные методы отли­чаются один от другого способом определения движения к оптимуму. Суть заключается в том, что если линии равных уровней R{xu x i) характеризуют графически зависимость R(x\jc?), то поиск оптимальной точки можно вести по-разному. Например, изобразить сетку на плоскости х\, хг с указанием зна­чений R в узлах сетки (рис. 2.13).

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

Численные методы

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

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

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

Выбор узловых точек, проведение экспериментов при определен­ных значениях (уровнях) независимых переменных (при непра­вильном выборе шага изменения фактора либо «пропустим» ха­рактерную особенность изучаемого процесса, либо удлиним про­цедуру и повысим трудоемкость поиска закономерности);

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

Выбор и использование критериев согласия, на основе которых на­ходятся параметры приближающих функций;

Выполнение требований заданной точности к выбору приближаю­щей функции.

В задачах приближения функций многочленами используются три класса

Линейная комбинация степенных функций (ряд Тейлора, много­члены Лагранжа, Ньютона и др.);

Комбинация функций соз пх, ш их (ряды Фурье);

Многочлен, образуемый функциями ехр (-а, г).

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