Пример 6.8.1-1. Найти точку локального минимума функции.
 |
f(x,y) = x2 + y2 – 4x + 100 – 8y.
Следовательно, в точке x* = 2 и y* = 4 функция имеет локальный минимум.
Пример 6.8.1-2. Найти точку локального минимума функции
f(x,y)= x2+y2–4x+10xy–8y.
Следовательно, функция не имеет точки локального минимума.
Аналитический метод поиска минимума применяется только для ограниченного круга задач. В основном это связано с необходимостью решения системы нелинейных уравнений, которая, как правило, решается численными методами. Оказывается, гораздо проще сразу решать задачу минимизации численными методами. Рассмотрим некоторые из методов.
Методы спуска
Большинство итерационных методов, применяемых для решения задач безусловной минимизации функции нескольких переменных, относятся к классу методов спуска. Это такие методы, для которых каждая итерация (шаг) приводит к уменьшению значения целевой функции: f(xk+1)<f(xk), для всех k³0.
Структура типичного алгоритма метода спуска для функции двух переменных Q(x,y) состоит в следующем:
1.Задается начальная точка (x0, y0), принадлежащая области допустимых значений функции.
2.На текущей k-й итерации (k=0,1, …n) определяется вектор 
задающий направление спуска, причем такой, чтобы для всех достаточно малых значений l>0 (где l- коэффициент, являющийся шагом поиска) выполнялось неравенство:
f(xk + lpk, yk+ lsk) < f(xk,yk).
3.Вычисляется шаг поиска - lk, для которого выполняется условие п.2, и за очередное приближение к точке минимума принимается точка:
|
|
|
(xk + lpk, yk+ lsk), где xk + lpk = xk+1, а yk+ lsk = yk+1.
4.Проверяется выполнение критерия окончания итераций. Если критерий метода выполняется, то полагают (x*,y*)»(xk+1,yk+1). В противном случае осуществляется переход к п.2 и выполняется следующая итерация.
Последовательность точек х1, х2, …, хk, получаемую методом спуска, называют траекторий спуска.
В градиентных методах спуска направление движения к точке минимума целевой функции совпадает с направлением антиградиента, а направление спуска выбирается по формулам:
Для использования градиентного метода оптимизации необходимо определить правило выбора шага (lk) на каждой итерации и правило прекращения итерационного процесса.
При решении вопроса о выборе шага lk следует учитывать, что выбор малого шага на каждой итерации приведет к малым изменениям аргумента и функции, и, следовательно, к увеличению числа итераций, необходимых для решения задачи. Выбор слишком большого шага lk может привести не к убыванию целевой функции Q(x,y), а к ее увеличению, и, следовательно, процесс не будет сходиться к точке минимума.
Метод градиентного спуска с дроблением шага
|
|
|
На каждой итерации шаг спуска lk выбирается таким образом, чтобы выполнялось условие:
(6.8.3-1)
Выбор шага в методе ГДШ заключается в следующем.
Задается начальное значение шага lk = l0 (как правило, l0=0,5). Проверяется условие сходимости, приведенное выше. Если условие сходимости выполняется, то шаг спуска для данной итерации выбран, а если оно не выполняется, то принимают новый шаг lk = lk/2, и снова проверяют условие сходимости (и т.д.).
Алгоритм метода ГДШ можно описать следующей последовательностью действий:
1.При k = 0 задаемся начальной точкой спуска (xk, yk), требуемой точностью e и начальным шагом l0 (пусть l0 =0,5).
2.Вычисляем значения
(6.8.3-2)
3.Вычисляем новые значения переменных
(6.8.3-3)
4.Проверяем условие сходимости:
(6.8.3-4)
Если условие выполняется, то полагаем величину шага равной lk, в противном случае lk = lk/2 и переходим к п.3.
5.Проверка окончания процесса итераций (необходимого условия существования минимума):
(6.8.3-5)
|
|
|
Если условие выполнено, то минимум найден, а если нет - вычисление координат следующей точки (k=k+1) и передача управления п.2.
Рис. 6.8.3-1. Траектория спуска ГДШ
Дата добавления: 2018-05-12; просмотров: 278; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!