Когда используют градиентный метод. Градиентный спуск. Проективный алгоритм Ньютона-Рафсона

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) для каждой точки траектории движения вдоль градиента, начиная с исходной.

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

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

Рис. 4.11.

Рис. 4.12.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В координатной форме этот процесс записывается следующим образом:

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

Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий.

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

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

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

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции /(х) убывает. Поэтому на каждой итерации необходимо решать задачу одномерной минимизации по я функции ф(я) =/(х (/г) - - agrad^x^))). Алгоритм метода наискорейшего спуска состоит в следующем.

• 1. Зададим координаты начальной точки х^° точность приближенного решения г. Положим k = 0.
• 2. В точке х (/г) вычислим значение градиента grad(/(x (^)).
• 3. Определим величину шага а^ путем одномерной минимизации по я функции ср(я).
• 4. Определим новое приближение к точке минимума х (* +1 > по формуле (10.4).
• 5. Проверим условия останова итерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае полагаем k k + 1 и переходим к п. 2.

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

минимума функции - = 0. Вычислив производную

сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

Задачу минимизации функции ф(я) можно свести к задаче вычисления корня функции одной переменной g(a) =

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

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

Вкину немного своего экспириенса:)

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

Идея данного метода в том, что поиск происходит в направлении покоординатного спуска во время новой итерации. Спуск осуществляется постепенно по каждой координате. Количество координат напрямую зависит от количества переменных.
Для демонстрации хода работы данного метода, для начала необходимо взять функцию z = f(x1, x2,…, xn) и выбрать любую точку M0(x10, x20,…, xn0) в n пространстве, которая зависит от числа характеристик функции. Следующим шагом идет фиксация всех точек функции в константу, кроме самой первой. Это делается для того, чтобы поиск многомерной оптимизации свести к решению поиска на определенном отрезке задачу одномерной оптимизации, то есть поиска аргумента x1.
Для нахождения значения данной переменной, необходимо производить спуск по этой координате до новой точки M1(x11, x21,…, xn1). Далее функция дифференцируется и тогда мы можем найти значение новой следующий точки с помощью данного выражения:

После нахождения значения переменной, необходимо повторить итерацию с фиксацией всех аргументов кроме x2 и начать производить спуск по новой координате до следующей новой точке M2(x11,x21,x30…,xn0). Теперь значение новой точки будет происходить по выражению:

И снова итерация с фиксацией будет повторяться до тех пор, пока все аргументы от xi до xn не закончатся. При последней итерации, мы последовательно пройдем по всем возможным координатам, в которых уже найдем локальные минимумы, поэтому целевая функция на последний координате дойдет до глобального минимума. Одним из преимуществ данного метода в том, что в любой момент времени есть возможность прервать спуск и последняя найденная точка будет являться точкой минимума. Это бывает полезно, когда метод уходит в бесконечный цикл и результатом этого поиска можно считать последнюю найденную координату. Однако, целевая установка поиска глобального минимума в области может быть так и не достигнута из-за того, что мы прервали поиск минимума (см. Рисунок 1).

Рисунок 1 – Отмена выполнения покоординатного спуска

Исследование данного метода показали, что каждая найденная вычисляемая точка в пространстве является точкой глобального минимума заданной функции, а функция z = f(x1, x2,…, xn) является выпуклой и дифференцируемой.
Отсюда можно сделать вывод, что функция z = f(x1, x2,…, xn) выпукла и дифференцируема в пространстве, а каждая найденная предельная точка в последовательности M0(x10, x20,…, xn0) будет являться точкой глобального минимума (см. Рисунок 2) данной функции по методу покоординатного спуска.

Рисунок 2 – Локальные точки минимума на оси координат

Можно сделать вывод о том, что данный алгоритм отлично справляется с простыми задачами многомерной оптимизации, путём последовательно решения n количества задач одномерной оптимизации, например, методом золотого сечения.

Ход выполнения метода покоординатного спуска происходит по алгоритму описанного в блок схеме (см. Рисунок 3). Итерации выполнения данного метода:
Изначально необходимо ввести несколько параметров: точность Эпсилон, которая должна быть строго положительной, стартовая точка 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 -мерном пространстве.
Для того, чтобы начать пользоваться данным методом, необходимо определиться с базовой вершиной всех имеющихся множества координат с помощью выражения:

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

Где xc - центр тяжести (см. Рисунок 1).

Рисунок 1 – Отражение через центр тяжести

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

Алгоритм Нелдера – Мида так же использует эти функции работы с симплексом по следующим формулам:

Функция отражения через центр тяжести симплекса высчитывается по следующему выражению:

Данное отражение выполняется строго в сторону точки экстремума и только через центр тяжести (см. Рисунок 2).

Рисунок 2 – Отражение симплекса происходит через центр тяжести

Функция сжатия вовнутрь симплекса высчитывается по следующему выражению:

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

Рисунок 3 – Сжатие симплекса происходит к наименьшему аргументу.

Функция отражения со сжатием симплекса высчитывается по следующему выражению:

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

Рисунок 4 - Отражение со сжатие

Функция отражения с растяжением симплекса (см. Рисунок 5) происходит с использованием двух функций – это отражение через центр тяжести и растяжение через наибольшее значение.

Рисунок 5 - Отражение с растяжением.

Чтобы продемонстрировать работу метода Нелдера – Мида, необходимо обратиться к блок схеме алгоритма (см. Рисунок 6).
Первостепенно, как и в предыдущих примерах, нужно задать параметр искаженности ε, которая должна быть строго больше нуля, а также задать необходмые параметры для вычисления α, β и a. Это нужно будет для вычисления функции f(x0), а также для построения самого симплекса.

Рисунок 6 - Первая часть метода Нелдера - Мида.

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

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

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

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

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

Рисунок 7 - Вторая часть метода Нелдера - Мида.

Вычисленное из предыдущей функции значение необходимо подставить в условие fmin < f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Исследования данного алгоритма показывают, что методы с нерегулярными симплексами (см. Рисунок 8) еще достаточно слабо изучены, но это не мешает им отлично справляться с поставленными задачами.
Более глубокие тесты показывают, что экспериментальным образом можно подобрать наиболее подходящие для задачи параметры функций растяжения, сжатия и отражения, но можно пользоваться общепринятыми параметрами этих функций α = 1/2, β = 2, γ = 2 или α = 1/4, β = 5/2, γ = 2. Поэтому, перед тем как отбрасывать данный метод для решения поставленной задачи, необходимо понимать, что для каждого нового поиска безусловного экстремума, нужно пристально наблюдать за поведением симплекса во время его работы и отмечать нестандартные решения метода.

Рисунок 8 - Процесс нахождения минимума.

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

P.S. Текст полностью мой. Надеюсь кому-нибудь данная информация будет полезной.

Лекция № 8

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

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

Будем рассматривать задачу максимизации нелинейной дифференцируемой функции f (x ). Суть градиентного поиска точки максимума х * весьма проста: надо взять произвольную точку х 0 и с помощью градиента , вычисленного в этой точке, определить направление, в котором f (х ) возрастает с наибольшей скоростью (рис. 7.4),

а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку x i . Потом снова определить наилучшее направление для перехода в очередную точку х 2 и т. д. На рис. 7.4 поисковая траектория представляет собой ломаную х 0 , x 1 , х 2 ... Таким образом, надо построить последовательность точек х 0 , x 1 , х 2 ,...,x k , ... так, чтобы она сходилась к точке максимума х *, т. е. для точек последовательности выполнялись условия

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

Движение из точки х k в новую точку x k+1 осуществляется по прямой, проходящей через точку х k и имеющей уравнение

(7.29)

где λ k - числовой параметр, от которого зависит величина шага. Как только значение параметра в уравнении (7.29) выбрано: λ k =λ k 0 , так становится определенной очередная точка на поисковой ломаной.

Градиентные методы отличаются друг от друга способом выбора величины шага - значения λ k 0 параметра λ k . Можно, например, двигаться из точки в точку с постоянным шагом λ k = λ, т. е. при любом k

Если при этом окажется, что , то следует возвратиться в точку и уменьшить значение параметра, например до λ /2.

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

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

Если целевая функция f (x ) вогнутая (выпуклая), то необходимым и достаточным условием оптимальности точки х * является равенство нулю градиента функции в этой точке.

Распространенным является вариант градиентного поиска, называемый методом наискорейшего подъема. Суть его в следующем. После определения градиента в точке х к движение вдоль прямой производится до точки х к+ 1 , в которой достигается максимальное значение функции f (х ) в направлении градиента . Затем в этой точке вновь определяется градиент, и движение совершается по прямой в направлении нового градиента до точки х к+ 2 , в которой достигается максимальное в этом направлении значение f (x ). Движение продолжается до тех пор, пока не будет достигнута точка х *, соответствующая наибольшему значению целевой функции f (x ). На рис. 7.5 приведена схема движения к оптимальной точке х * методом наискорейшего подъема. В данном случае направление градиента в точке х k является касательным к линии уровня поверхности f (х ) в точке х к+ 1 , следовательно, градиент в точкех к+ 1 ортогонален градиенту (сравните с рис. 7.4).

Перемещение из точки х k в точку сопровождается возрастанием функции f (x ) на величину

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

(7.31)

Найдем выражение для производной, дифференцируя равенство (7.30) по как сложную функцию:

Подставляя этот результат в равенство (7.31), получаем

Это равенство имеет простое геометрическое истолкование: градиент в очередной точке х к+ 1 , ортогонален градиенту в предыдущей точке х к .

построены линии уровня этой поверхности. С этой целью уравнение приведено к виду (x 1 -1) 2 +(x 2 -2) 2 =5-0,5f , из которого ясно, что линиями пересечения параболоида с плоскостями, параллельными плоскости x 1 Оx 2 (линиями уровня), являются окружности радиусом . При f =-150, -100, -50 их радиусы равны соответственно , а общий центр находится в точке (1; 2). Находим градиент данной функции:

I шаг . Вычисляем:

На рис. 7.6 с началом в точке х 0 =(5; 10) построен вектор 1/16, указывающий направление наискорейшего возрастания функции в точке х 0 . На этом направлении расположена следующая точка . В этой точке .

Используя условие (7.32), получаем

или 1-4=0, откуда =1/4. Так как , то найденное значение является точкой максимума . Находим x 1 =(5-16/4; 10-32/4)=(1; 2).

II шаг . Начальная точка для второго шага x 1 =(1; 2). Вычисляем =(-4∙1 +4; -4∙2+8)=(0; 0). Следовательно, х 1 =(1; 2) является стационарной точкой. Но поскольку данная функция вогнутая, то в найденной точке (1; 2) достигается глобальный максимум.

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

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

(7.34)

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

Начнем с геометрической иллюстрации процесса решения задачи (рис. 7.7). Пусть начальная точка х 0 расположена внутри допустимой области. Из точки х 0 можно двигаться в направлении градиента , пока f (x ) не достигнет максимума. В нашем случае f (x ) все время возрастает, поэтому остановиться надо в точке х , на граничной прямой. Как видно из рисунка, дальше двигаться в направлении градиента нельзя, так как выйдем из допустимой области. Поэтому надо найти другое направление перемещения, которое, с одной стороны, не выводит из допустимой области, а с другой - обеспечивает наибольшее возрастание f (x ). Такое направление определит вектор , составляющий с вектором наименьший острый угол по сравнению с любым другим вектором, выходящим из точки x i и лежащим в допустимой области. Аналитически такой вектор найдется из условия максимизации скалярного произведения . В данном случае вектор указывающий наивыгоднейшее направление, совпадает с граничной прямой.

Таким образом, на следующем шаге двигаться надо по граничной прямой до тех пор, пока возрастает f (x ); в нашем случае - до точки х 2 . Из рисунка видно, что далее следует перемещаться в направлении вектора , который находится из условия максимизации скалярного произведения , т. е. по граничной прямой. Движение заканчивается в точке х 3 , поскольку в этой точке завершается оптимизационный поиск, ибо в ней функция f (х ) имеет локальный максимум. Ввиду вогнутости в этой точке f (х ) достигает также глобального максимума в допустимой области. Градиент в точке максимума х 3 =х * составляет тупой угол с любым вектором из допустимой области, проходящим через х 3 , поэтому скалярное произведение будет отрицательным для любого допустимого r k , кроме r 3 , направленного по граничной прямой. Для него скалярное произведение =0, так как и взаимно перпендикулярны (граничная прямая касается линии уровня поверхности f (х ), проходящей через точку максимума х *). Это равенство и служит аналитическим признаком того, что в точке х 3 функция f (x ) достигла максимума.

Рассмотрим теперь аналитическое решение задачи (7.33) - (7.35). Если оптимизационный поиск начинается с точки, лежащей в допустимой области (все ограничения задачи выполняются как строгие неравенства), то перемещаться следует по направлению градиента так, как установлено выше. Однако теперь выбор λ k в уравнении (7.29) усложняется требованием, чтобы очередная точка оставалась в допустимой области. Это означает, что ее координаты должны удовлетворять ограничениям (7.34), (7.35), т. е. должны выполняться неравенства:

(7.36)

Решая систему линейных неравенств (7.36), находим отрезок допустимых значений параметра λ k , при которых точка х k +1 будет принадлежать допустимой области.

Значение λ k * , определяемое в результате решения уравнения (7.32):

При котором f (x ) имеет локальный максимум по λ k в направлении, должно принадлежать отрезку . Если же найденное значение λ k выходит за пределы указанного отрезка, то в качестве λ k * принимается . В этом случае очередная точка поисковой траектории оказывается на граничной гиперплоскости, соответствующей тому неравенству системы (7.36), по которому при решении системы получена правая конечная точка . отрезка допустимых значений параметра λ k .

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

при ограничениях

для тех t , при которых

где .

В результате решения задачи (7.37) - (7.40) будет найден вектор , составляющий с градиентом наименьший острый угол.

Условие (7.39) говорит о том, что точка принадлежит границе допустимой области, а условие (7.38) означает, что перемещение из по вектору будет направлено внутрь допустимой области или по ее границе. Условие нормализации (7.40) необходимо для ограничения величины , так как в противном случае значение целевой функции (7.37) можно сделать сколь угодно большим Известны различные формы условий нормализации, и в зависимости от этого задача (7.37) - (7.40) может быть линейной или нелинейной.

После определения направления находится значение λ k * для следующей точки поисковой траектории. При этом используется необходимое условие экстремума в форме, аналогичной уравнению (7.32), но с заменой на вектор , т. е.

(7.41)

Оптимизационный поиск прекращается, когда достигнута точка x k * , в которой .

Пример 7.5. Максимизировать функцию при ограничениях

Решение. Для наглядного представления процесса оптимизации будем сопровождать его графической иллюстрацией. На рис 7.8 изображено несколько линий уровня данной поверхности и допустимая область ОАВС, в которой следует найти точку х *, доставляющую максимум данной функции (см. пример 7 4).

Начнем оптимизационный поиск, например с точки х 0 =(4, 2,5), лежащей на граничной прямой АВ x 1 +4x 2 =14. При этом f (х 0)=4,55.

Найдем значение градиента

в точке x 0 . Кроме того, и по рисунку видно, что через допустимую область проходят линии уровня с пометками более высокими, чем f (x 0)=4,55. Словом, надо искать направление r 0 =(r 01 , r 02) перемещения в следующую точку x 1 более близкую к оптимальной. С этой целью решаем задачу (7.37) - (7.40) максимизации функции при ограничениях

Поскольку точка х 0 располагается только на одной (первой) граничной прямой (i =1) x 1 +4x 2 =14, то условие (7.38) записывается в форме равенства.

Система ограничительных уравнений этой задачи имеет только два решения (-0,9700; 0,2425) и (0,9700;-0,2425) Непосредственной подстановкой их в функцию T 0 устанавливаем, что максимум Т 0 отличен от нуля и достигается при решении (-0,9700; 0,2425) Таким образом, перемещаться из х 0 нужно по направлению вектора r 0 =(0,9700; 0,2425), т е по граничной прямой ВА.

Для определения координат следующей точки x 1 =(x 11 ; x 12)

(7.42)

необходимо найти значение параметра , при котором функция f (x ) в точке x

откуда =2,0618. При этом =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).

Если продолжить оптимизационный поиск, то при решении очередной вспомогательной задачи (7.37)- (7.40) будет установлено, что Т 1 =, а это говорит о том, что точка x 1 является точкой максимума х* целевой функции в допустимой области. Это же видно и из рисунка в точке x 1 одна из линий уровня касается границы допустимой области. Следовательно, точка x 1 является точкой максимума х*. При этом f max =f (x *)=5,4.

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

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