Как мы уже видели многие задачи на отыскание условного экстремума сводятся к задаче на безусловный экстремум. Поэтому значительный интерес представляют алгоритмы нахождения экстремума функций.
Принято различать 2 подхода к решению данной задачи. Первый заключается в замене задачи на экстремум задачей поиска решения трансцендентный уравнений вида:
(1)
Или
(2)
при ограничениях типа равенств.
Однако для поиска экстремума можно и не использовать необходимые условия вида (1) и (2). В самом деле, если мы найдем способ определения точек значения функции, в которых образуют убывающую сходящуюся последовательность, то тем самым удастся найти минимум функции, не прибегая к необходимым условиям (1) и (2).
Такие способы называют прямыми методами решения задачи оптимизации.
Итак, нам нужно научиться строить последовательность,
, удовлетворяющую условию
(3)
Такие последовательности называют релаксационными, а методы их построения называют методами спуска. Различные методы спуска отличаются друг от друга способами выбора направления спуска и длины шага вдоль этого направления.
Алгоритм метода спуска имеет вид:
(4)
- направление спуска
- длина шага вдоль этого направления
Важной характеристикой методов спуска является их скорость сходимости (линейная, сверхлинейная).
Алгоритмы (4) принято делить на классы, в зависимости от максимального порядка производных , используемых в алгоритме.
1. Методы, где используется только значение самой функции - методы нулевого порядка.
2. Если требуется - методы первого порядка.
3. Если требуется - методы второго порядка и так далее.
Они сходятся быстрее, но требуют большого числа вычислений. Поэтому на практике, методы, сходящиеся медленнее, но требующие меньшего числа промежуточных операций могут оказаться предпочтительнее.