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

Направление наискорейшего спуска соответствует направлению наибольшего убывания функции. Известно, что направление наибольшего возрастания функции двух переменных u = f(x, у) характеризуется ее градиентом:

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

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

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

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

Метод градиентного спуска обладает тем же недостатком, что и метод покоординатного спуска: при наличии оврагов на поверхности сходимость метода очень медленная.

В описанном методе требуется вычислять на каждом шаге оптимизации градиент целевой функции f(х):

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

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

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

Метод наискорейшего спуска для случая функции двух переменных z = f(x,y).

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

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

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

На 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. Понятие градиентных методов. Необходимым условием существова­ния экстремума непрерывной дифференцируемой функции яв­ляются условия вида

где – аргументы функции. Более компактно это условие можно записать в форме

(2.4.1)

где – обозначение градиента функции в заданной точке.

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

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

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

Через n и n– 1 обозначены номера шагов, а через и – векторы, соответствующие значениям аргументов целевой функции на n -м и (п– 1)-м шагах. После r-го шага можно получить

т. е. после r - шагов - целевая функция уже не будет увеличиваться (уменьшать­ся) при любом дальнейшем изменении ее аргументов;. Последнее означает достижение точки с координатами для которой можно написать, что

	(2.4.2)
	(2.4.3)

где – экстремальное значение целевой функции.

Для решения (2.4.1) в общем случае может быть применена следующая процедура. Запишем значение координат целевой функции в виде

где – некоторый коэффициент (скаляр), не равный нулю.

В точке экстремума так как

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

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

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

Вычисление градиента. Так как в результате оптимизации находятся координаты точки экстремума, для которых справедливо соотношение:

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

	(2.4.5)

где – малое изменение координаты

Если предположить, что точка определения градиента находится посередине

отрезка то

Выбор (2.4.5) или (2.4.6) зависит от крутизны функции на участке - Ах;; если крутизна не велика, предпочтение следует отдать (2.4.5), так как вычислений здесь меньше; в противном случае более точные результаты дает вычисление по (2.4.4). Повышение точности определения градиента возможно также за счет усреднения случайных отклонений.

Выбор значения шага Сложность выбора значения шага состоит в том, что направление градиента может меняться от точки к точке. При этом слишком большой шаг приведёт к отклонению от оптимальной траектории, т. е. от направления по градиенту или антиградиенту, а слишком малый шаг -к очень медленному движению к экстремуму за счет необходимости выполнения большого объёма вычислений.

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

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

Направление градиента в точке совпадает с направлением касательной. При поиске минимальной экстремальной точки изменение координаты х при движении по градиенту можно записать в виде:

Рис.2.4.2 Схема вычисления шага по методу Ньютона – Рафсона.

Подставив (2.4.7) в (2.4.8), получим:

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

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

и т.д. вычисление прекращается, если изменения целевой функции малы, т. е.

где – допустимая погрешность определения целевой функции.

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

Таким образом, оптимальные значения и для поиска минимума и максимума соответственно определяются из решения уравнений:

В (1) и (2) соответственно

Следовательно определение на каждом шаге заключается в нахождении из уравнений (1) или (2) для каждой точки траектории движения вдоль градиента, начиная с исходной.

В задаче безусловной оптимизации отсутствуют ограничения.

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

Градиент скалярной функции F (X ) в некоторой точке направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения F (X ), проходящей через точку X k ). Вектор, противоположный градиенту  антиградиент  направлен в сторону наискорейшего убывания функции F (X ). В точке экстремума grad F (X )= 0.

В градиентных методах движение точки при поиске минимума целевой функции описывается итерационной формулой

где  k  параметр шага на k -й итерации вдоль антиградиента. Для методов восхождения (поиска максимума) нужно двигаться по градиенту.

Различные варианты градиентных методов отличаются друг от друга способом выбора параметра шага, а также учета направления движения на предыдущем шаге . Рассмотрим следующие варианты градиентных методов: с постоянным шагом, с переменным параметром шага (дроблением шага), метод наискорейшего спуска и метод сопряженных градиентов.

Метод с постоянным параметром шага. В этом методе параметр шага постоянен на каждой итерации. Возникает вопрос: как практически выбрать величину параметра шага? Достаточно малый параметр шага может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой параметр шага может привести к проскакиванию точки минимума и к колебательному вычислительному процессу около этой точки. Указанные обстоятельства являются недостатками метода. Поскольку невозможно заранее угадать приемлемое значение параметра шага  k , то возникает необходимость использования градиентного метода с переменным параметром шага.

По мере приближения к оптимуму вектор градиента уменьшается по величине, стремясь к нулю, поэтому при  k = const длина шага постепенно уменьшается. Вблизи оптимума длина вектора градиента стремится к нулю. Длина вектора или норма в n -мерном евклидовом пространстве определяется по формуле

, где n  число переменных.

Варианты остановки процесса поиска оптимума:

C практической точки зрения удобней пользоваться 3-им критерием остановки (поскольку представляют интерес значения параметров проектирования), однако для определения близости точки экстремума нужно ориентироваться на 2-й критерий. Для остановки вычислительного процесса можно использовать несколько критериев.

Рассмотрим пример. Найти минимум целевой функции F (X ) = (x 1  2) 2 + (x 2  4) 2 . Точное решение задачи X*= (2,0;4,0). Выражения для частных производных

,
.

Выбираем шаг  k = 0,1. Осуществим поиск из начальной точки X 1 = . Решение представим в виде таблицы.

Градиентный метод с дроблением параметра шага. В этом случае в процессе оптимизации параметр шага  k уменьшается, если после очередного шага целевая функция возрастает (при поиске минимума). При этом часто длина шага дробится (делится) пополам, и шаг повторяется из предыдущей точки. Так обеспечивается более точный подход к точке экстремума.

Метод наискорейшего спуска. Методы с переменным шагом являются более экономичными с точки зрения количества итераций. В случае если оптимальная длина шага  k вдоль направления антиградиента является решением одномерной задачи минимизации, то такой метод называется методом наискорейшего спуска. В этом методе на каждой итерации решается задача одномерной минимизации:

F(X k+1 )=F(X k   k S k )=min F( k ), S k =  F(X);

 k >0

.

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

Пример. min F (x 1 , x 2 ) = 2x 1 2 + 4x 2 3 – 3. Тогда  F (X )= [ 4x 1 ; 12x 2 2 ]. Пусть точка X k = , следовательно  F (X )= [ 8; 12], F (X k   S k ) =

2(2  8 ) 2 + 4(1  12 ) 3  3. Необходимо найти , доставляющее минимум данной функции.

Алгоритм метода наискорейшего спуска (для поиска минимума)

Начальный шаг . Пусть   константа остановки. Выбрать начальную точку X 1 , положить k = 1 и перейти к основному шагу.

Основной шаг . Если || gradF (X )||< , то закончить поиск, в противном случае определить  F (X k ) и найти  k  оптимальное решение задачи минимизации F (X k   k S k ) при  k  0. Положить X k +1 = X k   k S k , присвоить k =

k + 1 и повторить основной шаг.

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

Метод дихотомии (бисекции) Начальный шаг. Выбирают константу различимости  и конечную длину интервала неопределенности l . Величина  должна быть по возможности меньшей, однако позволяющей различать значения функции F ( ) и F ( ) . Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить k =

Основной этап состоит из конечного числа однотипных итераций.

k-я итерация.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются. Решение x * = (a k + b k )/2. В противном случае

,
.

Шаг 2. Если F ( k ) < F ( k ), положить a k +1 = a k ; b k +1 =  k . В противном случае a k +1 =  k и b k +1 = b k . Присвоить k = k + 1 и перейти к шагу 1.

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

 = 0,618034 от конца интервала.

Алгоритм метода золотого сечения

Начальный шаг. Выбрать допустимую конечную длину интервала неопределенности l > 0. Пусть [ a 1 , b 1 ]  начальный интервал неопределенности. Положить  1 = a 1 +(1   )(b 1  a 1 ) и  1 = a 1 +  (b 1  a 1 ) , где  = 0,618 . Вычислить F ( 1 ) и F ( 1 ) , положить k = 1 и перейти к основному этапу.

Шаг 1. Если b k  a k  l , то вычисления заканчиваются x * = (a k + b k )/ 2. В противном случае если F ( k ) > F ( k ) , то перейти к шагу 2; если F ( k )  F ( k ) , перейти к шагу 3.

Шаг 2. Положить a k +1 =  k , b k +1 = b k ,  k +1 =  k ,  k +1 = a k +1 +  (b k +1 – a k +1 ). Вычислить F ( k +1 ), перейти к шагу 4.

Шаг 3. Положить a k +1 = a k , b k +1 =  k ,  k +1 =  k ,  k +1 = a k +1 + (1   )(b k +1 – a k +1 ). Вычислить F ( k +1 ).

Шаг 4. Присвоить k = k + 1, перейти к шагу 1.

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

Метод сопряженных градиентов (Флетчера-Ривса). В этом методе выбор направления движения на k + 1 шаге учитывает изменение направления на k шаге. Вектор направления спуска является линейной комбинацией направления антиградиента и предыдущего направления поиска. В этом случае при минимизации овражных функций (с узкими длинными впадинами) поиск идет не перпендикулярно оврагу, а вдоль него, что позволяет быстрее прийти к минимуму. Координаты точки при поиске экстремума методом сопряженных градиентов рассчитываются по выражению X k +1 = X k   V k +1 , где V k +1 – вектор, рассчитываемый по следующему выражению:

.

На первой итерации обычно полагается V = 0 и выполняется поиск по антиградиенту, как в методе наискорейшего спуска. Затем направление движения отклоняется от направления антиградиента тем больше, чем значительнее менялась длина вектора градиента на последней итерации. После n шагов для коррекции работы алгоритма делают обычный шаг по антиградиенту.

Алгоритм метода сопряженных градиентов

Шаг 1. Ввести начальную точку Х 0 , точность  , размерность n .

Шаг 2. Положить k = 1.

Шаг 3. Положить вектор V k = 0.

Шаг 4. Вычислить grad F (X k ).

Шаг 5. Вычислить вектор V k +1.

Шаг 6. Выполнить одномерный поиск по вектору V k +1.

Шаг 7. Если k < n , положить k = k + 1 и перейти к шагу 4, иначе к шагу 8.

Шаг 8. Если длина вектора V меньше , окончить поиск, иначе  перейти к шагу 2.

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

Недостатки градиентных методов

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

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

Метод релаксации

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

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

Пусть – осевое направление, т.е. .

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

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

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

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

Алгоритм спуска для выбранного осевого направления может быть записан так

(3.8)

где -значение варьируемой переменной на каждом шаге спуска;

Величина k+1 шага, которая может изменяться в зависимости от номера шага:

– функция знака z;

Вектор точки, в которой последний раз производилось вычисление производных ;

Знак “+” в алгоритме (3.8) принимается при поиске max I, а знак “-” – при поиске min I.Чем меньше шаг h., тем больше количество вычислений на пути движения к оптимуму. Но при слишком большой величине h вблизи оптимума может возникнуть зацикливание процесса поиска. Вблизи оптимума необходимо, чтобы выполнялось условие h

Простейший алгоритм изменения шага h состоит в следующем. В начале спуска задается шаг , равный например, 10% от диапазона d; изменения с этим шагом производится спуск по выбранному направлению до тез пор, пока выполняется условие для двух последующих вычислений

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

Формальная запись этого алгоритма следующая:

(3.9)

В результате использования такой стратегии ша спуска будет уменьшатся в районе оптимума по данному направлению и поиск по направлению можно прекратить, когда станет меньше E.

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

Рисунок 3.5 – Траектория движения к оптимуму в методе релаксации

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

Шаг 1. – осевое направление,

; , если ;

Шаг 2. – новое осевое направление;

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

В этом методе используется градиент функции . Градиентом функции в точке называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам (рис. 6.5)

Рисунок 3.6 – Градиент функции

.

Направление градиента – это направление наиболее быстрого возрастания функции (наиболее крутого “склона” поверхности отклика). Противоположное ему направление (направление антиградиента) – это направление наибыстрейшего убывания (направление наискорейшего “спуска” величин ).

Проекция градиента на плоскость переменных перпендикулярна касательной к линии уровня , т.е. градиент ортогонален к линиям постоянного уровня целевой функции (рис. 3.6).

Рисунок 3.7 – Траектория движения к оптимуму в методе

градиента

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

Поиск оптимума производится в два этапа. На первом этапе находятся значения частных производных по всем переменным , которые определяют направление градиента в рассматриваемой точке. На втором этапе осуществляется шаг в направлении градиента при поиске максимума или в противоположном направлении – при поиске минимума.

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

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

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

, (3.10)

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

, (3.11)

где – положительная константа;

“+” – при поиске max I;

“-” – при поиске min I.

Алгоритм градиентного поиска при нормировании градиента (деление на модуль) применяется в виде

; (3.12)

(3.13)

Определяет величину шага по направлению градиента.

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

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

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

Процесс поиска продолжается до тех пор, пока , , не станут близки к нулю или пока не будет достигнута граница области задания переменных.

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

Критерии окончания поиска оптимума:

; (3.16)

; (3.17)

где – норма вектора.

Поиск завершается при выполнении одного из условий (3.14) – (3.17).

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