Лекция 6.
Градиентные методы решения задач нелинейного программирования.
Вопросы: 1. Общая характеристика методов.
2. Метод градиента.
3. Метод наискорейшего спуска.
4. Метод Франка-Фулфа.
5. Метод штрафных функций.
1. Общая характеристика методов.
Градиентные методы представляют собой приближенные (итерационные) методы решения задачи нелинейного программирования и позволяют решить практически любую задачу. Однако при этом определяется локальный экстремум. Поэтому целесообразно применять эти методы для решения задач выпуклого программирования, в которых каждый локальный экстремум является и глобальным. Процесс решения задачи состоит в том, что, начиная с некоторой точки х (начальной), осуществляется последовательный переход в направлении gradF(x), если определяется точка максимума, и –gradF(x) (антиградиента), если определяется точка минимума, до точки, являющейся решением задачи. При этом эта точка может оказаться как внутри области допустимых значений, так и на ее границе.
Градиентные методы можно разделить на два класса (группы). К первой группе относятся методы, в которых все исследуемые точки принадлежат допустимой области. К таким методам относятся: метод градиента, наискорейшего спуска, Франка-Вулфа и др. Ко второй группе относятся методы, в которых исследуемые точки могут и не принадлежать допустимой области. Общим из таких методов является метод штрафных функций. Все методы штрафных функций отличаются друг от друга способом определения «штрафа».
Основным понятием, используемым во всех градиентных методах, является понятие градиента функции, как направления наискорейшего возрастания функции.
При определении решения градиентными методами итерационный процесс продолжается до тех пор, пока:
Либо grad F(x*) = 0, (точное решение);
где
- две последовательные точки,
-
малое число, характеризующее точность
решения.
2. Метод градиента.
Представим человека, стоящего на склоне оврага, которому необходимо спуститься вниз (на дно). Наиболее естественным, кажется, направление в сторону наибольшей крутизны спуска, т.е. направление (-grad F(x)). Получаемая при этом стратегия, называемая градиентным методом , представляет собой последовательность шагов, каждый из которых содержит две операции:
а) определение направления наибольшей крутизны спуска (подъема);
б) перемещение в выбранном направлении на некоторый шаг.
Правильный выбор шага имеет существенное значение. Чем шаг меньше, тем точнее результат, но больше вычислений. Различные модификации градиентного метода и состоят в использовании различных способов определения шага. Если на каком-либо шаге значение F(x) не уменьшилось, это означает, что точку минимума «проскочили», в этом случае необходимо вернуться к предыдущей точке и уменьшить шаг, например, вдвое.
Схема решения.
принадлежащей допустимой области
3. Выбор шага h.
x (k+1)
= x (k)
«-» - если min.
5. Определение F(x (k +1)) и:
Если
,
решение найдено;
Замечание. Если grad F(x (k)) = 0, то решение будет точным.
Пример.
F(x) = -6x 1
+ 2x 1 2
– 2x 1 x 2
+ 2x 2 2
min,
x 1 +x 2
2,x 1
0, x 2
0,
= 0,1.
3. Метод наискорейшего спуска.
В отличие от метода градиента, в котором градиент определяют на каждом шаге, в методе наискорейшего спуска градиент находят в начальной точке и движение в найденном направлении продолжают одинаковыми шагами до тех пор, пока значение функции уменьшается (увеличивается). Если на каком-либо шаге F(x) возросло (уменьшилось), то движение в данном направлении прекращается, последний шаг снимается полностью или наполовину и вычисляется новое значение градиента и новое направление.
Схема решения.
1. Определение х 0 = (х 1 ,x 2 ,…,x n),
принадлежащей допустимой области,
и F(x 0), k = 0.
2. Определение grad F(x 0) или –gradF(x 0).
3. Выбор шага h.
4. Определение следующей точки по формуле
x (k+1)
= x (k)
h grad F(x (k)),
«+» - если max,
«-» - если min.
5. Определение F(x (k +1)) и:
Если
,
решение найдено;
Если нет:
а) при поиске min: - если F(x (k +1))
Если F(x (k +1))
>F(x (k))
– переход к п. 2; б) при поиске max: -
еслиF(x (k +1))
>F(x (k))
– переход к п. 4; Если F(x (k +1))
Замечания:
1. Если grad F(x (k))
= 0, то решение будет точным. 2. Преимуществом метода
наискорейшего спуска является его
простота и сокращение расчетов, так
как grad F(x) вычисляется не во всех точках,
что важно для задач большой
размерности. 3. Недостатком является то,
что шаги должны быть малыми, чтобы не пропустить точку оптимума. Пример.
F(x) = 3x 1
– 0,2x 1 2
+ x 2 -
0,2x 2 2
x 1
+ x 2
x 1
+ 2x 2
4. Метод Франка-Вулфа.
Метод используется для оптимизации
нелинейной целевой функции при линейных
ограничениях. В окрестности исследуемой
точки нелинейная целевая функция
заменяется линейной функцией и задача
сводится к последовательному решению
задач линейного программирования. Схема решения.
1. Определение х 0 = (х 1 ,x 2 ,…,x n),
принадлежащей допустимой области, и
F(x 0), k = 0. 2. Определение grad F(x (k)). 3. Строят функцию 4. Определение max(min)f(x) при
исходных ограничениях. Пусть это будет
точка z (k) . 5. Определение шага вычислений x (k +1) =x (k) +
6. Определение F(x (k +1))
и проверяют необходимость дальнейших
вычислений: Если
Если нет, то переход к п. 2. Пример.
F(x) = 4x 1
+ 10x 2
–x 1 2
–x 2 2
x 1
+x 2 x 2
5. Метод штрафных функций.
Пусть необходимо найти F(x 1 ,x 2 ,…,x n)
g i
(x 1 ,
x 2 ,…,x n)
Функции F и g i –
выпуклые или вогнутые. Идея метода штрафных функций
заключается в поиске оптимального
значения новой целевой функции Q(x) = F(x)
+ H(x), которая является суммой исходной
целевой функции и некоторой функции
H(x), определяемой системой ограничений
и называемой штрафной функцией. Штрафные
функции строят таким образом, чтобы
обеспечить либо быстрое возвращение в
допустимую область, либо невозможность
выходы из нее. Метод штрафных функций
сводит задачу на условный экстремум к
решению последовательности задач на
безусловный экстремум, что проще.
Существует множество способов построения
штрафной функции. Наиболее часто она
имеет вид: H(x) =
где
Примечание
: Чем меньше
Начинают решение с малых
Используя штрафную функцию,
последовательно переходят от одной
точки к другой до тех пор, пока не получат
приемлемое решение. Схема решения.
1. Определение начальную точку х 0 = (х 1 ,x 2 ,…,x n),
F(x 0) и k = 0. 2. Выбирают шаг вычислений h. 3. Определяют частные производные
4. Определяют координаты следующей точки
по формуле: x j (k +1) 5. Если x (k +1) а) если
б) если grad F(x (k +1))
= 0, то найдено точное решение. Если x (k +1) Пример.
F(x) = – x 1 2
– x 2 2
(x 1
-5) 2 +(x 2
-5) 2 Вкину немного своего экспириенса:) Метод покоординатного спуска
Идея данного метода в том, что поиск происходит в направлении покоординатного спуска во время новой итерации. Спуск осуществляется постепенно по каждой координате. Количество координат напрямую зависит от количества переменных. После нахождения значения переменной, необходимо повторить итерацию с фиксацией всех аргументов кроме x2 и начать производить спуск по новой координате до следующей новой точке M2(x11,x21,x30…,xn0). Теперь значение новой точки будет происходить по выражению: И снова итерация с фиксацией будет повторяться до тех пор, пока все аргументы от xi до xn не закончатся. При последней итерации, мы последовательно пройдем по всем возможным координатам, в которых уже найдем локальные минимумы, поэтому целевая функция на последний координате дойдет до глобального минимума. Одним из преимуществ данного метода в том, что в любой момент времени есть возможность прервать спуск и последняя найденная точка будет являться точкой минимума. Это бывает полезно, когда метод уходит в бесконечный цикл и результатом этого поиска можно считать последнюю найденную координату. Однако, целевая установка поиска глобального минимума в области может быть так и не достигнута из-за того, что мы прервали поиск минимума (см. Рисунок 1). Исследование данного метода показали, что каждая найденная вычисляемая точка в пространстве является точкой глобального минимума заданной функции, а функция z = f(x1, x2,…, xn) является выпуклой и дифференцируемой. Можно сделать вывод о том, что данный алгоритм отлично справляется с простыми задачами многомерной оптимизации, путём последовательно решения n количества задач одномерной оптимизации, например, методом золотого сечения. Ход выполнения метода покоординатного спуска происходит по алгоритму описанного в блок схеме (см. Рисунок 3). Итерации выполнения данного метода: Итого, у нас имеется отличный и многофункциональный алгоритм многомерной оптимизации, который способен разбивать сложную задачу, на несколько последовательно итерационных одномерных. Да, данный метод достаточно прост в реализации и имеет легкое определение точек в пространстве, потому что данной метод гарантирует сходимость к локальной точке минимума. Но даже при таких весомых достоинствах, метод способен уходить в бесконечные циклы из-за того, что может попасть в своего рода овраг. Метод Нелдера - Мида
Стоит отметить известность данного алгоритма среди исследователей методов многомерной оптимизации. Метод Нелдера – Мида один из немногих методов, который основанный на концепции последовательной трансформации деформируемого симплекса вокруг точки экстремума и не используют алгоритм движения в сторону глобального минимума. Самым замечательным в этом методе то, что у симплекса существуют возможности самостоятельно выполнять определенные функции: Где xc - центр тяжести (см. Рисунок 1). Следующим шагом необходимо провести расчет аргументов целевой функции во всех вершинах отраженного симплекса. После этого, мы получим полную информацию о том, как симплекс будет вести себя в пространстве, а значит и информацию о поведении функции. Алгоритм Нелдера – Мида так же использует эти функции работы с симплексом по следующим формулам: Функция отражения через центр тяжести симплекса высчитывается по следующему выражению: Данное отражение выполняется строго в сторону точки экстремума и только через центр тяжести (см. Рисунок 2). Функция сжатия вовнутрь симплекса высчитывается по следующему выражению: Для того, чтобы провести сжатие, необходимо определить точку с наименьшим значением (см. Рисунок 3). Функция отражения со сжатием симплекса высчитывается по следующему выражению: Для того, чтобы провести отражение со сжатием (см. Рисунок 4), необходимо помнить работу двух отдельных функций – это отражение через центр тяжести и сжатие симплекса к наименьшему значению. Функция отражения с растяжением симплекса (см. Рисунок 5) происходит с использованием двух функций – это отражение через центр тяжести и растяжение через наибольшее значение. Чтобы продемонстрировать работу метода Нелдера – Мида, необходимо обратиться к блок схеме алгоритма (см. Рисунок 6). Рисунок 6 - Первая часть метода Нелдера - Мида.
После построения симплекса необходимо произвести расчет всех значений целевой функции. Как и было описано выше про поиск экстремума с помощью симплекса, необходимо рассчитать функцию симплекса f(x) во всех его точках. Далее производим сортировку, где базовая точка будет находиться: Теперь, когда базовая точка рассчитана, а также и все остальные отсортированы в списке, мы производим проверку условия достижимости по ранее заданной нами точности: Как только данное условие станет истинным, тогда точка x(0) симплекса будет считаться искомой точкой экстремума. В другом случае, мы переходим на следующий шаг, где нужно определить новое значение центра тяжести по формуле: Если данное условие выполняется, тогда точка x(0) будет являться точкой минимума, в противном случае, необходимо перейти на следующий шаг в котором необходимо произвести поиск наименьшего аргумента функции: Из функции необходимо достать самую минимальное значение аргумента для того, что перейти к следующему шагу выполнения алгоритма. Иногда случается проблема того, что несколько аргументов сразу имеют одинаковое значение, вычисляемое из функции. Решением такой проблемы может стать повторное определение значения аргумента вплоть до десятитысячных. Вычисленное из предыдущей функции значение необходимо подставить в условие fmin < f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек. Статистика показала, что в работе данного алгоритма существует одна из наиболее распространенных проблем – это вырождение деформируемого симплекса. Это происходит, когда каждый раз, когда несколько вершин симплекса попадают в одно пространство, размерность которого не удовлетворяет поставленной задачи. P.S. Текст полностью мой. Надеюсь кому-нибудь данная информация будет полезной. Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей. Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .
Метод градиентного спуска оказывается очень медленным при движении по оврагу, причём при увеличении числа переменных целевой функции такое поведение метода становится типичным. Для борьбы с этим явлением используется, суть которого очень проста. Сделав два шага градиентного спуска и получив три точки, третий шаг следует сделать в направлении вектора, соединяющего первую и третью точку, вдоль дна оврага. Для функций, близких к квадратичным, эффективным является метод сопряжённых градиентов . Метод градиентного спуска с некоторой модификацией широко применяется для обучения перцептрона и в теории искусственных нейронных сетей известен как метод обратного распространения ошибки . При обучении нейросети типа «персептрон» требуется изменять весовые коэффициенты сети так, чтобы минимизировать среднюю ошибку на выходе нейронной сети при подаче на вход последовательности обучающих входных данных. Формально, чтобы сделать всего один шаг по методу градиентного спуска (сделать всего одно изменение параметров сети), необходимо подать на вход сети последовательно абсолютно весь набор обучающих данных, для каждого объекта обучающих данных вычислить ошибку и рассчитать необходимую коррекцию коэффициентов сети (но не делать эту коррекцию), и уже после подачи всех данных рассчитать сумму в корректировке каждого коэффициента сети (сумма градиентов) и произвести коррекцию коэффициентов «на один шаг». Очевидно, что при большом наборе обучающих данных алгоритм будет работать крайне медленно, поэтому на практике часто производят корректировку коэффициентов сети после каждого элемента обучения, где значение градиента аппроксимируются градиентом функции стоимости, вычисленном только на одном элементе обучения. Такой метод называют стохастическим градиентным спуском
или оперативным градиентным спуском
. Стохастический градиентный спуск является одной из форм стохастического приближения. Теория стохастических приближений даёт условия сходимости метода стохастического градиентного спуска. В
основе метода лежит следующая итерационная
модификация формулы x k +1
= x k
+ a
k
s(x k), x k+1
= x k
- a
k
Ñ
f(x k),
где a
- заданный положительный коэффициент; Ñ
f(x k)
- градиент целевой функции первого
порядка. Недостатки: необходимость
выбора подходящего значения ; медленная
сходимость к точке минимума ввиду
малости f(x k)
в окрестности этой точки. Свободен
от первого недостатка простейшего
градиентного метода, т.к. a k
вычисляется
путем решения задачи минимизации Ñ
f(x k)
вдоль направления Ñ
f(x k)
с помощью одного из методов одномерной
оптимизации x k+1
= x k
- a
k
Ñ
f(x k). Данный
метод иногда называют методом Коши. Алгоритм
характеризуется низкой скоростью
сходимости при решении практических
задач. Это объясняется тем, что изменения
переменных непосредственно зависит от
величины градиента, которая стремится
к нулю в окрестности точки минимума и
отсутствует механизм ускорения на
последних итерациях. Поэтому, учитывая
устойчивость алгоритма, метод наискорейшего
спуска часто используется как начальная
процедура поиска решения (из точек,
расположенных на значительных расстояниях
от точки минимума). Общая
задача нелинейного программирования
без ограничений сводится к следующему:
минимизировать f(x),
x
E n ,
где f(x)
является
целевой функцией. При решении этой
задачи мы используем методы минимизации,
которые приводят к стационарной точке
f(x),
определяемой
уравнением f(x *)=0.
Метод сопряженных направлений относится
к методам минимизации без ограничений,
использующим производные. Задача:
минимизировать f(x),
x
E n ,
где f(x)
является
целевой функцией n
независимых
переменных. Важной особенностью является
быстрая сходимость за счет того, что
при выборе направления используется
матрица Гессе, которая описывает область
топологии поверхности отклика. В
частности, если целевая функция
квадратичная, то можно получить точку
минимума не более чем за количество
шагов, равное размерности задачи. Для
применения метода на практике его
необходимо дополнить процедурами
проверки сходимости и линейной
независимости системы направлений.
Методы
второго порядка Последовательное
применение схемы квадратичной
аппроксимации приводит к реализации
оптимизационного метода Ньютона по
формуле x k +1
= x k
- Ñ 2
f(x k -1)
Ñ
f(x k). Недостатком
метода Ньютона является его недостаточная
надежность при оптимизации не квадратичных
целевых функций. Поэтому его часто
модифицируют: x k +1
= x k
- a k
Ñ 2
f(x k -1)
Ñ
f(x k),
где a k
- параметр, выбираемый таким образом,
чтобы f(x k+1)
min. Дана
некоторая функция f(х)
на открытом интервале (а, в) изменения
аргумента х. Предполагаем, что exst
внутри этого интервала существует
(нужно сказать, что в общем случае
математически заранее это утверждать
не могут; однако в технических приложениях
очень часто наличие exst
внутри некоторого интервала изменения
интервала изменения аргумента может
быть предсказано из физических
соображений). Определение
exst.
Функция f(x)
заданная на интервале (а, в) имеет в точке
x *
max(min),
если эту точку можно окружить таким
интервалом (x * -ε,
x * +ε),
содержащимся
в интервале (а, в), что для всех ее точек
х, принадлежащих интервалу (x * -ε,
x * +ε),
выполняется
неравенство: f(x)
≤ f(x *)
→ для max f(x)
≥ f(x *)
→ для min Это
определение не накладывает никаких
ограничений на класс функций f(x),
что, конечно, очень ценно. Если
ограничится для функций f(x),
достаточно распространенным, но все же
более узким классом гладких функций
(под гладкими функциями мы будем понимать
такие функции, которые непрерывны вместе
со своими производными на интервале
изменения аргумента), то можно
воспользоваться теоремой Ферма, которая
дает необходимые условия существования
exst. Теорема
Ферма. Пусть функция f(x)
определена в некотором интервале (а, в)
и в точке "с" этого интервала
принимает наибольшее (наименьшее)
значение. Если существует в этой точке
двухсторонняя конечная производная
,
то существования необходимоexst
. Примечание.
Двухсторонняя производная характеризуется
свойством
иными словами, речь идет о том, что в
точке "с" производная в пределе
одна и та же при подходе к точке "с"
слева и справа, т.е.f(x)
– гладкая функция. * В
случае
имеет местоmin,
а при
→max.
Наконец, если при х=х 0
,
то использование 2-ой производной не
помогает и нужно воспользоваться,
например, определением exst. При
решении задачи I
необходимые условия exst
(т.е. теорема Ферма) используется очень
часто. Если
уравнение exst
имеет вещественные корни, то точки,
соответствующие этим корням, являются
подозрительными наexst
(но не обязательно самыми экстремумами,
ибо имеем дело с необходимыми, а не с
необходимыми и достаточными условиями).
Так, например, в точке перегиба Х п
имеет
место
,
однако, как известно, это не экстремум. Заметим
ещё, что: из
необходимых условий нельзя сказать,
какой вид экстремума найден max
или min:
для определения этого нужны дополнительные
исследования; из
необходимых условий нельзя определить,
глобальный это экстремум или локальный. Поэтому,
когда находят точки подозрительные на
exst,
их дополнительно исследуют, например,
на основе определения exst
или 2-ой производной. Градиентные методы Градиентные методы безусловной оптимизации используют только первые производные целевой функции и являются методами линейной аппроксимации на каждом шаге, т.е. целевая функция на каждом шаге заменяется касательной гиперплоскостью к ее графику в текущей точке. На 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(метод Ньютона). Если же целевая функция имеет общий вид, то метод ДФП эффективен за счет использования сопряженных направлений.
max,
7, x 1
0,
10, x 2
0.
(min – «-»;max– «+»).
(k) (z (k) –x (k)),
где
(k) – шаг, коэффициент, 0 
1.
(k) выбирается так, чтобы значение функции
F(x) было max (min) в точке х (k +1) .
Для этого решают уравнение
и
выбирают наименьший (наибольший) из
корней, но 0 
1.
или grad F(x (k +1))
= 0, то решение найдено;
max,
4, x 1
0,
2, x 2
0.
max(min),
b i , i
=
, x j
0, j =
.
,
-
некоторые положительные Const.
,
тем быстрее находится решение, однако,
точность снижается;
и увеличивают их на последующих шагах.
и
.
.
Допустимой
области, проверяют:
-
решение найдено, если нет – переход к
п. 2.
Допустимой области, задают новое значение
и
переходят к п. 4.
max,
8, x 1
0, x 2
0.
Для демонстрации хода работы данного метода, для начала необходимо взять функцию z = f(x1, x2,…, xn) и выбрать любую точку M0(x10, x20,…, xn0) в n пространстве, которая зависит от числа характеристик функции. Следующим шагом идет фиксация всех точек функции в константу, кроме самой первой. Это делается для того, чтобы поиск многомерной оптимизации свести к решению поиска на определенном отрезке задачу одномерной оптимизации, то есть поиска аргумента x1.
Для нахождения значения данной переменной, необходимо производить спуск по этой координате до новой точки M1(x11, x21,…, xn1). Далее функция дифференцируется и тогда мы можем найти значение новой следующий точки с помощью данного выражения:
Рисунок 1 – Отмена выполнения покоординатного спуска
Отсюда можно сделать вывод, что функция z = f(x1, x2,…, xn) выпукла и дифференцируема в пространстве, а каждая найденная предельная точка в последовательности M0(x10, x20,…, xn0) будет являться точкой глобального минимума (см. Рисунок 2) данной функции по методу покоординатного спуска. 
Рисунок 2 – Локальные точки минимума на оси координат
Изначально необходимо ввести несколько параметров: точность Эпсилон, которая должна быть строго положительной, стартовая точка x1 с которой мы начнем выполнение нашего алгоритма и установить Лямбда j;
Следующим шагом будет взять первую стартовую точку x1, после чего происходит решение обычного одномерного уравнения с одной переменной и формула для нахождения минимума будет, где k = 1, j=1:
Теперь после вычисления точки экстремума, необходимо проверить количество аргументов в функции и если j будет меньше n, тогда необходимо повторить предыдущий шаг и переопределить аргумент j = j + 1. При всех иных случаях, переходим к следующему шагу.
Теперь необходимо переопределить переменную x по формуле x (k + 1) = y (n + 1) и попытаться выполнить сходимость функции в заданной точности по выражению:
Теперь от данного выражения зависит нахождение точки экстремума. Если данное выражение истинно, тогда вычисление точки экстремума сводится к x*= xk + 1. Но часто необходимо выполнить дополнительные итерации, зависящие от точности, поэтому значения аргументов будет переопределено y(1) = x(k + 1), а значения индексов j =1, k = k + 1.
Рисунок 3 – Блок схема метода покоординатного спуска
Существуют овражные функции, в которых существуют впадины. Алгоритм, попав в одну из таких впадин, уже не может выбраться и точку минимума он обнаружит уже там. Так же большое число последовательных использований одного и того же метода одномерной оптимизации, может сильно отразиться на слабых вычислительных машинах. Мало того, что сходимость в данной функции очень медленная, поскольку необходимо вычислить все переменные и зачастую высокая заданная точность увеличивает в разы время решения задачи, так и главным недостатком данного алгоритма – ограниченная применимость.
Проводя исследование различных алгоритмов решения задач оптимизации, нельзя не отметить, что огромную роль играет качество данных алгоритмов. Так же не стоит забывать таких важных характеристик, как время и стабильность выполнения, способность находить наилучшие значения, минимизирующие или максимизирующие целевую функцию, простота реализации решения практических задач. Метод покоординатного спуска прост в использовании, но в задачах многомерной оптимизации, чаще всего, необходимо выполнять комплексные вычисления, а не разбиение целой задачи на подзадачи.
Данный симплекс является регулярным, а представляется как многогранник с равностоящими вершинами симплекса в N-мерном пространстве. В различных пространствах, симплекс отображается в R2-равносторонний треугольник, а в R3 - правильный тетраэдр.
Как упоминалось выше, алгоритм является развитием метода симплексов Спендли, Хекста и Химсворта, но, в отличие от последнего, допускает использование неправильных симплексов. Чаще всего, под симплексом подразумевается выпуклый многогранник с числом вершин N+1, где N – количество параметров модели в n -мерном пространстве.
Для того, чтобы начать пользоваться данным методом, необходимо определиться с базовой вершиной всех имеющихся множества координат с помощью выражения:
Отражение через центр тяжести, отражение со сжатием или растяжением;
Растяжение;
Сжатие.
Преимуществу среди этих свойств отдают отражению, поскольку данный параметр является наиболее опционально – функциональным. От любой выбранной вершины возможно сделать отражение относительно центра тяжести симплекса по выражению:.
Рисунок 1 – Отражение через центр тяжести
Для того чтобы совершить поиск точки минимума или максимума целевой функции с помощью методов использующих симплексы, необходимо придерживаться следующей последовательности:
На каждом шаге строиться симплекс, в каждой точке которого, необходимо произвести расчет всех его вершин, после чего отсортировать полученные результаты по возрастанию;
Следующий шаг – это отражение. Необходимо провести попытку получить значения нового симплекса, а путём отражения, у нас получиться избавиться от нежелательных значений, которые стараются двигать симплекс не в сторону глобального минимума;
Чтобы получить значения нового симплекса, из полученных отсортированных результатов, мы берем две вершины с наихудшими значениями. Возможны такие случаи, что сразу подобрать подходящие значения не удастся, тогда придется вернуться к первому шагу и произвести сжатие симплекса к точке с самым наименьшим значением;
Окончанием поиска точки экстремума является центр тяжести, при условии, что значение разности между функциями имеет наименьшие значения в точках симплекса.
Рисунок 2 – Отражение симплекса происходит через центр тяжести
Рисунок 3 – Сжатие симплекса происходит к наименьшему аргументу.
Рисунок 4 - Отражение со сжатие
Рисунок 5 - Отражение с растяжением.
Первостепенно, как и в предыдущих примерах, нужно задать параметр искаженности ε, которая должна быть строго больше нуля, а также задать необходмые параметры для вычисления α, β и a. Это нужно будет для вычисления функции f(x0), а также для построения самого симплекса. 
После повторного вычисления минимального аргумента, необходимо заново сохранить новые полученные значения на n позициях аргументов.
Рисунок 7 - Вторая часть метода Нелдера - Мида.
Исследования данного алгоритма показывают, что методы с нерегулярными симплексами (см. Рисунок 8) еще достаточно слабо изучены, но это не мешает им отлично справляться с поставленными задачами.
Более глубокие тесты показывают, что экспериментальным образом можно подобрать наиболее подходящие для задачи параметры функций растяжения, сжатия и отражения, но можно пользоваться общепринятыми параметрами этих функций α = 1/2, β = 2, γ = 2 или α = 1/4, β = 5/2, γ = 2. Поэтому, перед тем как отбрасывать данный метод для решения поставленной задачи, необходимо понимать, что для каждого нового поиска безусловного экстремума, нужно пристально наблюдать за поведением симплекса во время его работы и отмечать нестандартные решения метода.
Рисунок 8 - Процесс нахождения минимума.
Таким образом, размерность во время работы и заданная размерность закидывают несколько вершин симплекса в одну прямую, запуская метод в бесконечный цикл. Алгоритм в данной модификации еще не оснащен способом выйти из такого положения и сместить одну вершину в сторону, поэтому приходится создать новый симплекс с новыми параметрами, чтобы такого в дальнейшем не происходило.
Еще одной особенностью обладает данный метод – это некорректной работой при шести и более вершинах симплекса. Однако, при модификации данного метода, можно избавиться от этой проблемы и даже не потерять при этом скорости выполнения, но значение выделяемой памяти заметно повысится. Данный метод можно считать циклическим, поскольку он полностью основан на циклах, поэтому и замечается некорректная работа при большом количестве вершин.
Алгоритм Нелдера – Мида по праву можно считать одним из наилучших методов нахождения точки экстремума с помощью симплекса и отлично подходит для использования его в различные рода инженерных и экономических задачах. Даже не смотря на цикличность, количество памяти он использует очень малое количество, по сравнение с тем же методом покоординатного спуска, а для нахождения самого экстремума требуется высчитывать только значения центра тяжести и функции. Небольшое, но достаточное, количество комплексных параметров дают этому методу широкое использование в сложных математических и актуальных производственных задачах.
Симплексные алгоритмы – это край, горизонты которого еще мы не скоро раскроем, но уже сейчас они значительно упрощают нашу жизнь своей визуальной составляющей.Описание
[
|
]
Усовершенствования
[
|
]
Применение в искусственных нейронных сетях
[
|
]
Ссылки
[
|
]
Литература
[
|
]
Метод наискорейшего спуска
Метод сопряженных направлений
Метод Ньютона
2. Нахождение экстремума функции без ограничения
