КОНСПЕКТ ЛЕКЦІЙ
“Методи оптимізації та дослiдження операцiй”
за фахом «Програмна інженерія»
факультету №9
Харків – 2011
Применение метода наискорейшего спуска для решения задачи минимизации без ограничений было рассмотрено еще известным французским математиком Коши. Как известно из курса математического анализа, градиент целевой функции в любой точке
x=(x1,…,xn) есть вектор в направлении локального увеличения . Следовательно, для минимизации целевой функции нужно двигаться в направлении, противоположном градиенту , т.е. в направлении наискорейшего спуска, поскольку отрицательный градиент в точке =(x1 (k) ,…,xn (k) ) направлен в сторону наибольшего уменьшения по всем компонентам x и ортогонален линии уровня в точке , где k – номер шага метода, k=0, 1, …. Введение направления, противоположного градиенту, т.е. направления наискорейшего спуска, дает следующую формулу перехода из в :
(3.1.1)
Отрицательный градиент дает только направление оптимизации, но не величину шага. При этом можно использовать различные версии метода наискорейшего спуска в зависимости от процедуры выбора . Поскольку один шаг в направлении наискорейшего спуска в общем случае не приводит в точку минимума , формула (3.1.1) должна применяться несколько раз до тех пор, пока минимум не будет достигнут. В точке минимума все сотавляющие вектора градиента равны нулю, т.е. критерий останова алгоритма поиска:
|
|
(3.1.2)
Используем следующий метод нахождения . Пусть - функция от . Наращиваем от 0 с малым шагом до тех пор, пока не получим .
Построим полином второго порядка для по трем точкам (0, /2, ):
, где . (3.1.3)
Составляем систему:
(3.1.4)
решаем ее относительно коэффициентов a и b, после чего находим оптимальное значение как координату экстремума параболы по формуле:
. (3.1.5)
Для вычисления градиента функции воспользуемся определением производной , пусть , тогда
(3.1.6)
Таким образом, используя формулы (3.1.1)-(3.1.6), получаем минимизирующую последовательность и искомое значение .