ФГБОУ «Санкт-Петербургский государственный электротехнический
университет «ЛЭТИ» им. В.И. Ульянова (Ленина)»
Кафедра САПР
Отчет по лабораторной работе № 4
по учебной дисциплине «методы оптимизации»
на тему «исследование градиентных методов»
Вариант 1
Выполнили:
Гаража И.М.
Иванов П.В.
Группа 0306
Преподаватель:
Марков М.В.
(должность, Ф.И.О.)
Санкт-Петербург
2012
Оглавление:
Задание………………………………………………………………………………………………………………………………………………….3
Описание методов оптимизации…………………………………………………………………………………………………………3
Блок-схемы методов……………………………………………………………………………………………………………………………..5
Текст программы …………………..……………………………………………....................................................................7
Результаты тестирования, Графическая интерпретация и Выводы…………………….…………………………….9
Ответы на контрольные вопросы………………………………………………...........................................................10
Задание:
Цель работы – разработка программы многомерной минимизации целевых функций на основе применения простых градиентных методов поиска.
Методы многомерной оптимизации:
М1 – метод Коши;
|
Функция y(x) |
Начальная точка (x1)t |
Значение минимума (x*)t |
|
100(x2 – x12)2 + (1 – x1)2 |
(–1.2; 1) (1.5; 2) (–2; –2) |
(1; 1) |
Описание методов оптимизации:
Метод Свенна 4.
Начальный этап. Для запуска метода необходимо:
(1) задать x0 – начальная точка.
(2) выбрать шаг h равным 0.001 или min{η,|(y1-y’)/y’1|}, где η=1,2.
(3) выбрать направление поиска p.
Основной этап
Шаг 1. Установить направление убывания функции. h=h, если y’(x0,p)<0 и h=-h, если y’(x0,p)>0.
Шаг 2.Двигаться в направлении р, вычисляя значение функции в точках xk+1=xk+hk*p, hk=2hk-1. Пока производная не поменяет знак, т.е. Y’m-1*Y’m<0
Шаг 3. Фиксируем начальный интервал: [Xm-1,Xm]
Метод Дэвидона.
Этот метод является аналогом метода кубической аппроксимации в задачах поиска минимума функции нескольких переменных по заданному направлению. Идея метода заключается в том, чтобы на ТИЛ найти аппроксимирующий минимум строя полином 3-го порядка.
Начальный этап:
Взять ε, х 0 – начальную точку поиска, p – направление поиска.
Найти начальный шаг α1 = min{ η,|(y1-y’)/y’1|}, где η=1,2. y1=y(x1), y’1 =y’(x1,p)
Получить начальный интервал поиска [a,b] методом Свенна 4.
Основной этап:
Найти аппроксимирующий минимум, т.е. точку r по формулам:
r = a+αr *p
αr = α a +γ*( α b - αa )
γ=(z-f’a+W)/(f’b-f’a+2*W)
W=√z2-f’a*f’b
z=f’a+f’b+3*(fa-fb)/(b-a)
Проверить КОП если Y’r<=ε, то остановиться. X= a+ αr *p Иначе сократить ТИЛ двумя способами:
Y’r<0 -> [r,b]
Y’r>0 -> [a,r]
Установить k=k+1 и вернуться на шаг 1.
Можно модифицировать алгоритм – ввести смещение точек на α0 .
Метод Коши
Начальный этап:
Взять ε - погрешность,
х 0 – начальную точку поиска,
k=1 – счетчик количества итераций.
Основной этап:
Шаг1: Вычислить антиградиентное направление pk = - grad (yk );
Шаг2: Найти оптимальный шаг αk с помощью метода Дэвидона;
Шаг3: Перейти в новую точку:
- xk+1= xk + αk*pk ;
- k=k+1;
Шаг4: Проверить КОП (любой):
(1) ||∆ xk||<= e1
(2) | ∆yk|<= e2
(3) ||grad (yk)||<= e3
(4) ||∆ xk||/(1+||∆ xk||)<= e4
(5) ||grad (yk)||/(1+||grad (yk)||)<= e5
Если КОП выполняется остановимся x* = xк+1 , иначе вернуться на
Шаг1.
Блок-схемы использованных методов.
Метод Свенна
h1=0.1*|x1|
x2=x1+h1
x1=x2;
x2=x1+h;
h=2*h;
Меняем местами а
и b
h=-h;
x2=x1+h;
Да
Да
Да
Нет
Нет
Нет