Размещено на http://www.allbest.ru/

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

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

В краткой форме задачу нелинейного программирования можно записать так:

F (x) > max при условиях g (x) ? b, x ? 0,

где x - вектор искомых переменных; F (x) - целевая функция; g (x) - функция ограничений (непрерывно дифференцируемая); b - вектор констант ограничений (выбор знака ? в первом условии здесь произволен, его всегда можно изменить на обратный).

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

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

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

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

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

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

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

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

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

В этом разделе излагается стратегия градиентных (наискорейшего спуска) методов оптимизации без ограничений; в вычислительном аспекте эти методы используют только первые производные целевой функции. На k-м этапе переход из точки x^(k) в точку x^(k+1) описывается следующим соотношением:

нелинейный алгоритм спуск оптимизация

где

? x^(k) - вектор перехода из точки x^(k) в точку x^(k+1);

- единичный вектор в направлении ? x^(k);

s^(k) - любой вектор в направлении ? x^(k);

- скаляры, определяемые соотношениями:

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

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

Градиент целевой функции f(x) в любой точке х есть вектор в направлении наибольшего локального увеличения f(x). Следовательно, нужно двигаться в направлении, противоположном градиенту f(x), т.е. в направлении наискорейшего спуска, поскольку отрицательный градиент f(x) в точке x^(k) направлен в сторону наибольшего уменьшения f(x) по всем компонентам х и ортогонален линии уровня f(x) в точке x^(k). Введение направления, противоположного нормированному (единичному) градиенту f(x), т.е. направления наискорейшего спуска, определяемого в точке x^(k) по формуле

В (1) дает следующую формулу перехода из x^(k) в x^(k+1);

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

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

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

Рассмотрим сначала случая, когда л выбирается так, чтобы минимизировать f(x) в заданном направлении. При этом на каждом шаге старая информация отбрасывается и заменяется новой информацией, так что никакого ускорения оптимизации осуществить нельзя. Сходимость метода наискорейшего спуска в такой постановке может быть доказана. Можно показать, что для выпуклой целевой функции, имеющие производные до третьего порядка (и для некоторых других функций при еще более слабых ограничениях), этот метод в пределе сходится при k > ?. Тем не менее упомянутое свойство метода наискорейшего спуска не является большим его достоинством на практике, поскольку скорость сходимости может быть слишком медленной, как это оказывалось в многочисленных экспериментах, а также предсказывается теорией.

При определении точки x^(k+1) на основе формулы (3) f(x) может быть формально минимизирована путем вычисления л из уравнения

В качестве конкретного примера предложим, что f(x) - квадратичная функция [имея это в виду подставим в уравнение

вместо (х - x^(k))]. Тогда

что дает следующие выражение для л^(k):

Функцию f(x) можно минимизировать также с помощью одного из методов одногомерного численного поиска.

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

Если f(x) минимизируется в направлении s^(k).

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

Это можно показать следующим образом. Отметим, что если

то градиент f(x) равен

так что

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

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

Общая формула для нахождения значения аргумента x^(k+1) по значению x^(k), найденному на k-м шаге работы алгоритма наискорейшего спуска:

где: s^(k) - вектор единичной длины в направлении, противоположном направлению градиента , определенном в точке x^(k) (далее будет использоваться обозначение );

- норма (например, длина) вектора градиента :

- шаг градиентной процедуры (определяет число векторов единичной длины (если >0 - целое) или долей длины вектора (если дробное), которое укладывается в направлении, противоположном градиенту при совершении (k+1) - го шага).

Геометрическая интерпретация алгоритма наискорейшего спуска: траектория x(k) ортогональна линиям равного уровня минимизируемой функции. Поскольку шаг движения к экстремуму имеет конечную длину, по мере перемещения к точке x^(k+1) ортогональность нарушается. В точке x^(k+1) направление корректируется и снова становится ортогональным к линиям равного уровня.

Размещено на Allbest.ru