Similar presentations:
Численный анализ нелинейных моделей и теория Куна-Таккера (Лекция 5)
1. Моделирование систем
МОДЕЛИРОВАНИЕ СИСТЕМЛекция 5: Численный анализ нелинейных
моделей и теория Куна-Таккера.
2. содержание
СОДЕРЖАНИЕТекущий контроль
Методы наискорейшего
спуска (спуск по
градиенту)
Элементы теории КунаТаккера
3. Текущий контроль 1
ТЕКУЩИЙ КОНТРОЛЬ 1Выбрать оптимальную архитектуру
обсерватории, корпус которой является
цилиндрическим, а раздвижная крыша может
быть полусферической или конической. Объем
обсерватории равен V, минимизируется расход
материала на ее стены, основание и крышу. Для
высоты и радиуса цилиндра и конуса
определены нижние границы.
h1
d
h2
d/2
4. Текущий контроль 2 Решить методом множителей лагранжа
ТЕКУЩИЙ КОНТРОЛЬ 2РЕШИТЬ МЕТОДОМ МНОЖИТЕЛЕЙ ЛАГРАНЖА
i-порядковый номер студента.
i
i
max;
x2 y2
x 2 y 2 2i 2 .
5. Постановка задачи
ПОСТАНОВКА ЗАДАЧИЗадана нелинейная однокритериальная
оптимизационная модель вида:
f ( x ) min (max);
j : j ( x ) b j ;
(1)
x {x1 , x2 ,...., xn };
1 i n : ai xi bi .
Все функции системы (1) являются
гладкими и дифференцируемыми, известно
одно допустимое значение
Вектора переменных. Требуется определить
оптимальный вектор переменных.
6. СПУСК ПО ГРАДИЕНТУ – ИДЕЯ МЕТОДА
Суть метода – в движении от однойточки к другой в направлении
экстремума:
касательные
х₂
Стартовая точка
х₁
7. Алгоритм спуска по градиенту – первые два шага (всего 10 шагов)
АЛГОРИТМ СПУСКА ПО ГРАДИЕНТУ – ПЕРВЫЕДВА ШАГА (ВСЕГО 10 ШАГОВ)
Шаг 1. Вычисляется значение
функции f в стартовой точке.
Шаг 2. Для каждой переменной
вычисляется новое значение по
формуле:
i : xiн xic
f ( x)
xi
f
(
x
)
j x
j
2
.
8. Алгоритм спуска по градиенту – следующие четыре шага
АЛГОРИТМ СПУСКА ПО ГРАДИЕНТУ – СЛЕДУЮЩИЕЧЕТЫРЕ ШАГА
Шаг 3. Вычисляется новое значение целевой
функции f₁.
Шаг 4. Если f₁ «лучше» чем f, то перейти к
следующему шагу, нет – к шагу 8.
Шаг 5. Если ограничения системы (1)
выполняются, то перейти к следующему шагу,
в противном случае – к шагу 8.
Шаг 6. Переменной f присваивается
значение, равное f₁.
9. Последние четыре шага алгоритма
ПОСЛЕДНИЕ ЧЕТЫРЕ ШАГААЛГОРИТМА
Шаг 7. Старые значения переменных
заменяются на новые, полученные на шаге 2
последней итерации. Перейти к шагу 2.
Шаг 8. Величине шага β присваивается новое
значение, которое вдвое меньше хранящегося
в памяти: β = β/2.
Шаг 9. Если новое значение β больше заданной
точности поиска Ɛ, то перейти к шагу 2, в
противном случае – к шагу 10.
Шаг 10. Конец алгоритма
10. ПРИМЕР 1
Пользуясь спуском по градиенту решитьзадачу:
1 1
f x y max;
2
2
x
y
9;
(1)
x 0; y 0.
Точка старта: х=у=3; f=0,66, начальная
величина шага β=1, конечная величина шага
γ=0,25.
11. РЕШЕНИЕ
1f
x x 2 ;
1)
f
12 .
y
y
z=0,8.
x н xc
н
c
y
y
f
x
f
x
f
x
2
2
2
2
f
y
f
y
f
y
2,5;
2,5.
Новые значения переменных удовлетворяют
ограничениям, f=0,8, поэтому величина шага β не
меняется.
12. Решение – вторая итерация
РЕШЕНИЕ – ВТОРАЯ ИТЕРАЦИЯf
2) н c
x
x x
2,5 0,5 2,0;
2
2
f f
x y
f
н
y
c
2,5 0,5 2,0.
y y
2
2
f f
x y
Ограничения не выполняются, поэтому величина шага β
уменьшается в два раза: β=β/2=0,5. Возврат в точку старта,
найденную на первой итерации.
13. Решение – третья итерация
РЕШЕНИЕ – ТРЕТЬЯ ИТЕРАЦИЯ3)
xн xc
н
c
y
y
f
x
f
x
f
x
2
2
2
2
f
y
f
y
f
y
2,5 0,25 2,25;
2,5 0,25 2,25.
Ограничения выполняются, новое значение целевой
функции f = 0,888.
14. РЕШЕНИЕ – ЧЕТВЕРТАЯ ИТЕРАЦИЯ
4)xн xc
н
c
y y
f
x
f
x
f
x
2
f
y
f
y
2
2
f
y
2
2,25 0,5
0,2
2,0;
0,4
2,25 0,5
0,2
2,0.
0,4
Так как ограничения не выполняются, то шаг
уменьшается в 2 раза: β=0,25.
15. Решение – пятая итерация
РЕШЕНИЕ – ПЯТАЯ ИТЕРАЦИЯ5)
xн xc
н
c
y y
f
x
f
x
2
f
y
f
y
2
2,25 0,25
0,2
2,125;
0,4
0,2
2,25 0,25
2,125.
2
2
0,4
f f
x y
Ограничения выполняются, f = 0,9411.
16. Решение – шестая итерация
РЕШЕНИЕ – ШЕСТАЯ ИТЕРАЦИЯ6)
xн xc
н
c
y
y
f
x
1
2,125 0,25 2,0;
2
2
2
f f
x y
f
y
1
2,125 0,25 2,0.
2
2
2
f f
x y
Значения переменных не удовлетворяют ограничению, шаг β
уменьшается в два раза, но при этом он становится меньше,
чем γ, поэтому поиск прекращается. x=у=2,125; f=0,9411.
17. самостоятельно
САМОСТОЯТЕЛЬНОПользуясь приведенным выше алгоритмом
решить задачу (2):
( x 2) 2 ( y 3) 2 min;
2
2
x y 4.
(2)
Решить задачи (1) и (2), пользуясь методом
множителей Лагранжа и сравнить
результаты.
Сформулировать достоинства и недостатки
спуска по градиенту.
18. Определение выпуклых функций
ОПРЕДЕЛЕНИЕ ВЫПУКЛЫХ ФУНКЦИЙФункция f называют выпуклой на интервале [a,b] если
для любой точки отрезка, соединяющего точки f(a) и f(b),
справедливо: все точки этого отрезка расположены над
кривой, отображающей f(x) на этом интервале:
f
a
х
b
19. Определение вогнутых функций
ОПРЕДЕЛЕНИЕ ВОГНУТЫХ ФУНКЦИЙФункция f называют вогнутой на
интервале [a,b] если для любой точки
отрезка, соединяющего точки f(a) и f(b),
справедливо: все точки этого отрезка
расположены под кривой, отображающей
f(x) на этом интервале:
f
a
b
x
20. Определения глобального и локального оптимума
ОПРЕДЕЛЕНИЯ ГЛОБАЛЬНОГО И ЛОКАЛЬНОГООПТИМУМА
Функция называется локально оптимальной
в точке «х» , если все значения в Ɛокрестности этой точки «хуже», чем в точке
х.
Функция достигает в точке х глобального
оптимума, если для любого допустимого
вектора y≠x значение функции «хуже», чем в
«х».
21. Элементы теории Куна-таккера
ЭЛЕМЕНТЫ ТЕОРИИ КУНА-ТАККЕРАТеорема 1. Если целевая функция является выпуклой и
максимизируемой, а область допустимых значений является
непрерывной и выпуклой, то локально оптимальное
решение совпадает с глобально оптимальным.
Теорема 2. Если целевая функция является вогнутой и
минимизируемой, а область допустимых значений
аргументов – выпуклой, то локальный оптимум совпадает с
глобальным.
22. самостоятельно
САМОСТОЯТЕЛЬНООпределить являлись ли решения
задач (1) и (2), полученные выше
спуском по градиенту, глобально
оптимальными.
Проверить, являлись ли решения тех
же задач, полученные методом
множителей Лагранжа, глобально
оптимальными.
23. Поиск по градиенту с изменяемой целевой функцией.
ПОИСК ПО ГРАДИЕНТУ С ИЗМЕНЯЕМОЙ ЦЕЛЕВОЙФУНКЦИЕЙ.
1. Определена задача:
f ( x) min(max);
q j ( x) 0; j 1, m; m число ораничений
2. Осуществляется спуск в лучшем
направлении по градиенту функции f до тех
пор, пока справедливы ограничения. Если
оптимальное значение при этом найдено
внутри допустимой области, то алгоритм
закончен, переход к шагу 6, в противном
случае – к следующему шагу.
24. Шаги 3 – 6 алгоритма
ШАГИ 3 – 6 АЛГОРИТМА3. Пусть J – множество
индексов таких,
j J : q jчто
( x) 0
Строим новую целевую
2
функцию
Н:
H
q ( x)
j J
j
4. Осуществляется спуск по
градиенту в сторону
убывания Н до тех пор, пока
Н не станет меньше 0.
5. Перейти к шагу 2.
25. САМОСТОЯТЕЛЬНО
1.2.
Дать формальное описание градиентного
поиска с изменяемой целевой функцией и
построить блок-схему.
Пользуясь этим методом, решить задачу:
( x 2) 2 ( y 3) 2 min;
2
2
x
y
3;
(3)
x3. Реализовать
метод
программно.
y0 1; начальный
шаг
1; конечный - 0.25.
0
4.
Оценить достоинства и недостатки
метода.