Лабораторная работа № 14
РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ ГРАДИЕНТНЫМИ МЕТОДАМИ
1. Цель работы.
Научиться использовать ЭВМ для определения экстремума функции двух переменных методом градиентного спуска (подъема).
2. Исходные данные
2.1. Функция двух переменных, вид экстремума и начальные значения аргументов выбираются из табл. 1 в зависимости от номера варианта.
2.2. Начальное значение параметра, определяющего длину шага поиска: h = + 0.05.
2.3. Максимальное число итераций m=200.
2.4. Минимальное значение модуля градиента Ед = 0,005;
минимальное приращение аргумента Ех = 0,001.
Таблица 1
Варианты исходных данных
| Ва- ри- ант | Функция f (x1,x2) | Вид экстре- мума | Координаты начальной точки | ||||
| x1(0) | x2(0) | x1(0) | x2(0) | ||||
| 2*(x1-2)2+(x2-3)4+1 | min | ||||||
| (x1-1)4+3*(x2-2)2+2 | min | ||||||
| 2*(x1+3)2+0.5*(x2-4)4+3 | min | -2 | -4 | ||||
| (x1+2)4+2*(x2-1)2+4 | min | -1 | -3 | ||||
| -(x1-2)2-0.5*(x2-1)4-5 | max | ||||||
| -2*(x1+3)2-(x2-2)4-6 | max | -2 | -4 | ||||
| -(x1-1)4-3*(x2-3)2-7 | max | ||||||
| -2*(x1-5)2-(x2-4)4+8 | max | ||||||
| -0.5(x1+4)4-(x2-1)2+9 | max | -5 | -3 | ||||
| -(x1-2.5)2-(x2+3)4+10 | max | -2 | -4 | ||||
| -(x1+3.5)4-3*(x2+4)2+11 | max | -5 | -5 | -2 | -3 | ||
| (x1+5)4+2*(x2+2)2-12 | min | -4 | -1 | -6 | -3 | ||
| (x1-1.5)2+(x2+2.5)4-13 | min | -4 | -1 | ||||
| 0.5*(x1-4.5)4+(x2-5.5)2-14 | min |
3. Содержание работы
3.1. Разработать алгоритм и программу для определения экстремума функции двух переменных градиентным методом.
3.2. По разработанной программе на ЭВМ провести поиск экстремального значения функции. В процессе поиска через каждые 10 итераций на печать выводить номер итерации, модуль градиента и значения аргументов.
По окончании поиска напечатать оценки оптимальных значений аргументов и экстремального значения функции, значение параметра h и число итераций.
3.3. Изменяя параметр h в интервале h= + 0.05... + 0.2 с шагом + 0.05, исследовать влияние параметра на скорость поиска.
3.4. Построить график зависимости числа итераций, необходимых для нахождения экстремума, от величины параметра h.
4. Теоретические основы работы
 |
Градиент ─ это вектор, который показывает направление наискорейшего возрастания функции. Для функции n переменных W = f (X) градиент записывается в виде
где - частные производные функции, которые являются проекциями
градиента на координатные оси;
где ─ единичные векторы (орты).
Модуль градиента равен наибольшей скорости возрастания функции в данной точке
 |
Вектор, направленный противоположно градиенту и равный ему по величине, называется антиградиентом.
Для проведения поиска градиентным методом вначале выбирается произвольная точка М0, принадлежащая области определения оптимизируемой функции. Затем :
1) определяется направление градиента в точке М0;
2) осуществляется перемещение из точки М0 на величину, равную некоторому шагу, в точку М1, причем перемещение проводится в направлении градиента, если ищется максимум функции и в направлении антиградиента, если ищется минимум функции ;
3) в точке М1 устанавливается новое градиентное направление и делается следующий шаг в новую точку и т.д.
Значение каждой координаты хj в конце к-го шага определится по формуле
 |
где h ─ параметр, определяющий длину шага ;
cкорость изменения функции по координате xj в точке Х(k)
Таким образом, градиентный метод обеспечивает на каждом шаге изменение всех независимых переменных, причем каждая переменная получает приращение, пропорциональное соответствующей составляющей градиента по данной оси.
При поиске минимума движение происходит в антиградиентном направлении, поэтому параметр h берется со знаком "минус".
Рекомендуется придерживаться следующей схемы поиска :
 |  |
1) определить значения проекций градиента в точке (х1,х2)
 |
2) вычислить модуль градиента
если , то перейти к п.6;
 |  |
3) определить координаты очередной точки
4) проверить условия окончания поиска
│х1 (1) ─ х1│ <= Ех , │х2 (1) ─ х2│ <= Ех ,
в случае их выполнения перейти к п.6 ;
5) перейти в новую точку
х1 = х1(1) , х2 = х2(1)
и возвратиться к п.1;
6) вычислить оценку экстремального значения функции
f (x1 (1) , x2 (1) )
5. Содержание отчета
5.1. Цель работы.
5.2. Исходные данные.
5.3. Расчетные формулы с пояснениями.
5.4. Схема алгоритма поиска.
5.5. Распечатка программы и результатов оптимизации.
5.6. График зависимости необходимого числа итераций от величины
параметра h.
5.7. Выводы.