‹-- Назад
Выпуклые множества и функции
Выше мы дали определение выпуклого множества: напомним, что множество 
-- выпуклое, если вместе с любыми двумя точками 
множеству 
принадлежат все точки 
отрезка, соединяющего в пространстве 
точку 
с точкой 
. Заметим, что отрезок, состоящий из точек , можно параметризовать следующим образом: 
Тогда при 
будет получаться точка 
, при 
-- точка 
, а при 
-- промежуточные точки отрезка, так что обозначения точек отрезка как будут согласованы с обозначениями его концов.
На следующем рисунке изображены два множества на плоскости 
: одно выпуклое, а другое нет.
Выпуклыми в пространстве
являются, например, такие множества: всё пространство , его положительный октант 
и неотрицательный октант 
, любой шар, как открытый 
, так и замкнутый 
, любая гиперплоскость 
(заданная некоторым уравнением вида 
, а также открытое и замкнутое полупространства, заданные, соответственно, условиями 
и 
.
Заметим также, что, согласно определению, выпуклы также все одноточечные множества 
и пустое множество 
.
некоторого семейства 
выпуклы, то выпукло и их пересечение
Доказательство. Пусть точки и принадлежат ; тогда обе они принадлежат каждому из множеств 
. Значит, если -- произвольная точка отрезка, соединяющего и , то она принадлежит , поскольку выпукло. Но так как 
для всех 
, то 
, что и требовалось доказать.
Из этой теоремы следует, например, что прямая в 
-мерном пространстве (её можно задать как векторным уравнением: 
, где 
-- фиксированные векторы, а 
-- параметр, так и в виде пересечения гиперплоскостей 
) является выпуклым множеством. Действительно, каждая гиперплоскость 
-- выпуклое множество.
Проколотая окрестность любой точки 
, то есть множество 
( 
), не является выпуклым. Чтобы показать это, достаточно выбрать любой ненулевой вектор 
длины меньше 
и рассмотреть точки проколотой окрестности 
и 
, расположенные симметрично относительно точки . Тогда середина отрезка, соединяющего с , то есть точка 
, совпадает с и, следовательно, не лежит в проколотой окрестности точки .
Если 
, то есть речь идёт о подмножествах прямой 
, то выпуклые множества можно описать полностью: это а) пустое множество; б) все одноточечные множества; в) все интервалы вида 
(где 
может равняться 
, а 
может равняться 
); г) все полуинтервалы вида 
(где может равняться ) и 
(где может равняться ); наконец, д) все отрезки вида 
. Никаких других выпуклых множеств на прямой нет.
Напомним изученное в первом семестре определение выпуклой функции одного вещественного переменного.
, заданная на отрезке , называется выпуклой (или выпуклой книзу) на этом отрезке, если для всех 
и 
выполняется неравенство 
и вогнутой (или выпуклой кверху), если выполняется неравенство
(То есть функция
вогнута в том и только том случае, если функция 
выпукла.) В левой части этого неравенства стоит значение функции 
в производной точке
и 
(будем для простоты считать, что 
), а в правой части неравенства -- значение линейной функции 
, такой что 
и 
(см. рис.). 
Если
и 
, то неравенство, означающее выпуклость функции , превращается в такое:
. Дадим теперь определение выпуклой функции многих переменных.
-- выпуклое множество, на котором задана функция 
. Функция называется выпуклой (или выпуклой книзу) на множестве , если для любых двух точек функция 
, служащая ограничением функции на отрезок, соединяющий точки и , является выпуклой (книзу) функцией одного переменного 
(здесь, как и выше, 
). 
Функция
называется вогнутой (или выпуклой кверху) в , если функция вогнута. Таким образом, функция вогнута в том и только том случае, когда функция 
выпукла.
Выпуклость функции в означает, что для любого отрезка 
с концами и параметризация этого отрезка в виде 
задаёт композицию 
, являющуюся выпуклой функцией параметра . Ввиду выпуклости области , любые точки 
и 
отрезка 
лежат в , и их снова можно взять в качестве концов отрезка. Поэтому для выпуклости функции 
в области необходимо и достаточно, чтобы неравенство
и . Если при этом при всех и выполняется строгое неравенство
будем называть строго выпуклой в . Наконец, функция называется строго вогнутой, если функция строго выпукла; это означает выполнение строгого неравенства
и . Геометрически (в случае 
) строгая выпуклость означает, что для любой хорды графика 
точки дуги графика с теми же концами, что у хорды, лежащие в вертикальном сечении, проходящем через эту хорду, располагаются ниже точек хорды. Строгая вогутость означает, что в любом вертикальном сечении график проходит выше любого отрезка, соединяющего две точки графика.
Заметим, что понятия выпуклой и вогнутой функций (а также строго выпуклой и строго вогнутой функций) в области
определены только для выпуклых областей . Дадим теперь такое алгебраическое определение.
размера 
. Она называется неотрицательно определённой, если 
для любого вектора-столбца 
(точкой обозначено скалярное произведение в ). Матрица называется положительно определённой, если 
для всех 
. Заметим, что выражение 
можно записать в виде 
, где 
-- это матрица-строка, равная транспонированному столбцу 
. Вообще, верхний левый индекс 
мы будем применять для обозначения транспонированной матрицы.
называется симметричной, если при всех 
имеет место равенство 
, то есть если 
. У симметричной матрицы равны друг другу элементы, расположенные симметрично друг другу относительно главной диагонали матрицы.
-- симметричная неотрицательно определённая матрица размера . Тогда квадратичная функция (она же называется квадратичной формой, заданной матрицей )
). Если же симметричная матрица -- положительно определённая, то заданная ею квадратичная форма 
является строго выпуклой.
Доказательство. Пусть и -- две произвольные точки и 
, где , -- точка отрезка, соединяющего с .
Предположим, что матрица неотрицательно определена. Элементарные преобразования позволяют записать 
в виде
 | |
 |
Поскольку матрица
неотрицательно определена, имеет место неравенство
. Доказательство строгой выпуклости в случае положительно определённой матрицы проводится с помощью очевидных изменений приведённого доказательства.
Другой пример выпуклой функции даёт линейная функция:
-- постоянные, является выпуклой функцией во всём пространстве (но не является строго выпуклой функцией). Действительно, как легко проверить, при всех 
и имеем
Поскольку функция 
, очевидно, также линейна, линейная функция 
является одновременно и вогнутой (но не строго вогнутой).
Если о некоторых функциях известно, что они выпуклы в области , то из них можно сконструировать другие выпуклые функции, используя следующие свойства выпуклых функций.
-- выпуклая область и функции и 
выпуклы в . Тогда сумма этих функций 
также выпукла в . Доказательство. Пусть и , где . Тогда
 | |
 |
что и означает выпуклость функции
. Поскольку, как мы доказали выше, квадратичная функция с неотрицательно определённой матрицей и линейная функция выпуклы, то и их сумма, согласно доказанному свойству, -- выпуклая функция. В качестве упражнения докажите, однако, ещё одно утверждение, не вытекающее из теоремы 7.17:
-- квадратичная форма, заданная симметричной положительно определённой матрицей , а -- линейная функция, то функция 
строго выпукла. Указание: по сути дела, нужно повторить доказательство теоремы 7.16, с очевидными изменениями.
выпукла в области , то функция 
, заданная в равенством
. Доказательство. Пусть снова и , где . Тогда
 | (7.11*) |
 | (7.12) |
что и означает выпуклость функции
. Первое неравенство в (7.11*) следует из того, что функция выпукла, а второе -- из того, что при всех 
имеет место неравенство:
-- равенство
выпукла в области , то функция 
также выпукла в . Доказательство. Пусть снова и , где . Тогда, ввиду того что 
, получаем:
 | |
 | |
 |
Последнее неравенство следует из того, что
при . Следующие три утверждения остаются читателю для самостоятельного доказательства в качестве упражнения.
и выпуклы в области и 
, то функция 
также выпукла в . Если функции и выпуклы в области , то функция 
также выпукла в .
Если функция выпукла в области , а функция одного переменного 
выпукла на интервале 
, содержащем множество значений функции при всех 
, и 
возрастает всюду на интервале или убывает всюду на , то композиция 
выпукла в . (Например, если функция выпукла в , то функция 
также будет выпуклой в .)
Выпуклые функции интересны такой своей особенностью: они не могут иметь нескольких локальных минимумов с разными значениями.
Сначала дадим такое определение.
-- некоторая область в . Точка 
называется точкой локального минимума функции , если существует такая окрестность 
, , что 
при всех 
. Если при этом 
при всех , не совпадающих с , то точка называется точкой строгого локального минимума. И в том и в другом случае значение 
называется локальным минимумом функции .
Точка называется точкой локального максимума функции , если существует такая окрестность , , что 
при всех . Если при этом 
при всех , не совпадающих с , то точка называется точкой строгого локального максимума. И в том и в другом случае значение называется локальным максимумом функции .
, выпуклой в области , даёт наименьшее значение функции во всей области ; любая точка локального максимума функции
, выпуклой в области , даёт наибольшее значение функции во всей области . Доказательство. Очевидно, что достаточно доказать лишь первое утверждение: второе следует из него сменой знака функции.
Пусть -- точка локального минимума, а в некоторой другой точке функция имеет меньшее значение: 
. Тогда в точках отрезка, соединяющего с , то есть точках , при всех 
значения функции будут меньше, чем в точке :
с имеются в любой, сколь угодно малой, окрестности точки , что противоречит предположению о том, что -- точка локального минимума. Значит, неравенство невозможно, и 
для любой точки 
. Это означает, что значение функции в точке локального минимума -- наименьшее во всей области . Практическая ценность этого утверждения в том, что при поиске наименьшего значения выпуклой функции в области достаточно найти любую точку локального минимума; во всех остальных точках локального минимуцма (если они существуют) значение функции будет точно такое же. Для невыпуклых функций это, конечно, не так, как видно на следующем рисунке:
Имеет место также следующая
Доказательство. Пусть в двух разных точках и функция принимает одно и то же значение 
Поскольку функция строго выпукла, то в точках , не совпадающих с и с , должно выполняться неравенство
, например, в середине отрезка 
, значение меньше 
, что противоречит предположению о том, что значение -- наименьшее во всей области. Значит, второй точки 
с тем же минимальным значением нет.
