ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ
Мы будем рассматривать экстремальные задачи в конечномерных евклидовых пространствах, хотя все приведенные ниже формулировки и доказательства справедливы и для банаховых пространств с выпуклым телесным конусом.
Определение 1. Множество 
линейного пространства
называется выпуклым,
если для любых 
и 
справедливо: 
.▄
Определение 2. Вектор-функцию 
, определенную на выпуклом
подмножестве линейного пространства 
со значениями в линейном пространстве 
, будем называть выпуклой, если для любых и 
из области допустимых значений функции 
справедливо:
.▄
(В случае банаховых пространств неравенства 
понимаются как
принадлежность конусу 
.)
В теории экстремальных задач важную роль играют теоремы отделимости. Здесь мы приведем без доказательства одну из них.
Теорема 1. Пусть - выпуклое множество в , имеющее внутреннюю точку (т.е., найдется точка 
, принадлежащая
множеству вместе с некоторой
своей 
-окрестностью: из 
следует 
.), и точка 
не принадлежит внутренности множества . (Т.е., в любой
окрестности точки найдется точка, не
принадлежащая .) Тогда найдется ненулевой линейный функционал 
, (в конечномерном пространстве линейный функционал - это просто элемент ) отделяющий точку от множества , т.е. такой, что для любого справедливо: 
.▄
Задача выпуклого программирования
Пусть 
- определенная на скалярная выпуклая функция, а
выпуклая вектор-функция действует из в . Рассмотрим следующую задачу:
Задача 1.
▄
Определение 3. Скажем, что ограничения
задачи 1 удовлетворяют условию Слейтера, если найдется 
такой, что 
.▄
Теорема 2 (Куна-Таккера).
Пусть ограничения задачи 1 удовлетворяют условию Слейтера, и - ее решение. Тогда найдется линейный функционал 
, определенный на , такой что справедливо:
|
|
(1) |
|
|
(2) |
Равенство (2) часто называют условием дополняющей нежесткости.
Доказательство.
Построим в 
следующее множество 
:
|
|
(3) |
- - выпуклое множество. Действительно,
пусть
, пусть - соответствующие им в силу (3) элементы , пусть . Тогда
и 
, следовательно, точка 
также принадлежит . - имеет внутреннюю точку. Действительно, положим в (3)
, тогда точка 
принадлежит
множеству . Следовательно, любая точка 
принадлежит
множеству с некоторой окрестностью. - Точка
не является
внутренней точкой множества . Предположим противное, тогда в силу (3) найдется 
такой что 
, а это противоречит исходному предположению теоремы о
том, что решение задачи 1.
Следовательно, к множеству и точке применима теорема отделимости
(Теорема 1), и найдется определенный на линейный функционал 
, причем
|
|
(4) |
такой что
|
|
(5) |
Из (5) следует, что 
. Действительно, пусть 
. Точка 
, например, при . Тогда 
, что противоречит (5). Также при
, любая точка вида 
. Следовательно 
, отсюда 
.
Из (3)
следует, что для любого 
точка 
принадлежит . Отсюда и из (5) следует:
|
|
(6) |
Из условия Слейтера следует, что 
. Действительно, предположим противное, т.е., что 
, тогда из (4) следует 
, отсюда, из и из условия Слейтера
следует 
, что противоречит (6). Раз , мы можем разделить неравенство (6) на 
и перенести свободный член в его правую часть, после чего и
получаем искомое соотношение (1). Если в (1) положить , получим 
. С другой стороны, из 
и заключаем: 
, что в совокупности и дает (2). Теорема доказана. ▄
Теорема 3. (Достаточные условия минимума) Пусть
точка из области допустимых значений задачи 1 и линейный функционал
, определенный на таковы, что выполняется (1). Тогда - решение задачи 1.
Доказательство.
Предположим противное. Пусть 
и 
. Тогда из и заключаем: 
, отсюда тем более 
, что противоречит (1). Полученное противоречие и доказывает
теорему. ▄
Определение 4. Функция 
, где 
; 
; а 
и 
- выпуклые функции из постановки задачи 1, называется
функцией Лагранжа задачи 1, а компоненты вектора 
- множителями Лагранжа. ▄
Теорема 4. Точка 
, где 
- решение задачи 1, а 
- соответствующий ему линейный функционал, существующий в
силу теоремы Куна-Таккера, есть седловая
точка функции Лагранжа, т.е. выполняется
|
|
(7) |
Доказательство.
Прибавим к правой части неравенства (1) равную нулю левую часть равенства (2),
получаем: 
. Пусть теперь 
. Из соотношений (2) и заключаем: 
, отсюда и 
, что и завершает доказательство теоремы. ▄
Справедливо и обратное утверждение.
Теорема 5. Пусть точка , где 
, а 
и , является седловой точкой функции Лагранжа задачи 1, т.е., для выполняется соотношение (7). Тогда - решение задачи 1, а для вектора выполняются соотношения (1) и (2).
Доказательство.
Из левого неравенства соотношения (7) следует 
. Последнее может быть справедливо лишь если . Действительно, если не выполняется , то найдется 
такой что 
, и, следовательно, неравенство 
не может быть справедливо например для 
при
достаточно больших 
. Полагая теперь 
в соотношении , получаем . Отсюда, и из неотрицательности следует 
, т.е., выполняется уравнение дополняющей нежесткости
(2). Подставляя (2) в соотношение , получаем (1). По теореме 3, соотношение (1) является
достаточным условием экстремальности точки . Теорема доказана. ▄
Двойственнось в задачах линейного программирования
Рассмотрим задачу линейного программирования в стандартной постановке.
Задача 2.
,
.
Здесь 
- линейный
оператор, действующий из в .▄
Линейный
функционал 
, аффинный оператор 
, и линейный оператор 
, где 
- единичный линейный оператор, действующий из в , являются
выпуклыми, поэтому к задаче 2 можно применить результаты, полученные для
выпуклых задач. Для этого перепишем задачу 2 в виде, соответствующем постановке
задачи 1.
Задача 2а.
,
,
.▄
Условие Слейтера для задачи 2а будет
состоять в существовании , такого что 
.
Запишем для задачи 2а функцию Лагранжа:
|
|
(8) |
Пусть для задачи 2а выполнено
условие Слейтера и - ее решение, тогда из теорем предыдущего раздела следует,
что найдутся 
, такие что, 
- седловая точка функции Лагранжа,
т.е., для любых 
выполняется 
, или, умножая на 
,
|
|
(9) |
Положим в левой части (9) 
, получаем 
. Но, как мы знаем, 
, отсюда заключаем: 
. Положим теперь в (9) 
, тогда справедливо:
|
|
(10) |
или, что то же самое,
|
|
(11) |
Здесь 
- линейный оператор, сопряженный 
. (В конечномерном случае это просто транспонированная
матрица). Соотношения (10) и (11) означают, что - седловая точка функции
|
|
(12) |
,определенной
на множестве 
.
Определение 5. Функцию (12) будем называть функцией Лагранжа стандартной задачи линейного программирования. ▄
Сформулируем теперь полученный результат в виде теоремы.
Теорема 6. Пусть - доставляет решение задаче 2, для которой выполнено условие
Слейтера. Тогда найдется вектор 
такой, что точка будет седловой точкой
функции Лагранжа (12) стандартной задачи линейного программирования 2:
.▄
Пусть теперь,
- седловая точка функции Лагранжа
(12) задачи 2.
Из левого неравенства соотношения (10) следует
|
|
(13) |
Соотношение (13) может
выполняться лишь если 
. Действительно, если не выполнено , обязательно найдется вектор 
, такой что 
, отсюда следует, что скалярное произведение 
не ограничено снизу на множестве , и мы приходим к противоречию с (13). Следовательно, - допустимый элемент задачи 2. Далее, полагая в (13) , получаем 
, отсюда, из и получаем соотношение
дополняющей нежесткости:
|
|
(14) |
Аналогично, из правого неравенства соотношения (11) следует:
, откуда можно заключить:
|
|
(15) |
|
|
(16) |
Далее, из (12), (14) и (16) заключаем:
|
|
(17) |
Если 
- произвольный допустимый элемент задачи 2, т.е., 
, из правого неравенства соотношения (10) заключаем: 
, т.е., доставляет решение задаче
2.
Аналогично,
если 
и 
, то из левого неравенства соотношения (11) заключаем: 
, т.е., доставляет решение следующей задаче линейного
программирования:
Задача 3.
,
.
Где 
, векторы 
и 
те же самые, что и в
задаче 2, а оператор 
сопряжен оператору задачи 2.▄
Определение 6. Задача 3 называется двойственной или сопряженной по отношению к задаче 2. Исходную задачу по отношению к двойственной называют прямой. ▄
Отношение двойственности, связывающее задачу 2 и задачу 3, в конечномерных пространствах симметрично. В банаховых пространствах этой симметрии может и не быть, она имеет место лишь в так называемых рефлексивных банаховых пространствах. Попробуйте повторить выкладки этого раздела, взяв в качестве прямой задачу 3. В качестве двойственной получится задача 2.
Сформулируем полученные выше результаты в виде достаточного условия оптимальности для задач линейного программирования.
Теорема 7. Пусть функция Лагранжа (12)
задач линейного программирования 2 и 3 имеет седловую
точку , такую что выполнено (10) или (11), тогда обе задачи 2 и 3
имеют решения, точка доставляет решение
задаче 2, а точка - решение задаче 3, причем выполняются условия дополняющей нежесткости (14) и (16). ▄
Приведем еще достаточные условия существования экстремума для задач линейного программирования.
Теорема 8. Пусть -допустимые элементы задач 2 и 3 соответственно, такие
что для них выполняются условия дополняющей нежесткости
(14) и (16). Тогда точка является седловой точкой функции Лагранжа (12).
Доказательство.
, т.к. если - допустимый элемент задачи 3, то 
. Аналогично,
, т.к. если - допустимый элемент задачи 2, то 
. И, наконец, 
, что следует из определения функции Лагранжа (12) и
выполнения условий дополняющей нежесткости (14) и
(16). ▄
Теорема 9. Пусть 
-допустимые элементы задач 2 и 3 соответственно, тогда
. Если же для допустимых выполнено , то является седловой
точкой функции Лагранжа (12).
Доказательство.
Пусть -допустимые элементы задач 2 и 3 соответственно. В
функции Лагранжа 
всегда 
, а 
, следовательно, для любых допустимых справедливо . Пусть теперь для допустимых выполнено .
Из 
заключаем:
, но 
, а 
, следовательно, выполняются соотношения дополняющей нежесткости (14) и (16), и по теореме 8, - седловая точка функции Лагранжа
(12). ▄
Следствие. Двойственные задачи линейного программирования либо обе имеют решения, либо обе решений не имеют. Если значение одной из задач неограниченно на множестве ее допустимых элементов, то у двойственной задачи не может быть допустимых элементов. ▄