-
Минимум выпуклой функции.
Замечание: Выпуклые функции не имеют локальных минимумов.
Теорема
1.
Если
выпукла на D(выпуклом), то любая точка
локального min одновременно является ее
глобальным минимумом и
выпукло. Если f строго выпукло, то D*
содержит не более одной точки.
Доказательство.
Пусть
x*
locmin
f
(из
выпуклости D)
Из выпуклости
или
является
глобальным.
Пусть
-выпукло.
Если
,то
для строго выпуклых функций предыдущее
неравенством не может превратиться в
равенство и они не могут достигать
минимум более чем в одной точке.
Теорема
2.
Если
выпукла на выпуклом множестве D и
то
(1)
и
если
то
(1)
превращается
в равенство. Если кроме того
выпукла на D, то (1)
является
достигнутым условием, чтобы
.Для
недифференцируемых функций критерий
вводится
с использованием понятия субградиента.
Опр.1.
Пусть
.
Вектор
называется субградиентом
в
,
если
.
(2)
Замечание:
множество всех субградиентов
в
и обозначается
,
а (2) означает, что график
лежит не ниже графика линейной функции
,
определенной равенством
.
Теорема
3.
Если
выпукла
на выпуклом
и
,
то
.
Доказательство:
(следует
из Т1, п.3.2). Обратное вложение: т.к.
и из (2)
и
выполняется
(3)
а
условие
влечет
для всех малых
,
и подставляя
в (3) получаем
.
ч.т.д.
Замечание: субдифференциал не пуст в каждой точке области определения выпуклой функции.
Теорема
4:
Пусть
.
Точка
является точкой
на
.
Док-во:
Неравенство
(4)
имеет место, если
-
точка
на
.
Оно влечет за собой
.
Обратно, условие (4) означает, что
принадлежит субдифференциалу
в
.
Это означает, что
- точка
на
.
-
Функция Лагранжа и седловая точка.
Пусть
Опр.1.
определенная формулой
называется регулярной функцией Лагранжа
для задачи выпуклого программирования
(ВП).
Опр.
2.
Пара
называется Седловой точкой для задачи
ВП, если
(1)
Теорема
1.
седловая точка для
1)
,
2)
Доказательство
Необходимость
-
седловая точка, тогда из (1) следует 1).
Перепишем в (1) левое неравенство
и тогда
(2). Покажем, что
.
Построим вектор
если
если
.
.
Подставляя
в (2), получаем
.
Условие
2) для
доказано; докажем его для
.Построим
вектор
полагая
.
Из (2)
учитывая
следует выполнение 2) для
.
Достаточность.
Пусть для
выполняются 1) и 2). Правое неравенство
в (1) выполняется. Покажем выполнение
левого. Из
а из 2)
если
Суммируя неравенства, переходим к
требуемому неравенству.
Замечание.
Т.к. в фиксированной точке
на оптимальные свойства целевой функции
в некоторой окрестности точки
влияют лишь те ограничения, для которых
выполняется условие
,
то вводится понятие активного ограничения
в
активно в
,
если
.
Теорема
2.
Пусть пара
есть седловая точка для функции Лагранжа
в задаче ВП, тогда
.
Доказательство
Из
(Т.1)
(3)
(3)
верно и для
.
Тогда
и из (3) следует
.