Условная оптимизация Функция Лагранжа

Сентябрь 2, 2022

Главная
Алгебра
Условная оптимизация Функция Лагранжа

Содержание

2. 09/02/2023 Постановка задач Найти минимум функции При ограничениях
3. 09/02/2023 Понятие функции Лагранжа Вначале на простом примере функции двух переменных рассмотрим какие условия в точке
4. 09/02/2023 Получение Условия минимума Вдоль кривой имеет место очевидное соотношение
5. 09/02/2023 Получение Условия минимума Запишем условие минимума для функции Вдоль кривой y=y(x) имеем
6. 09/02/2023 Условия минимума λ– множитель Лагранжа обозначим Получаем Преобразуем
7. 09/02/2023 Необходимые Условия минимума Таким образом в точке минимума f(x,y) на кривой g(x,y)=0 выполняются три условия:
8. 09/02/2023 введем функцию Лагранжа Для нее условия экстремума которые мы выше вывели получаются естественным образом
9. 09/02/2023 Рассмотрим простой пример Функция Лагранжа Условия экстремума Решение x=2; y=2; λ=4.
10. 09/02/2023 анализ, вблизи точки экстремума точка экстремума функции Лагранжа представляет седловую точку, в которой достигается минимум
11. 09/02/2023 функция Лагранжа для нескольких ограничений в виде неравенств Условие регулярности: Существует точка в которой все
12. 09/02/2023 Теорема о седловой точке Куна-Таккера В точке минимума при указанных ограничениях существует такой набор при
13. 09/02/2023 Графическое представление седловой точки
14. 09/02/2023 Условия дополнительности Если пара является седловой точкой функции Лагранжа, то выполняются условия дополнительности: Это значит,
15. 09/02/2023 Понятие двойственности Допустим, что у функции Лагранжа седловая точка существует Положим Аналогично Из свойства седловой
16. 09/02/2023 Рассмотрим простой пример Из условия дополнительности
17. 09/02/2023 Двойственная задача
18. 09/02/2023 Задача линейного программирования
19. 09/02/2023 Затраты: xj - количество Пример: Имеются три продукта П1,П2,П3 разной цены, каждый из которых содержит
20. 09/02/2023 function LinProgr1; %Задание цены продуктов c=[44; 35; 100]; % Матрица ограничений A=[4 6 15 2
21. 09/02/2023 Задача квадратичного программирования
22. 09/02/2023 Задача о рисках Нужно вложить некоторую сумму в различные предприятия А1,А2,А3,А4 с целью получить желаемую
23. 09/02/2023 Решение МатЛаб function quadrogr1; % матрица квадратичной формы C=[102 27 -52 66 27 148 42
25. Скачать презентацию

Слайд 2

09/02/2023
Постановка задач
Найти минимум функции
При ограничениях

Слайд 3

09/02/2023
Понятие функции Лагранжа
Вначале на простом примере функции двух переменных рассмотрим

какие условия в точке минимума имеют место и как их проще получить
Целевая функция
Ограничение
Условный минимум лежит
на кривой, описываемой
уравнением ,
которое неявно определяет
зависимость y=y(x)

Слайд 4

09/02/2023
Получение Условия минимума
Вдоль кривой
имеет место очевидное соотношение

Слайд 5

09/02/2023
Получение Условия минимума
Запишем условие минимума для функции
Вдоль кривой y=y(x)
имеем

Слайд 6

09/02/2023
Условия минимума
λ– множитель Лагранжа
обозначим
Получаем
Преобразуем

Слайд 7

09/02/2023
Необходимые Условия минимума
Таким образом в точке
минимума f(x,y)
на кривой g(x,y)=0
выполняются
три условия:

Слайд 8

09/02/2023
введем функцию Лагранжа
Для нее условия экстремума которые мы выше вывели

получаются естественным образом

Слайд 9

09/02/2023
Рассмотрим простой пример
Функция Лагранжа
Условия экстремума
Решение x=2; y=2; λ=4.

Слайд 10

09/02/2023
анализ, вблизи точки экстремума
точка экстремума функции Лагранжа представляет седловую точку,

в которой достигается минимум по переменным xy и максимум по переменной λ

Сечение функции Лагранжа
при y=2

Слайд 11

09/02/2023
функция Лагранжа для нескольких ограничений в виде неравенств
Условие регулярности:
Существует точка в

которой все ограничения обращаются в строгие неравенства

Слайд 12

09/02/2023
Теорема о седловой точке Куна-Таккера
В точке минимума при указанных ограничениях существует

такой набор
при котором для всех выполняется
Точка является седловой

Слайд 13

09/02/2023
Графическое представление седловой точки

Слайд 14

09/02/2023
Условия дополнительности
Если пара является седловой точкой функции Лагранжа, то выполняются условия

дополнительности:
Это значит, что для тех ограничений, на которых не лежит точка минимума, соответствующий множитель лагранжа равен нулю
При этом

Слайд 15

09/02/2023
Понятие двойственности
Допустим, что у функции Лагранжа седловая точка существует
Положим
Аналогично
Из свойства

седловой точки
Или
Т.е можно вместо минимума находить максимум

Слайд 16

09/02/2023
Рассмотрим простой пример
Из условия дополнительности

Слайд 17

09/02/2023
Двойственная задача

Слайд 18

09/02/2023
Задача линейного программирования

Слайд 19

09/02/2023
Затраты: xj - количество
Пример: Имеются три продукта П1,П2,П3 разной цены, каждый

из которых содержит определенное количество питательных ингридиентов И1,И2,И3,И4. Известно, что в день требуется употребить : И1 – не менее 250, И2 ≥ 60, И3 ≥100, И4≥200. цена: П1=44, П2=35, П3=100. Требуется минимизировать затраты на приобретение П

Питательность, или содержание Иi в Пj

Слайд 20

09/02/2023
function LinProgr1;
%Задание цены продуктов
c=[44; 35; 100];
% Матрица ограничений
A=[4 6 15
2

2 0
5 3 4
7 3 12];
A=-A;
b=[250; 60; 100; 220];
b=-b;
xm=[0; 0; 0];
% Обращение к стандартной программе
[x,p]=linprog(c,A,b,[],[],xm)
return

Результат
x =
13.2143
16.7857
6.4286
p =
1.8118e+003

Решение в МатЛаб

Слайд 21

09/02/2023
Задача квадратичного программирования

Слайд 22

09/02/2023
Задача о рисках
Нужно вложить некоторую сумму в различные предприятия А1,А2,А3,А4 с

целью получить желаемую доходность с минимальным риском.
Доли вкладов : x1+x2+x3+x4=1; xi≥0
Доходности Аi: y1 y2 y3 y4 и матрица ковариации V
Тогда доходность и риски вычисляются по формулам:

Задача:

Слайд 23

09/02/2023
Решение МатЛаб
function quadrogr1;
% матрица квадратичной формы
C=[102 27 -52 66
27

148 42 -66
-52 42 246 57
66 -66 57 272];
% матрицы ограничений
Ae=[11 13 16 17.5;
1 1 1 1 ];
be=[15; 1];
xm=[0; 0; 0];
% Обращение к стандартной пр-ме
[x,p]=quadprog(C,[],[],[],Ae,be,xm)
return

Результат:
Optimization terminated.
x =
0.0413
0.4511
0.1341
0.3734
p =
31.8349

Условная оптимизация Функция Лагранжа

Содержание

09/02/2023Постановка задачНайти минимум функцииПри ограничениях

09/02/2023Понятие функции Лагранжа Вначале на простом примере функции двух переменных рассмотрим

09/02/2023Получение Условия минимумаВдоль кривой имеет место очевидное соотношение

09/02/2023Получение Условия минимумаЗапишем условие минимума для функцииВдоль кривой y=y(x) имеем

09/02/2023Условия минимумаλ– множитель ЛагранжаобозначимПолучаемПреобразуем

09/02/2023Необходимые Условия минимумаТаким образом в точкеминимума f(x,y) на кривой g(x,y)=0выполняютсятри условия:

09/02/2023введем функцию Лагранжа Для нее условия экстремума которые мы выше вывели

09/02/2023Рассмотрим простой пример Функция ЛагранжаУсловия экстремумаРешение x=2; y=2; λ=4.

09/02/2023анализ, вблизи точки экстремума точка экстремума функции Лагранжа представляет седловую точку,

09/02/2023функция Лагранжа для нескольких ограничений в виде неравенствУсловие регулярности:Существует точка в

09/02/2023Теорема о седловой точке Куна-ТаккераВ точке минимума при указанных ограничениях существует

09/02/2023Графическое представление седловой точки

09/02/2023Условия дополнительностиЕсли пара является седловой точкой функции Лагранжа, то выполняются условия

09/02/2023Понятие двойственностиДопустим, что у функции Лагранжа седловая точка существуетПоложимАналогично Из свойства

09/02/2023Рассмотрим простой примерИз условия дополнительности

09/02/2023Двойственная задача

09/02/2023Задача линейного программирования

09/02/2023Затраты: xj - количествоПример: Имеются три продукта П1,П2,П3 разной цены, каждый

09/02/2023function LinProgr1;%Задание цены продуктовc=[44; 35; 100];% Матрица ограниченийA=[4 6 15 2

09/02/2023Задача квадратичного программирования

09/02/2023Задача о рискахНужно вложить некоторую сумму в различные предприятия А1,А2,А3,А4 с

09/02/2023Решение МатЛабfunction quadrogr1;% матрица квадратичной формы C=[102 27 -52 66 27

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