Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту -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) находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции.
В задаче безусловной оптимизации отсутствуют ограничения.
Напомним, что градиентом многомерной функции называют вектор, который аналитически выражается геометрической суммой частных производных
Градиент скалярной функции 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.
Метод сопряженных направлений является одним из наиболее эффективных в решении задач минимизации. Метод в совокупности с одномерным поиском часто практически используется в САПР. Однако следует отметить, что он чувствителен к ошибкам, возникающим в процессе счета.
Недостатки градиентных методов
В задачах с большим числом переменных трудно или невозможно получить производные в виде аналитических функций.
При вычислении производных по разностным схемам возникающая при этом ошибка, особенно в окрестностях экстремума, ограничивает возможности такой аппроксимации.
Вкину немного своего экспириенса:)
Метод покоординатного спуска
Идея данного метода в том, что поиск происходит в направлении покоординатного спуска во время новой итерации. Спуск осуществляется постепенно по каждой координате. Количество координат напрямую зависит от количества переменных.
Для демонстрации хода работы данного метода, для начала необходимо взять функцию 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. Текст полностью мой. Надеюсь кому-нибудь данная информация будет полезной.
Лекция 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 Метод релаксации
Алгоритм метода заключается в отыскании осевого направления, вдоль которого целевая функция уменьшается наиболее сильно (при поиске минимума). Рассмотрим задачу безусловной оптимизации Для определения осевого направления в начальной точке поиска из области определяются производные , , по всем независимым переменным. Осевому направлению соответствует наибольшая по модулю производная . Пусть – осевое направление, т.е. Если знак производной отрицательный, функция убывает в направлении оси, если положительный – в обратном направлении: В точке вычисляют . По направлению убывания функции производится один шаг, определяется и в случае улучшения критерия шаги продолжаются до тех пор, пока не будет найдено минимальное значение по выбранному направлению. В этой точке вновь определяются производные по всем переменным, за исключением тех, по которой осуществляется спуск. Снова находится осевое направление наиболее быстрого убывания , по которому производятся дальнейшие шаги и т.д. Эту процедуру повторяют до тех пор, пока не достигается оптимальная точка, при движении из которой по любому осевому направлению дальнейшего убывания не происходит. На практике критерием окончания поиска служит условие которое при превращается в точное условие равенства нулю производных в точке экстремума. Естественно условие (3.7) может быть использовано только в том случае, если оптимум лежит внутри допустимой области изменения независимых переменных . Если же оптимум попадает на границу области , критерий типа (3.7) непригоден и вместо него следует применять положительности всех производных по допустимым осевым направлениям. Алгоритм спуска для выбранного осевого направления может быть записан так где -значение варьируемой переменной на каждом шаге спуска; Величина k+1 шага, которая может изменяться в зависимости от номера шага: – функция знака z; Вектор точки, в которой последний раз производилось вычисление производных ; Знак “+” в алгоритме (3.8) принимается при поиске max I, а знак “-” – при поиске min I.Чем меньше шаг h., тем больше количество вычислений на пути движения к оптимуму. Но при слишком большой величине h вблизи оптимума может возникнуть зацикливание процесса поиска. Вблизи оптимума необходимо, чтобы выполнялось условие h Простейший алгоритм изменения шага h состоит в следующем. В начале спуска задается шаг , равный например, 10% от диапазона d; изменения с этим шагом производится спуск по выбранному направлению до тез пор, пока выполняется условие для двух последующих вычислений При нарушении условия на каком-либо шаге направление спуска на оси изменяется на обратное и спуск продолжается из последней точки с уменьшенной вдвое величиной шага. Формальная запись этого алгоритма следующая: В результате использования такой стратегии ша спуска будет уменьшатся в районе оптимума по данному направлению и поиск по направлению можно прекратить, когда станет меньше E. Затем отыскивается новое осевое направление начальный шаг для дальнейшего спуска, обычно меньший пройденного вдоль предыдущего осевого направления. Характер движения в оптимуме в данном методе показан на рисунке 3.4. Рисунок 3.5 – Траектория движения к оптимуму в методе релаксации Улучшение алгоритма поиска по данному методу может быть достигнуто путем применения методов однопараметрической оптимизации. При этом может быть предложена схема решения задачи: Шаг 1. – осевое направление, Шаг 2. – новое осевое направление; Метод градиента
В этом методе используется градиент функции . Градиентом функции в точке Рисунок 3.6 – Градиент функции Направление градиента – это направление наиболее быстрого возрастания функции (наиболее крутого “склона” поверхности отклика). Противоположное ему направление (направление антиградиента) – это направление наибыстрейшего убывания (направление наискорейшего “спуска” величин ). Проекция градиента на плоскость переменных перпендикулярна касательной к линии уровня , т.е. градиент ортогонален к линиям постоянного уровня целевой функции (рис. 3.6). Рисунок 3.7 – Траектория движения к оптимуму в методе градиента В отличие от метода релаксации в методе градиента шаги совершаются в направлении наибыстрейшего уменьшения (увеличения) функции . Поиск оптимума производится в два этапа. На первом этапе находятся значения частных производных по всем переменным , которые определяют направление градиента в рассматриваемой точке. На втором этапе осуществляется шаг в направлении градиента при поиске максимума или в противоположном направлении – при поиске минимума. Если аналитическое выражение неизвестно, то направление градиента определяется поиском на объекте пробных движений. Пусть начальная точка. Дается приращение величина , при этом . Определяют приращение и производную Аналогично определяют производные по остальным переменным. После нахождения составляющих градиента пробные движения прекращаются и начинаются рабочие шаги по выбранному направлению. Причем величина шага тем больше, чем больше абсолютная величина вектора . При выполнении шага одновременно изменяются значения всех независимых переменных. Каждая из них получает приращение, пропорциональное соответствующей составляющей градиента или в векторной форме где – положительная константа; “+” – при поиске max I; “-” – при поиске min I. Алгоритм градиентного поиска при нормировании градиента (деление на модуль) применяется в виде Определяет величину шага по направлению градиента. Алгоритм (3.10) обладает тем достоинством, что при приближении к оптимуму длина шага автоматически уменьшается. А при алгоритме (3.12) стратегию изменения можно строить независимо от абсолютной величины коэффициента. В методе градиента каждый разделяется один рабочий шаг, после которого вновь вычисляются производные, определяется новое направление градиента и процесс поиска продолжается (рис. 3.5). Если размер шага выбран слишком малым, то движение к оптимуму будет слишком долгим из-за необходимости вычисления в очень многих точках. Если же шаг выбран слишком большим, в район оптимума может возникнуть зацикливание. Процесс поиска продолжается до тех пор, пока , , не станут близки к нулю или пока не будет достигнута граница области задания переменных. В алгоритме с автоматическим уточнением шага величину уточняют так, чтобы изменение направления градиента в соседних точках и
Критерии окончания поиска оптимума: где Поиск завершается при выполнении одного из условий (3.14) – (3.17). Недостатком градиентного поиска (так же и рассмотренных выше методов) является то, что при его использовании можно обнаружить только локальный экстремум функции . Для отыскания других локальных экстремумов необходимо производить поиск из других начальных точек.
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.
.
(3.8)
(3.9)
; , если ;
называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам (рис. 6.5)
.
, (3.10)
, (3.11)
; (3.12)
(3.13)
; (3.16)
; (3.17)
– норма вектора.
