Выпуклый анализ. Теория двойственности. Лекция 27

Сентябрь 7, 2022

Главная
Алгебра
Выпуклый анализ. Теория двойственности. Лекция 27

Содержание

2. 10. ТЕОРИЯ ДВОЙСТВЕННОСТИ 10.1. Постановка двойственной задачи. 10.2. Теорема двойственности.
3. 10.1. Постановка двойственной задачи. определенную формулой Нетрудно видеть, что неравенство переходит в равенство. Отсюда выводим равенство
4. Тогда исходную задачу можно переписать в виде. Задача 1. и сконструируем задачу. Задача 2. Определение 1.
5. 10.2. Теорема двойственности. основной и двойственной задач. Теорема 1. Имеет место неравенство Доказательство. от обеих частей
6. Теорема доказана. Теорема 2 (двойственности). Для того чтобы было выполнено необходимо и достаточно, Множество седловых точек
7. Последнее равенство означает, что Отсюда также следует, вложено в множество седловых точек функции Лагранжа. Достаточность. седловая
8. выводим Из (7),(6) в силу теоремы 1 получим Тогда Отсюда выводим, что множество седловых точек функции
9. также являются седловыми точками. можно выбирать одними и теми же Тогда множители Лагранжа в теореме Куна
10. Пример 1. Пусть Данная функция имеет единственную седловую точку а Существуют задачи выпуклого программирования, даже если
11. Выпишем функцию Лагранжа для данной задачи Вычисляем Пояснения требует третья строчка в равенстве (8). Приведем график
12. Отсюда и соотношение (8) доказано. Таким образом, но
13. Двойственная задача всегда является задачей выпуклого программирования какой была основная (исходная) задача. Действительно, двойственная задача эквивалентна
15. Двойственная задача к двойственной не обязана совпадать с исходной задачей. Например, если исходная задача не является
17. Скачать презентацию

Слайд 2

10. ТЕОРИЯ ДВОЙСТВЕННОСТИ
10.1. Постановка двойственной задачи.
10.2. Теорема двойственности.

Слайд 3

10.1. Постановка двойственной задачи.
определенную формулой
Нетрудно видеть, что
неравенство переходит

в равенство.

Отсюда выводим равенство

Слайд 4

Тогда исходную задачу можно переписать в виде.
Задача 1.
и сконструируем

задачу.

Задача 2.

Определение 1.

Задача 2 называется двойственной к задаче 1 (основной).

называются основными,

двойственными.

Слайд 5

10.2. Теорема двойственности.
основной и двойственной задач.
Теорема 1.
Имеет место

неравенство

Доказательство.

от обеих частей (1)

Обозначим через

множество всех решений двойственной задачи и

Слайд 6

Теорема доказана.
Теорема 2 (двойственности).
Для того чтобы было выполнено
необходимо

и достаточно,

Множество седловых точек функции Лагранжа

Доказательство. Необходимость.

Пусть выполнены соотношения (3).

Имеем

Переходя в неравенстве (2)

получим

Слайд 7

Последнее равенство означает, что
Отсюда также следует,
вложено в множество седловых

точек функции Лагранжа.

Достаточность.

седловая точка функции Лагранжа.

Тогда

Отсюда следует

Аналогично из неравенства

Тогда из неравенства (4)

следует, что

Слайд 8

выводим
Из (7),(6)
в силу теоремы 1 получим
Тогда
Отсюда выводим, что множество седловых

точек функции Лагранжа

Теорема доказана.

Отсюда, в частности следует, что если пары

образуют седловые точки функции Лагранжа,

то и пары

Слайд 9

также являются седловыми точками.
можно выбирать одними и теми же
Тогда

множители Лагранжа в теореме Куна – Таккера

Замечание.

что исходная задача является задачей выпуклого программирования.

Таким образом,

определенная из условия

не обязана быть седловой точкой.

Слайд 10

Пример 1.
Пусть
Данная функция имеет единственную седловую точку
а
Существуют

задачи выпуклого программирования,

даже если

Пример 2.

Пусть

Тогда

и

Слайд 11

Выпишем функцию Лагранжа для данной задачи
Вычисляем
Пояснения требует третья строчка

в равенстве (8).

Приведем график функции

Найдем минимизирующую точку

Имеем

Слайд 12

Отсюда
и соотношение (8) доказано.
Таким образом,
но

Слайд 13

Двойственная задача всегда является задачей выпуклого программирования
какой была основная (исходная)

задача.

Действительно, двойственная задача

эквивалентна задаче

Имеем

справедливо

Слайд 14

Слайд 15

Двойственная задача к двойственной не обязана совпадать с исходной задачей.
Например, если

исходная задача не является задачей выпуклого программирования.