Численный анализ нелинейных моделей и теория Куна-Таккера (Лекция 5)

Сентябрь 14, 2022

Главная
Математика
Численный анализ нелинейных моделей и теория Куна-Таккера (Лекция 5)

Содержание

2. СОДЕРЖАНИЕ Текущий контроль Методы наискорейшего спуска (спуск по градиенту) Элементы теории Куна-Таккера
3. ТЕКУЩИЙ КОНТРОЛЬ 1 Выбрать оптимальную архитектуру обсерватории, корпус которой является цилиндрическим, а раздвижная крыша может быть
4. ТЕКУЩИЙ КОНТРОЛЬ 2 РЕШИТЬ МЕТОДОМ МНОЖИТЕЛЕЙ ЛАГРАНЖА i-порядковый номер студента.
5. ПОСТАНОВКА ЗАДАЧИ Задана нелинейная однокритериальная оптимизационная модель вида: Все функции системы (1) являются гладкими и дифференцируемыми,
6. СПУСК ПО ГРАДИЕНТУ – ИДЕЯ МЕТОДА Суть метода – в движении от одной точки к другой
7. АЛГОРИТМ СПУСКА ПО ГРАДИЕНТУ – ПЕРВЫЕ ДВА ШАГА (ВСЕГО 10 ШАГОВ) Шаг 1. Вычисляется значение функции
8. АЛГОРИТМ СПУСКА ПО ГРАДИЕНТУ – СЛЕДУЮЩИЕ ЧЕТЫРЕ ШАГА Шаг 3. Вычисляется новое значение целевой функции f₁.
9. ПОСЛЕДНИЕ ЧЕТЫРЕ ШАГА АЛГОРИТМА Шаг 7. Старые значения переменных заменяются на новые, полученные на шаге 2
10. ПРИМЕР 1 Пользуясь спуском по градиенту решить задачу: Точка старта: х=у=3; f=0,66, начальная величина шага β=1,
11. РЕШЕНИЕ 1) z=0,8. Новые значения переменных удовлетворяют ограничениям, f=0,8, поэтому величина шага β не меняется.
12. РЕШЕНИЕ – ВТОРАЯ ИТЕРАЦИЯ 2) Ограничения не выполняются, поэтому величина шага β уменьшается в два раза:
13. РЕШЕНИЕ – ТРЕТЬЯ ИТЕРАЦИЯ 3) Ограничения выполняются, новое значение целевой функции f = 0,888.
14. РЕШЕНИЕ – ЧЕТВЕРТАЯ ИТЕРАЦИЯ 4) Так как ограничения не выполняются, то шаг уменьшается в 2 раза:
15. РЕШЕНИЕ – ПЯТАЯ ИТЕРАЦИЯ 5) Ограничения выполняются, f = 0,9411.
16. РЕШЕНИЕ – ШЕСТАЯ ИТЕРАЦИЯ 6) Значения переменных не удовлетворяют ограничению, шаг β уменьшается в два раза,
17. САМОСТОЯТЕЛЬНО Пользуясь приведенным выше алгоритмом решить задачу (2): Решить задачи (1) и (2), пользуясь методом множителей
18. ОПРЕДЕЛЕНИЕ ВЫПУКЛЫХ ФУНКЦИЙ Функция f называют выпуклой на интервале [a,b] если для любой точки отрезка, соединяющего
19. ОПРЕДЕЛЕНИЕ ВОГНУТЫХ ФУНКЦИЙ Функция f называют вогнутой на интервале [a,b] если для любой точки отрезка, соединяющего
20. ОПРЕДЕЛЕНИЯ ГЛОБАЛЬНОГО И ЛОКАЛЬНОГО ОПТИМУМА Функция называется локально оптимальной в точке «х» , если все значения
21. ЭЛЕМЕНТЫ ТЕОРИИ КУНА-ТАККЕРА Теорема 1. Если целевая функция является выпуклой и максимизируемой, а область допустимых значений
22. САМОСТОЯТЕЛЬНО Определить являлись ли решения задач (1) и (2), полученные выше спуском по градиенту, глобально оптимальными.
23. ПОИСК ПО ГРАДИЕНТУ С ИЗМЕНЯЕМОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ. 1. Определена задача: 2. Осуществляется спуск в лучшем направлении
24. ШАГИ 3 – 6 АЛГОРИТМА 3. Пусть J – множество индексов таких, что Строим новую целевую
26. Скачать презентацию

Слайд 2

СОДЕРЖАНИЕ
Текущий контроль
Методы наискорейшего спуска (спуск по градиенту)
Элементы теории Куна-Таккера

Слайд 3

ТЕКУЩИЙ КОНТРОЛЬ 1
Выбрать оптимальную архитектуру обсерватории, корпус которой является цилиндрическим, а

раздвижная крыша может быть полусферической или конической. Объем обсерватории равен V, минимизируется расход материала на ее стены, основание и крышу. Для высоты и радиуса цилиндра и конуса определены нижние границы.

h1
d
h2

d/2

Слайд 4

ТЕКУЩИЙ КОНТРОЛЬ 2 РЕШИТЬ МЕТОДОМ МНОЖИТЕЛЕЙ ЛАГРАНЖА
i-порядковый номер студента.

Слайд 5

ПОСТАНОВКА ЗАДАЧИ
Задана нелинейная однокритериальная оптимизационная модель вида:
Все функции системы (1) являются

гладкими и дифференцируемыми, известно одно допустимое значение
Вектора переменных. Требуется определить оптимальный вектор переменных.

Слайд 6

СПУСК ПО ГРАДИЕНТУ – ИДЕЯ МЕТОДА
Суть метода – в движении от

одной точки к другой в направлении экстремума:

х₁

х₂

Стартовая точка

касательные

Слайд 7

АЛГОРИТМ СПУСКА ПО ГРАДИЕНТУ – ПЕРВЫЕ ДВА ШАГА (ВСЕГО 10 ШАГОВ)

Шаг 1. Вычисляется значение функции f в стартовой точке.
Шаг 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
Пользуясь спуском по градиенту решить задачу:
Точка старта: х=у=3; f=0,66, начальная

величина шага β=1, конечная величина шага γ=0,25.

Слайд 11

РЕШЕНИЕ
1)
z=0,8.
Новые значения переменных удовлетворяют ограничениям, f=0,8, поэтому величина шага β

не меняется.

Слайд 12

РЕШЕНИЕ – ВТОРАЯ ИТЕРАЦИЯ
2)
Ограничения не выполняются, поэтому величина шага β

уменьшается в два раза: β=β/2=0,5. Возврат в точку старта, найденную на первой итерации.

Слайд 13

РЕШЕНИЕ – ТРЕТЬЯ ИТЕРАЦИЯ
3)
Ограничения выполняются, новое значение целевой функции f =

0,888.

Слайд 14

РЕШЕНИЕ – ЧЕТВЕРТАЯ ИТЕРАЦИЯ
4)
Так как ограничения не выполняются, то шаг уменьшается

в 2 раза: β=0,25.

Слайд 15

РЕШЕНИЕ – ПЯТАЯ ИТЕРАЦИЯ
5)
Ограничения выполняются, f = 0,9411.

Слайд 16

РЕШЕНИЕ – ШЕСТАЯ ИТЕРАЦИЯ
6)
Значения переменных не удовлетворяют ограничению, шаг β уменьшается

в два раза, но при этом он становится меньше, чем γ, поэтому поиск прекращается. x=у=2,125; f=0,9411.

Слайд 17

САМОСТОЯТЕЛЬНО
Пользуясь приведенным выше алгоритмом решить задачу (2):
Решить задачи (1) и (2),

пользуясь методом множителей Лагранжа и сравнить результаты.
Сформулировать достоинства и недостатки спуска по градиенту.

Слайд 18

ОПРЕДЕЛЕНИЕ ВЫПУКЛЫХ ФУНКЦИЙ
Функция f называют выпуклой на интервале [a,b] если для

любой точки отрезка, соединяющего точки f(a) и f(b), справедливо: все точки этого отрезка расположены над кривой, отображающей f(x) на этом интервале:
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. Определена задача:
2. Осуществляется

спуск в лучшем направлении по градиенту функции f до тех пор, пока справедливы ограничения. Если оптимальное значение при этом найдено внутри допустимой области, то алгоритм закончен, переход к шагу 6, в противном случае – к следующему шагу.

Слайд 24

ШАГИ 3 – 6 АЛГОРИТМА
3. Пусть J – множество индексов таких,

что
Строим новую целевую функцию Н:
4. Осуществляется спуск по градиенту в сторону убывания Н до тех пор, пока Н не станет меньше 0.
5. Перейти к шагу 2.
6. Конец алгоритма.

Численный анализ нелинейных моделей и теория Куна-Таккера (Лекция 5)

Содержание

СОДЕРЖАНИЕТекущий контрольМетоды наискорейшего спуска (спуск по градиенту)Элементы теории Куна-Таккера

ТЕКУЩИЙ КОНТРОЛЬ 1Выбрать оптимальную архитектуру обсерватории, корпус которой является цилиндрическим, а

ТЕКУЩИЙ КОНТРОЛЬ 2 РЕШИТЬ МЕТОДОМ МНОЖИТЕЛЕЙ ЛАГРАНЖАi-порядковый номер студента.

ПОСТАНОВКА ЗАДАЧИЗадана нелинейная однокритериальная оптимизационная модель вида:Все функции системы (1) являются

СПУСК ПО ГРАДИЕНТУ – ИДЕЯ МЕТОДАСуть метода – в движении от

АЛГОРИТМ СПУСКА ПО ГРАДИЕНТУ – ПЕРВЫЕ ДВА ШАГА (ВСЕГО 10 ШАГОВ)

АЛГОРИТМ СПУСКА ПО ГРАДИЕНТУ – СЛЕДУЮЩИЕ ЧЕТЫРЕ ШАГА Шаг 3. Вычисляется

ПОСЛЕДНИЕ ЧЕТЫРЕ ШАГА АЛГОРИТМАШаг 7. Старые значения переменных заменяются на новые,

ПРИМЕР 1Пользуясь спуском по градиенту решить задачу:Точка старта: х=у=3; f=0,66, начальная

РЕШЕНИЕ1) z=0,8.Новые значения переменных удовлетворяют ограничениям, f=0,8, поэтому величина шага β

РЕШЕНИЕ – ВТОРАЯ ИТЕРАЦИЯ2) Ограничения не выполняются, поэтому величина шага β

РЕШЕНИЕ – ТРЕТЬЯ ИТЕРАЦИЯ3)Ограничения выполняются, новое значение целевой функции f =

РЕШЕНИЕ – ЧЕТВЕРТАЯ ИТЕРАЦИЯ4)Так как ограничения не выполняются, то шаг уменьшается

РЕШЕНИЕ – ПЯТАЯ ИТЕРАЦИЯ5)Ограничения выполняются, f = 0,9411.

РЕШЕНИЕ – ШЕСТАЯ ИТЕРАЦИЯ6)Значения переменных не удовлетворяют ограничению, шаг β уменьшается

САМОСТОЯТЕЛЬНОПользуясь приведенным выше алгоритмом решить задачу (2):Решить задачи (1) и (2),

ОПРЕДЕЛЕНИЕ ВЫПУКЛЫХ ФУНКЦИЙФункция f называют выпуклой на интервале [a,b] если для

ОПРЕДЕЛЕНИЕ ВОГНУТЫХ ФУНКЦИЙФункция f называют вогнутой на интервале [a,b] если для

ОПРЕДЕЛЕНИЯ ГЛОБАЛЬНОГО И ЛОКАЛЬНОГО ОПТИМУМАФункция называется локально оптимальной в точке «х»

ЭЛЕМЕНТЫ ТЕОРИИ КУНА-ТАККЕРАТеорема 1. Если целевая функция является выпуклой и максимизируемой,

САМОСТОЯТЕЛЬНООпределить являлись ли решения задач (1) и (2), полученные выше спуском

ПОИСК ПО ГРАДИЕНТУ С ИЗМЕНЯЕМОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ. 1. Определена задача:2. Осуществляется

ШАГИ 3 – 6 АЛГОРИТМА3. Пусть J – множество индексов таких,

Похожие презентации