Помимо аналитических методов оптимизации, в практике широко применяются численные методы оптимизации, причем при численной оптимизации дифференцируемых функций во многих случаях также используется понятие градиента.
Рассмотрим некоторые из методов численной оптимизации. Для простоты изложения будем полагать, что модель оптимизации, представленная в форме (4.2), не содержит ограничений. Тогда мы можем говорить, что непрерывная дифференцируемая функция задана во всех точках пространства
. Для произвольной точки
, в которой
, вектор градиента
задает направление наискорейшего роста функции
, а обратное ему направление -
, называемое антиградиентом, - направление наискорейшего убывания этой функции. Это значит, что движение (на очень малый шаг) в направлении градиента функции обеспечивает наибольший рост, а в направлении антиградиента - наибольшее уменьшение этой функции. Из сказанного вытекает общая идея градиентного спуска (подъема): отправляясь из заданной точки
, строим последовательность точек
, так, что перемещение от каждой точки
к точке
, производится в направлении антиградиента (градиента) в точке
[1, С.272; 5, С.225; 15, С.42].
Определение 4.2
Метод градиентного спуска - это метод численной оптимизации гладких функций многих переменных, при котором приближение к экстремуму производится так, что
, (4.5)
где
- вектор единичной длины, имеющий то же направление, что и
.
Существуют различные модификации метода градиентного спуска в зависимости от того, каким образом выбирается величина множителя
, которая должна уменьшаться по мере приближения к точке экстремума. Наиболее простым способом обеспечения требуемого уменьшения шага является выбор длины шага
, пропорциональной длине вектора градиента в точке
.
Определение 4.3
Пропорционально-градиентный метод - один из видов метода градиентного спуска, при котором длина шага на (i+1)-м приближении определяется из условия
,
,
. (4.6)
При использовании полношагового градиентного метода (метода наискорейшего спуска) каждый шаг градиентного спуска делается на максимально возможную длину, обеспечивающую требуемое направление изменения значения функции.
Таким образом, на полупрямой, исходящей из очередной точки
в направлении антиградиента (при спуске) ищется точка абсолютного минимума, которая и выбирается в качестве очередной точки
[1, С.272; 5, С.227; 15, С.45].
Определение 4.4
Метод наискорейшего спуска - один из градиентных методов оптимизации, при котором положение точки
в (i+1)-м приближении определяется из условия
, где
. (4.7)
На рисунке 4.1. изображена геометрическая иллюстрация этого метода для случая минимизации функции двух переменных. Из начальной точки
перпендикулярно линии уровня
в направлении -
спуск продолжают до тех пор, пока не будет достигнуто минимальное вдоль луча значение функции
. В найденной точке
этот луч касается линии уровня
. Затем из точки
проводят спуск в направлении, перпендикулярном линии уровня, до достижения
и т.д. Следует отметить, что чрезвычайно большое значение при использовании численных методов имеет выбор начальной точки
. Так, для случая, приведенного на рисунке, выбор в качестве начальной точки
приведет к тому, что каждая итерация будет приближать решение к седловой точке
, а не к точке минимума
.
Рис 4.1. Геометрическая интерпретация метода наискорейшего спуска при минимизации функции двух переменных
В качестве критерия окончания итераций при использовании численных методов оптимизации, как правило, используют следующие условия
, (4.8)
, (4.9)
, (4.10)
где
,
,
- заданные положительные числа. Нередко используются различные сочетания критериев (4.8)-(4.10) или критерии, основанные на понятии относительной погрешности [1, С.270]. Надежные и универсальные критерии окончания счета, которые были бы применимы к широкому классу задач и гарантировали бы достижение требуемой точности, в настоящее время неизвестны.
Помимо рассмотренных нами методов численной оптимизации широко применяются методы сопряженных градиентов [1, С.284; 5, С.228; 15, С.73], покоординатного спуска [1, С.268; 5, С.239; 15, С.53], метод Ньютона [1, С.279; 15, С.55], методы выпуклой оптимизации [5, С.231] и т.д.
Рис 4.2. Графики функций двух переменных, для максимизации которых градиентные методы неприменимы
Кроме численных методов, основанных на применении понятия градиента, существуют так называемые «методы прямого поиска», при использовании которых вычисление производных не требуется. Методы прямого поиска основаны на сравнении значений целевой функции в последовательно вычисляемых пробных точках. Обычно методы этой группы применяются тогда, когда в окрестности точки локального экстремума функция не является гладкой и не может быть продифференцирована. Примеры графиков таких функций приведены на рисунке 4.2. Методы прямого поиска гораздо менее эффективны, чем градиентные методы, но в ряде случаев их использование неизбежно [1, С.287; 31, С.211-239].
Рассмотренные нами методы численной оптимизации применяются обычно для решения задач без ограничений. В то же время математическая модель оптимизации в форме (4.2) в общем виде содержит ограничения - равенства и неравенства. Задачи вида (4.2) удается сводить к случаю безусловной оптимизации за счет изменения целевой функции. Такой подход реализуется в методах штрафных функций и барьеров [5, С.229; 31, С.196-206].
При использовании метода штрафных функций в задаче максимизации целевая функция
заменяется семейством функцией вида
,
=1,2,... , (4.11)
где
- штрафная функция, которая внутри допустимой области принимает нулевое значение, а вне ее - отрицательна, а
-
-й элемент последовательности положительных чисел, сходящейся к нулю.
В методе барьеров при решении задачи максимизации в форме (4.2) целевая функция
заменяется семейством функций
,
=1,2,... (4.12)
где
- барьерная функция, которая характеризуется свойством стремиться к -
при приближении
к границам допустимой области изнутри, а
определяется аналогично (4.11).
При решении любым из численных методов задачи безусловной оптимизации (4.11) или (4.12) при
=1,2,..., может быть получена последовательность экстремальных точек
, сходящаяся к экстремальной точке исходной задачи (4.2).Переход от задачи максимизации к задаче минимизации при использовании метода штрафных функций и метода барьеров осуществляется изменением знака штрафной
