Математические методы исследования операций в экономике (стр. 17 из 37)

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

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

Пустьf(x)=f(x₁,x₁,...x_n) —дифференцируемая функция, заданная на Rⁿ, а х^(q) =(x₁^(q),x₂^(q),...,x_n^(q)) — некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) х⁽⁰⁾, не существует, однако по возможности она должна находиться близко от искомого оптимального плана х*. Как уже говорилось выше, если х^(q)— нестационарная точка (т. е. |

f(x^(q))|>0), то при движении в направлении f(x^(q)) функция f(х) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значенияf(x) от шагового множителя λ > 0. полагая х = х^(q) + λ f(x^(q))

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

Чтобы добиться наибольшего из возможных значений f при движении по направлению

f(x^(q)), нужно выбрать такое значение , которое максимизирует функцию φ(λ) (φ( )= max(φ(λ)). Для вычисления , используется необходимое условие экстремума dφ(λ)/dλ =0. Заметим, что если для любого λ>0 dφ( )/dλ> 0, то функция f(х) не ограничена сверху (т. е. не имеет максимума). В противном случае, на основе (2.10) получаем

что, в свою очередь, дает

Если считать, что следующая точка х^(q+1) соответствует оптимальному значению λ=

, то в ней должно выполняться условиеdφ( )/dλ =0, и следует находить из условия f(x^(q+1)) f(x^(q))=0 или

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

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

После того как точка x^(q+1) найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора Δf(x^(q)) должны быть близки к нулю.

Метод дробления шага

Для нахождения шага λ в методе наискорейшего спуска требуется решить уравнение (2.13), которое может оказаться достаточно сложным. Поэтому часто ограничиваются «подбором» такого значения λ, что φ(λ) > φ(0). Для этого задаются некоторым начальным значением λ₁, (например,λ₁=l) и проверяют условие φ(λ₁) >φ(0). Если оно не выполняется, то полагают

λ₂= 1/2 λ₁

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

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

в случае градиентных методов, может быть осуществлен за счет подбора соответствующих начальных приближений х⁽⁰⁾.

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

-Функция f(x) = f (x₁, x₂, …, x_n)называетсявыпуклой в области D, если для любых двух точекх⁽¹⁾,

х⁽²⁾ ÎD и любогоλ Î [0,1] выполняется неравенство

если же

то функция называется вогнутой.

Геометрический смысл понятий выпуклости и вогнутости для случая функции одной переменной представлен на рис. 2.3. Из него, в частности, видно, что график выпуклой функции лежит ниже отрезка, соединяющего точки (х⁽¹⁾, f(x(¹⁾)) и (х⁽²⁾, f(x⁽²⁾)), а график вогнутой — выше.

Можно доказать, что достаточным условием выпуклости функцииf (x₁, x₂, …, x_n) является положительная определенность матрицы

называемой также матрицей Гессе, во всех точках х Î D. Соответственно, достаточным условием вогнутости является отрицательная определенность матрицы Гессе. В частности, для функций одной переменной достаточным условием выпуклости (вогнутости) является выполнение неравенства fⁿ(x)≥0 (fⁿ(x)≤0).

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

Теорема 2.2. Если f(x) выпуклая (вогнутая) на Rⁿфункция и

f(x*)=0, тох* — точка глобального минимума (максимума).

Доказательство.

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

Пусть х — произвольная точка, отличная от точки х*. Тогда, для любого λ Î [0,1], в силу вогнутости функцииf(x) будет выполняться

из чего следует

Если ввести вектор l = х - х* и обозначить Δх = λ(x – х*) = λl, то длина вектора Δх будет равна ||Δx||=λ||l||. Следовательно,

Устремив λ → 0 и учитывая, что вектор l сонаправлен с Δх, получим

По условию теоремы

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