Лабораторная работа № 4
Тема: Выпуклый анализ.
Рассматриваемые вопросы:
— выпуклые функции и множества
— основные свойства выпуклых и вогнутых функций:
— задача выпуклого программирования .
— выпуклая задача оптимизации .
— геометрическая интерпретация выпуклой задачи оптимизации .
— функция Лагранжа задачи выпуклого программирования .
— теоремаКуна – Таккера .
1. Постановка выпуклой задача оптимизации
Выпуклые функции и множества
Функция , заданная на выпуклом множестве Х, называется выпуклой, если для любых двух точек из Х и любого выполняется соотношение
. (1)
Функция , заданная на выпуклом множестве Х, называется вогнутой, если для любых двух точек из Х и любого выполняется соотношение
. (2)
Если неравенства (1) и (2) считать строгими и они выполняются при , то функция является строго выпуклой (строго вогнутой). Выпуклость и вогнутость функций определяется только относительно выпуклых множеств.
Рис. 1.
Если , – выпуклые (вогнутые) функции на некотором выпуклом множестве , то функция ‑ также выпуклая (вогнутая) на Х.
|
|
Основные свойства выпуклых и вогнутых функций:
1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве, ‑ выпукло.
2. Пусть ‑ выпуклая функция, заданная на замкнутом выпуклом множестве . Тогда локальный минимум на Х является и глобальным.
3. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.
4. Если ‑ строго выпуклая функция, то ее глобальный минимум на выпуклом множестве Х достигается в единственной точке.
5. Пусть функция ‑ выпуклая функция, заданная на выпуклом множестве Х, и, кроме того, она непрерывна вместе со своими частными производными первого порядка во всех внутренних точках Х. Пусть – точка, в которой . Тогда в точке достигается локальный минимум, совпадающий с глобальным минимумом.
6. Множество точек глобальных (следовательно, и локальных) минимумов выпуклой функции , заданной на ограниченном замкнутом выпуклом множестве Х, включает хотя бы одну крайнюю точку . если множество локальных минимумов включает в себя хотя бы одну внутреннюю точку множества Х, то является функцией-константой.
Рассмотрим задачу нелинейного программирования
(3)
(4)
(5)
Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций , разработаны эффективные методы их решения.
Говорят, что множество допустимых решений задачи (3)–(5) удовлетворяет условию регулярности, или условию Слейтера, если существует по крайней мере одна точка , принадлежащая области допустимых решений такая, что .
|
|
2. Выпуклая задача оптимизации
Постановка задачи оптимизации: заданы множество Х и функция f (x), определенная на Х . требуется найти точки минимума или максимума функции f на X. Задачу на минимум будем записывать в виде
f(x) ® min, хÎ Х.
Задача называется выпуклой, если X – выпуклое множество, f – выпуклая функция на X.
Пример 1. Пусть дана задача
f(x) = x2 ® min,
, , .
Ее геометрической интерпретацией служит рис.2. Отсюда видно, что решением задачи является «нижняя» точка пересечения окружности g1(x) = 0 и прямой g3(x) = 0, т.е. .
Пример 2 (задача поиска). Объект, подлежащий обнаружению, находится в одном из п районов с вероятностями р1,…, рп соответственно. Для поиска объекта имеется общий ресурс времени Т. Известно, что при поиске в i -м районе в течение времени ti, вероятность обнаружения объекта (при условии, что он там находится) равна , где ai > . 0 – заданное число. Требуется так распределить время наблюдения по районам, чтобы максимизировать вероятность обнаружения объекта. Соответствующая задача оптимизации имеет вид
,
,
ti ³ 0, i = 1, …, n.
Нетрудно проверить, что целевая функция задачи вогнута по t = (t1, …, tn). Переходя к минимизации этой функции, взятой с обратным знаком, получаем задачу выпуклого программирования.
3. Задача выпуклого программирования и функция Лагранжа
Задача (3)–(5) называется задачей выпуклого программирования, если функция является вогнутой (выпуклой), а функции – выпуклыми.
Функцией Лагранжа задачи выпуклого программирования (3)–(5) называется функция
где – множители Лагранжа.
Точка называется седловой точкой функции Лагранжа, если
для всех и .
Теорема Куна – Таккера. Для задачи выпуклого программирования (3)–(5), множество допустимых решений которой обладает свойством регулярности, является оптимальным решением тогда и только тогда, когда существует такой вектор , что – седловая точка функции Лагранжа.
Если предположить, что функции и непрерывно дифференцируемы, то теорема Куна – Таккера может быть дополнена аналитическими выражениями, определяющими необходимые и достаточные условия того, чтобы точка была седловой точкой функции Лагранжа, т. е. являлась решением задачи выпуклого программирования:
где и – значения соответствующих частных производных функции Лагранжа, вычисленных в седловой точке.
Пример 3. Рассмотрим задачу
Точка X °=(2,1) — оптимальный план задачи,
— функция Лагранжа.
Проверим выполнение условий Куна-Таккера:
Легко видеть, что эти условия выполняются на плане X °=(2,1) при .
Таким образом, пара является седловой точкой функции Лагранжа:
Т. е., для любых , и выполняется условие дополняющей нежесткости.
Задание 1. Дана задача выпуклого программирования. Требуется:
1) найти решение графическим методом
2) написать функцию Лагранжа данной задачи и найти ее седловую точку, используя решение задачи, полученное графически.
Задание 2. Самостоятельно сформулировать задачу выпуклого программирования и найти ее решение аналогичным способом.
http://www.matem96.ru/primer/primer_matprogr4.shtml