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

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

f(x [k ] -a k f"(x [k ])) = f(x [k] - af"(x [k ])) .

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

j(a) = f(x [k ] - af"(x [k ])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

• 1. Задаются координаты начальной точки х .
• 2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f"(x [k ]) .
• 3. Определяется величина шага a k , путем одномерной минимизации по а функции j(a) = f(x [k ] - af"(x [k ])).
• 4. Определяются координаты точки х [k+ 1]:

х i [k+ 1] = x i [k ] - а k f" i (х [k ]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции?(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

d j(a)/da = -f"(x [k+ 1]f"(x [k ]) = 0.

Рис. 2.9.

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

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l i , i =1, …, n , матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 2.10.

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

Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.

Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .

Описание [ | ]

Усовершенствования [ | ]

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

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

Применение в искусственных нейронных сетях [ | ]

Метод градиентного спуска с некоторой модификацией широко применяется для обучения перцептрона и в теории искусственных нейронных сетей известен как метод обратного распространения ошибки . При обучении нейросети типа «персептрон» требуется изменять весовые коэффициенты сети так, чтобы минимизировать среднюю ошибку на выходе нейронной сети при подаче на вход последовательности обучающих входных данных. Формально, чтобы сделать всего один шаг по методу градиентного спуска (сделать всего одно изменение параметров сети), необходимо подать на вход сети последовательно абсолютно весь набор обучающих данных, для каждого объекта обучающих данных вычислить ошибку и рассчитать необходимую коррекцию коэффициентов сети (но не делать эту коррекцию), и уже после подачи всех данных рассчитать сумму в корректировке каждого коэффициента сети (сумма градиентов) и произвести коррекцию коэффициентов «на один шаг». Очевидно, что при большом наборе обучающих данных алгоритм будет работать крайне медленно, поэтому на практике часто производят корректировку коэффициентов сети после каждого элемента обучения, где значение градиента аппроксимируются градиентом функции стоимости, вычисленном только на одном элементе обучения. Такой метод называют стохастическим градиентным спуском или оперативным градиентным спуском . Стохастический градиентный спуск является одной из форм стохастического приближения. Теория стохастических приближений даёт условия сходимости метода стохастического градиентного спуска.

Ссылки [ | ]

• J. Mathews. Module for Steepest Descent or Gradient Method. (недоступная ссылка)

Литература [ | ]

• Акулич И. Л. Математическое программирование в примерах и задачах. - М. : Высшая школа, 1986. - С. 298-310.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. - М. : Мир, 1985.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М. : Энергоатомиздат, 1972.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М. : МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М. : МИФИ, 1980.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М. : Наука, 1970. - С. 575-576.
• С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. - Нижний Новгород: Издательство Нижегородского Университета, 2007. - С. 357-363.

В этом варианте градиентного метода минимизирующая последовательность {X k } также строится по правилу (2.22). Однако величина шага a k находится в результате решения вспомогательной задачи одномерной минимизации

min{j k (a) | a>0 }, (2.27)

где j k (a)=f(X k - a· (X k)). Таким образом, на каждой итерации в направлении антиградиента выполняется исчерпывающий спуск. Для решения задачи (2.27) можно воспользоваться одним из методов одномерного поиска, изложенных в разделе 1, например, методом поразрядного поиска или методом золотого сечения.

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

Шаг 0. Задать параметр точности e>0, выбрать X 0 ÎE n , положить k=0.

Шаг 1. Найти (X k) и проверить условие достижения заданной точности || (x k) ||£ e. Если оно выполняется, то перейти к шагу 3, иначе - к шагу 2.

Шаг 2. Решить задачу (2.27), т.е. найти a k . Найти очередную точку , положить k=k+1 и перейти к шагу 1.

Шаг 3 Завершить вычисления, положив X * = X k , f * = f(X k).

Типовой пример

Минимизировать функцию

f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)

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

Решив ее, получим стационарную точку X*=(3;1). Далее проверим выполнение достаточного условия, для чего найдем матрицу вторых производных

Так как, согласно критерию Сильвестра, эта матрица положительно определена при " , то найденная точка X* является точкой минимума функции f(X). Минимальное значение f *=f(X*)=0. Таково точное решение задачи (11).

Выполним одну итерацию метода градиентого спуска для (2.28). Выберем начальную точку X 0 =(1;0), зададим начальный шаг a=1 и параметр l=0,5. Вычислим f(X 0)=8.

Найдем градиент функции f(X) в точке X 0

(X 0)= = (2.29)

Определим новую точку X=X 0 -a· (X 0), вычислив ее координаты

x 1 =

x 2 = (2.30)

Вычислим f(X)= f(X 0 -a· (X 0))=200. Так как f(X)>f(X 0), то выполняем дробление шага, полагая a=a·l=1·0,5=0,5. Снова вычисляем по формулам (2.30) x 1 =1+4a=3; x 2 =8a=4 и находим значение f(X)=39. Так как опять f(X)>f(X 0), то еще уменьшаем величину шага, полагая a=a·l=0,5·0,5=0,25. Вычисляем новую точку с координатами x 1 =1+4·0,25=2; x 2 =8·0,25=2 и значение функции в этой точке f(X)=5. Поскольку условие убывания f(X)

Выполним одну итерацию по методу наискорейшего спуска для (2.28) с той же начальной точкой X 0 =(1;0). Используя уже найденный градиент (2.29), находим

X= X 0 -a· (X 0)

и строим функцию j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2 . Минимизируя ее с помощью необходимого условия

j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0

находим оптимальное значение величины шага a 0 =5/34.

Определяем точку минимизирующей последовательности

X 1 = X 0 -a 0 · (X 0) .

Градиентом дифференцируемой функции f(x) в точке х называется n -мерный вектор f(x ) , компоненты которого являются частными производными функции f(х), вычисленными в точке х , т. е.

f"(x) = (дf(х )/дх 1 , …, дf(х )/дх n) T .

Этот вектор перпендикулярен к плоскости, проведенной через точку х , и касательной к поверхности уровня функции f(x), проходящей через точку х .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С 0 , С 1 , ... , получим серию поверхностей, характеризующих ее топологию (Рис. 2.8).

Рис. 2.8. Градиент

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

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

х[k+ 1] = x [k ]-a k f"(x [k]) , а k > 0; k =0, 1, 2, ...

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

x i [k +1]=х i [k ] - a k f(x [k]) /x i

i = 1, ..., n ; k = 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x [k +l] - x [k ] || <= e , либо выполнение условия малости градиента

|| f’(x [k +l]) || <= g ,

Здесь e и g - заданные малые величины.

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

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

f(х[k +1]) = f(x [k] – a k f’(x [k])) < f(x [k]) .

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

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

При использовании метода наискорейшего спуска на каждой итерации величина шага а k выбирается из условия минимума функции f(x) в направлении спуска, т. е.
f(x [k ] –a k f’(x [k ])) = f(x [k] – af"(x [k ])) .

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j (a) = f(x [k ] - af"(x [k ])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х .

2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f’(x [k ]) .

3. Определяется величина шага a k , путем одномерной минимизации по а функции j (a) = f(x [k ] - af"(x [k ])).

4. Определяются координаты точки х [k+ 1]:

х i [k+ 1] = x i [k ] – а k f’ i (х [k ]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции?(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j (a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj (a)/da = -f’(x [k+ 1]f’(x [k ]) = 0.

Рис. 2.9. Геометрическая интерпретация метода наискорейшего спуска

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

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l i , i =1, …, n , матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 2.10. Овражная функция

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

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

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n -мерных вектора х и у называют сопряженными по отношению к матрице H (или H -сопряженными), если скалярное произведение (x , Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером п хп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x [k ]) в направление p [k ], H -сопряженное с ранее найденными направлениями р , р , ..., р [k -1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р [k ] вычисляют по формулам:

p[k ] = -f’(x [k ]) +b k-1 p [k -l], k >= 1;

p = -f ’(x ) .

Величины b k -1 выбираются так, чтобы направления p [k ], р [k -1] были H -сопряженными:

(p [k ], Hp [k- 1])= 0.

В результате для квадратичной функции

,

итерационный процесс минимизации имеет вид

x[k +l] =x [k ] +a k p [k ],

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

f(х[k ] + а k р [k ]) = f(x [k ] + ар [k ]) .

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х вычисляется p = -f’(x ) .

2. На k- м шаге по приведенным выше формулам определяются шаг а k . и точка х [k+ 1].

3. Вычисляются величины f(x [k +1]) и f’(x [k +1]) .

4. Если f’(x ) = 0, то точка х [k +1] является точкой минимума функции f(х). В противном случае определяется новое направление p [k +l] из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+ 1)-й итерации процедуры 1-4 циклически повторяются с заменой х на х [п +1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:

x[k +l] = x [k ] +a k p [k ],

p[k ] = -f’(x [k ])+ b k- 1 p [k -l], k >= 1;

p = -f’(x );

f(х[k ] + a k p [k ]) = f(x [k ] + ap [k ];

.

Здесь I - множество индексов: I = {0, n, 2п, Зп, ...} , т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х осуществляется спуск в направлении р = -f"(x ). В точке х определяется вектор-градиент f"(x ). Поскольку х является точкой минимума функции в направлении р , то f’(х ) ортогонален вектору р . Затем отыскивается вектор р , H -сопряженный к р . Далее отыскивается минимум функции вдоль направления р и т. д.

Рис. 2.11. Траектория спуска в методе сопряженных градиентов

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

Постановка задачи

Пусть дана функция f (х) R n

Требуется f (х) X = R n

Стратегия поиска

x k } , k = 0,1,..., таких, что , k = 0,1,... . Точки последовательности {x k } вычисляются по правилу

где точка х 0 задается пользователем; величина шага t k определяется для каждого значения k из условия

Решение задачи (3) может осуществляться с использованием необходи­мого условия минимума с последующей проверкой достаточного условия минимума . Такой путь может быть использован либо при достаточно простой минимизируемой функции , либо при предварительной аппроксимации достаточно сложной функции полиномом P(t k) (как правило, второй или третьей степени), и тогда условие замещается условием , а условие условием

Построение последовательности { x k } заканчивается в точке x k , для которой , где ε - заданное малое положительное число, или k ≥ M , где М - предельное число итераций, или при двукратном одновременном выполнении двух неравенств , где ε 2 - малое положительное число. Вопрос о том, может ли точка x k рассматриваться как найденное приближение искомой точки локального минимума x * , решается путем дополни­тельного исследования.

Геометрическая интерпретация метода для n=2 на рис. 4.

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

Постановка задачи

Пусть дана функция f (х) , ограниченная снизу на множестве R n и имеющая непрерывные частные производные во всех его точках.

f (х) на множестве допустимых решений X = R n , т.е. найти такую точку , что

Стратегия поиска

Стратегия решения задачи состоит в построении последовательности точек {x k } , k = 0,1,..., таких, что , k = 0,1,... . Точки последовательности {x k } вычисляются по циклам в соответствии с правилом

(4)

где j - номер цикла вычислений; j = 0,1,2,...; k - номер итерации внутри цикла, k = 0,1,... ,n - 1; е k +1 , k = 0,l,...,n - 1 -единичный вектор, (k +1) -я проекция ко­торого равна 1; точка х 00 задается пользователем, величина шага t k выбирается из условия

или .

Если выбранное условие при текущем t k не выполняется, шаг уменьшается вдвое и точка вычисляется заново. Легко видеть, что при фиксированном j за одну итерацию с номером k изменяется только одна проекция точки х jk , имеющая номер k + 1 , а в течение всего цикла с номером j , т.е. начиная с k = 0 и кончая k = n -1 , изменяются все п проекций точки х j0 . После этого точке х j n присваивается номер х j + 1,0 , и она берется за на­чальную точку для вычислений в j + 1 цикле. Расчет заканчивается в точке х jk при выполнении по крайней мере одного из трех критериев окончания счета: , или , или двукратного выполнения неравенств .

Полученные в результате вычислений точки могут быть записаны как эле­менты последовательности {х l }, где l=n*j+k - порядковый номер точки,

Геометрическая интерпретация метода для п = 2 приведена на рис. 5.

4. Метод Франка-Вулфа .

Пусть требуется найти максимальное значение вогнутой функции

При условиях

Характерной особенностью этой задачи является то, что ее система ограничений содержит только линейные неравенства. Эта особенность является основой для замены в окрестности исследуемой точки нелинейной целевой функции линейной, благодаря чему решение исходной задачи сводится к последовательному решению задач линейного программирования.
Процесс нахождения решения задачи начинают с определения точки, принадлежащей области допустимых решений за-
270
дачи. Пусть это точка X (k) тогда в этой точке вычисляют градиент функции (57)

И строят линейную функцию

Затем находят максимальное значение этой функции при ограничениях (58) и (59). Пусть решение данной задачи определяется точкой Z (k) . Тогда за новое допустимое решение исходной задачи принимают координаты точки X (k +1) :

Где λ k - некоторое число, называемое шагом вычислений и заключенное между нулем и единицей (0< λ k < 1). Это число λ k берут произвольно или определяют

таким образом, чтобы значение функции в точке X (k +1) f(X (k +1)) , зависящее от λ k , было максимальным. Для этого необходимо найти решение уравнения и выбрать его наименьший корень. Если его значение больше единицы, то следует положить λ k =1 . После определения числа λ k находят координаты точки X (k +1) вычисляют значение целевой функции в ней и выясняют необходимость перехода к новой точке X (k +2) . Если такая необходимость имеется, то вычисляют в точке X (k +1) градиент целевой функции, переходят к соответствующей задаче линейного программирования и находят ее решение. Определяют координаты точки и X (k +2) и исследуют необходимость проведения дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

Итак, процесс нахождения решения задачи (57) - (59) методом Франка-Вулфа включает следующие этапы :

1. Определяют исходное допустимое решение задачи.
2. Находят градиент функции (57) в точке допустимого решения.
3. Строят функцию (60) и находят ее максимальное значение при условиях (58) и (59).
4. Определяют шаг вычислений.
5. По формулам (61) находят компоненты нового допустимого решения.
6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.

Метод штрафных функций.

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

f (х 1 , х 2 , .... х n) при условиях g i (х 1 , х 2 , .... х n) ≤ b i (i=l, m) , х j ≥ 0 (j=1, n) , где g i (х 1 , х 2 , .... х n) - выпуклые функции.

Вместо того чтобы непосредственно решать эту задачу, находят максимальное значение функции F(х 1 , х 2 , ...., х n)= f(х 1 , х 2 , ...., х n) +H(х 1 , х 2 , ...., х n) являющейся суммой целевой функции задачи, и некоторой функции

H(х 1 , х 2 , ...., х n) , определяемой системой ограничений и называемой штрафной функцией . Штрафную функцию можно построить различными способами. Однако наиболее часто она имеет вид

А a i > 0 - некоторые постоянные числа, представляющие собой весовые коэффициенты.
Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. При этом координаты последующей точки находят по формуле

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

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

1. Определяют исходное допустимое решение.
2. Выбирают шаг вычислений.
3. Находят по всем переменным частные производные от целевой функции и функций, определяющих область допустимых решений задачи.

4. По формуле (72) находят координаты точки, определяющей возможное новое решение задачи.
5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты найденной точки определяют допустимое решение задачи, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.
6. Устанавливают значения весовых коэффициентов и переходят к этапу 4.

Метод Эрроу - Гурвица.

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

В качестве начальных значений a i (0) берут произвольные неотрицательные числа.

ПРИМЕР РЕШЕНИЯ

Пример 1 .

Найти локальный минимум функции

Определение точки х k

1.Зададим .

2. Положим к = 0 .

3 0 . Вычислим

4 0 . Вычислим . Переходим к шагу 5.

5 0 . Проверим условие . Переходим к шагу 6.

6 0 . Зададим t 0 = 0,5 .

7 0 . Вычислим

8 0 . Сравним . Имеем . Вывод: условие для k = 0 не выполняется. Зададим t 0 = 0,25 , переходим к по­вторению шагов 7, 8.

7 01 . Вычислим .

8 01 . Сравним f (х 1) и f (х 0) . Вывод: f (x 1) < f (x 0) . Переходим к шагу 9.

9 0 . Вычислим

Вывод: полагаем k =1 и переходим к шагу 3.

3 1 . Вычислим

4 1 . Вычислим . Переходим к шагу 5.

5 1 . Проверим условие k ≥ M: k = 1 < 10 = M . Переходим к шагу 6.

6 1 . Зададим t 1 = 0,25.

7 1 . Вычислим

8 1 . Сравним f (х 2) с f (х 1) . Вывод: f (х 2) < f (х 1). Переходим к шагу 9.

9 1 . Вычислим

Вывод: полагаем k = 2 и переходим к шагу 3.

3 2 . Вычислим

4 2 . Вычислим . Переходим к шагу 5.

5 2 . Проверим условие k ≥ M : k = 2 < 10 = М , переходим к шагу 6.

6 2 . Зададим t 2 =0,25 .

7 2 . Вычислим

8 2 . Сравним f (х 3) и f (х 2) . Вывод: f (х 3) < f (х 2) .Переходим к шагу 9.

9 2 . Вычислим

Вывод: полагаем k = 3 и переходим к шагу 3.

3 3 . Вычислим

4 3 . Вычислим . Переходим к шагу 5.

5 3 . Проверим условие k ≥ M : k = 3<10 = М , переходим к шагу 6.

6 3 . Зададим t 3 = 0,25.

7 3 . Вычислим

8 3 . Сравним f (х 4) и f (х 3) : f (х 4) < f (х 3) .

9 3 . Вычислим

Условия выполнены при k = 2,3 . Расчет

окончен. Найдена точка

На рис. 3 полученные точки соединены пунктирной линией.

II. Анализ точки х 4 .

Функция является дважды дифференцируемой, поэтому проведем проверку достаточных условий минимума в точке х 4 . Для этого проанализируем матрицу Гессе .

Матрица постоянна и является положительно определенной (т.е. H > 0 ) , так как оба ее угловых минора и положительны. Следовательно, точка есть найденное приближение точки локального минимума , а значение есть найденное приближение значения f (x *) =0 . Заметим, что условие H > 0 , есть одновременно условие строгой выпуклости функции . Следовательно, есть найден­ные приближения точки глобального минимума f (x) и ее наименьшего значе­ния на R 2 . ■

Пример 2

Найти локальный минимум функции

I. Определение точки х k , в которой выполнен по крайней мере один из критериев окончания расчетов.

1.Зададим .

Найдем градиент функции в произвольной точке

2. Положим к = 0 .

3 0 . Вычислим

4 0 . Вычислим . Переходим к шагу 5.

5 0 . Проверим условие . Переходим к шагу 6.

6° . Следующая точка находится по формуле

Подставим полученные выражения для коор­динат в

Найдем минимум функции f(t 0) по t 0 с помощью необходимых условий безусловного экстремума:

Отсюда t 0 =0.24 . Так как , найденное значение шага обеспечивает минимум функции f(t 0) по t 0 .

Определим

7 0 . Найдем

8°. Вычислим

Вывод: полагаем k = 1 и переходим к шагу 3.

3 1 . Вычислим

4 1 . Вычислим

5 1 . Проверим условие k ≥ 1: k = 1 < 10 = М.

6 1 . Определим

7 1 . Найдем :

8 1 . Вычислим

Полагаем k = 2 и переходим к шагу 3.

3 2 . Вычислим

4 2 . Вычислим

5 2 . Проверим условие k ≥ M: k = 2 < 10 = M .

6 2 . Определим

7 2 . Найдем

8 2 . Вычислим

Полагаем k =3 и переходим к шагу 3.

3 3 . Вычислим

4 3 . Вычислим .

Расчет окончен. Найдена точка

II. Анализ точки х 3 .

В примере 1.1 (гл.2 §1) было показано, что функция f (x) является строго выпуклой и, следовательно, точках3 является найденным приближением точки глобаль­ного минимума х* .

Пример 3.

Найти локальный минимум функции

I. Определение точки x jk , в которой выполнен по крайней мере один из критериев окончания расчетов.

1. Зададим

Найдем градиент функции в произвольной точке

2. Зададим j = 0.

3 0 . Проверим выполнение условия

4 0 . Зададим k = 0.

5 0 . Проверим выполнение условия

6 0 . Вычислим

7 0 . Проверим условие

8 0 . Зададим

9 0 . Вычислим , где

10 0 . Проверим условие

Вы­вод: полагаем и переходим к шагу 9.

9 01 . Вычислим х 01 с шагом

10 01 . Проверим условие

11 0 . Проверим условия

Полагаем k =1 и переходим к шагу 5.

5 1 . Проверим условие

6 1 . Вычислим

7 1 . Проверим условие

8 1 . Зададим

9 1 . Вычислим

10 1 . Проверим условие :

11 1 . Проверим условия

Полагаем k = 2 , переходим к шагу 5.

5 2 . Проверим условие . Зададим , пе­реходим к шагу 3.

3 1 . Проверим условие

4 1 . Зададим k = 0.

5 2 . Проверим условие

6 2 . Вычислим

7 2 . Проверим условие

8 2 . Зададим

9 2 . Вычислим

10 2 . Проверим условие

11 2 . Проверим условия

Полагаем k =1 и переходим к шагу 5.

5 3 . Проверим условие

6 3 . Вычислим

7 3 . Проверим условия

8 3 . Зададим

9 3 . Вычислим

10 3 . Проверим условие

11 3 . Проверим условия

Зададим k = 2 и переходим к шагу 5.

5 4 . Проверим условие

Полагаем j = 2, х 20 = х 12 и переходим к шагу 3.

3 2 . Проверим условие

4 2 . Зададим k =0 .

5 4 . Проверим условие

6 4 . Вычислим

7 4 . Проверим условие

8 4 . Зададим

9 4 . Вычислим

10 4 . Проверим условие , пе­рейдем к шагу 11.

11 4 . Проверим условия

Условия выполнены в двух последовательных циклах с номерами j = 2 и j -1= 1 . Расчет окончен, найдена точка

На рис. 6 полученные точки соединены пунктирной линией.

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

II. Анализ точки х21 .

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

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

Теорема. Если функция f (x) ограничена снизу, ее градиент удовлетворяет условию Липшица () и выбор значения t n производится одним из описанных выше спосо­бов, то, какова бы ни была начальная точка х 0 :

при .

При практической реализации схемы

k =1, 2, … n .

итерации прекращаются, если для всех i , i = 1, 2, ..., n , выпол­нены условия типа

,

где - некоторое заданное число, характеризующее точ­ность нахождения минимума.

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

ЗАКЛЮЧЕНИЕ

Выше были рассмотрены примеры градиентных методов безусловной оптимизации. В результате проделанной работы можно сделать следующие выводы:

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

2. Многие алго­ритмы решения задач с ограничениями включают миними­зацию без ограничений как некоторый этап.

3. Различные методы спуска отличаются друг от друга способами выбора направления спуска и длины шага вдоль этого направления.

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Косоруков О.А. Исследование операций: учебник. 2003

2. Пантлеев А.В. Методы оптимизации в примерах и задачах: учеб. Пособие. 2005

3. Шишкин Е.В. Исследование операций: учеб. 2006

4. Акулич И.Л. Математическое программирование в примерах и задачах. 1986

5. Вентцель Е.С. Исследование операций. 1980

6. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения. 1988

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-07-02