Простейший градиентный метод

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

В данном разделе будет рассматриваться задача безусловной оптимизации, т.е. данная задача характеризуется тем, что минимум функции f: R^m ® R ищется на всем пространстве: f(x) ® min, x Î R^m.

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

· методы прямого поиска, основанные на вычислении только значений целевой функции;

· градиентные методы, в которых используются точные значения первых производных f (x);

· методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции f (x).

Методы прямого поиска

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

· относительная простота соответствующих вычислительных процедур, которые быстро реализуются и легко корректируются;

· не требуют явного выражения целевой функции в аналитическом виде;

· может требовать более значительных затрат времени по сравнению с методами, основанными на производных.

Метод поиска по симплексу

Процедура симплексного метода базируется на регулярном симплексе. Регулярный симплекс в N-мерном пространстве представляет собой многогранник, образованный N+1 равностоящими друг от друга точками - вершинами. Так в задаче с двумя переменными симплексом является равносторонний треугольник, с тремя - тетраэдр.

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

Преимущества метода:

· сравнительная простота логической структуры метода и, соответственно, программы для ЭВМ;

· используется сравнительно небольшое число заранее установленных параметров;

· невысокий уровень требований к ЭВМ;

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

Недостатки метода:

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

· алгоритм работает достаточно медленно, т.к. полученная на предыдущих итерациях информация не используется для ускорения поиска;

· не существует простого способа расширения симплекса. Требуется перерасчет значений целевой функции во всех точках образца.

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

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

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

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

Матрица вторых производных Ñ2F(x) – это симметричная квадратная матрица порядка n вторых частных производных функции F(x). Эту матрицу называют матрицей Гессе и обозначают H(x) = Ñ2F(x). Ее элемент, расположенный на пересечении i-й строки и j-го столбца, равен:

Пусть х^Т=[x₁, x₂,…, x_n] – вектор переменных. Для наличия в точке x* локального минимума (максимума) необходимо, чтобы выполнялось равенство ÑF(x*) = и матрица Гессе H(x*) = ѲF(x*) была положительно (отрицательно) полуопределенной, т.е. x^THx ³ ( x^THx £).

Достаточным условием существования минимума (максимума) в точке x* является положительная (отрицательная) определённость матрицы Гессе в этой точке, т.е. x^THx > ( x^THx<).

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой x^k+1 = x^k + a^k s(x^k), где

x^k - текущее приближение к решению x^*;

a^k - параметр, характеризующий длину шага;

s(x^k) - направление поиска в N - мерном пространстве управляемых переменных x_i, i = 1, 2,..., N.

Способ определения a^k и s(x^k) на каждой итерации связан с особенностями применяемого метода. Обычно выбор a^k осуществляется путем решения задачи минимизации f(x) в направлении s(x^k). Поэтому при реализации градиентных методов необходимо использовать эффективные алгоритмы одномерной минимизации.

Простейший градиентный метод

В основе метода лежит следующая итерационная модификация формулы

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) в окрестности этой точки.