1. Выпуклые множества и выпуклые функции.

Пусть — две точки -мерного евклидова пространства которые мы можем рассматривать как векторы в с соответствующими координатами.

Назовем отрезком или сегментом, соединяющим точки множество точек пространства вида где t — любое число из сегмента

Будем обозначать отрезок, соединяющий точки символом

Определение 1. Множество Q точек пространства называется выпуклым, если оно обладает следующим свойством: каковы бы ни были две точки принадлежащие множеству Q, отрезок их соединяющий, также принадлежит этому множеству.

Примером выпуклого множества в пространстве может служить -мерный шар (безразлично, открытый или замкнутый) или полупространство (т. е. множество всех точек пространства координата которых удовлетворяет условию

Примером множества Q, не являющегося выпуклым, может служить дополнение -мерного шара или -мерный открытый шар, из которого удалена хотя бы одна точка.

Пусть Q — некоторое множество точек пространства — любая фиксированная точка этого пространства.

Назовем расстоянием от точки х до множества Q точную нижнюю грань расстояний от точки х до всевозможных точек этого множества.

Будем обозначать расстояние от точки х до множества Q символом Итак, по определению

Для любого множества Q пространства и любой точки х этого пространства существует расстояние . В частности, если точка х принадлежит множеству Q, то

Однако у множества Q не всегда существует точка у такая, что

Так, например, если множество Q представляет открытый -мерный шар, — точка лежащая вне этого шара, то у такого множества Q не существует точки у такой, что

для всех точек у открытого шара справедливо неравенство

Если все же у множества Q существует точка у такая, что то эта точка у называется проекцией точки х на множество

Проекцию точки х на множество Q будем обозначать символом

Подчеркнем, что если точка х принадлежит множеству Q то

Итак, проекция точки х на множество Q определяется соотношением

Полезно отметить, что может существовать несколько проекций точки х на множество Так, например, если -мерная сфера с центром в точке х, то любая точка Q является проекцией точки х на множество

Справедлива, однако, следующая лемма:

Лемма 1. Если множество Q пространства является выпуклым и замкнутым, — любая точка то существует и притом единственная проекция точки х на множество

Доказательство. Сначала докажем существование хотя бы одной проекции точки х на множество Обозначим через расстояние от точки х до множества По определению как точной нижней грани найдется последовательность точек множества Q такая, что

По определению предела числовой последовательности для любого все элементы начиная с некоторого номера» удовлетворяют соотношению

Отсюда следует, что последовательность точек пространства во всяком случае является ограниченной и потому в силу теоремы Больцано — Вейерштрасса (см. п. 2 § 2 гл. 12) из этой последовательности можно выделить сходящуюся подпоследовательность где Обозначим через у предел подпоследовательности . В силу замкнутости множества Q точка у принадлежит этому множеству. Остается доказать, что

Для доказательства этого заметим, что в силу неравенств треугольника

справедливо соотношение

Из этого соотношения и их сходимости подпоследовательности к у вытекает, что , т. е.

Тем самым доказательство существования хотя бы одной проекции точки х на множество Q завершено.

Докажем теперь, что существует только одна проекция точки х на множество Предположим, что существуют две различные проекции и 1/2 точки х на множество Так как множество Q является выпуклым, то весь отрезок соединяющий точки принадлежит множеству . В частности, множеству Q принадлежит середина - указанного отрезка.

Убедимся в том, что расстояние от точки х до указанной середины отрезка строго меньше расстояния

Исключим из рассмотрения тривиальный случай, когда . В этом случае в то время как ибо в противном случае обе точки совпадали бы с х и не могли бы быть различными. Итак, в тривиальном случае неравенство

очевидно.

Докажем теперь неравенство (12.1.1) в случае, когда

Используя свойства скалярного произведения двух векторов пространства (см., например, замечание 2 из п. 1 § 1 гл. 12), мы получим соотношение

Убедимся теперь в справедливости строгого неравенства

В сноске на с. 485 доказано, что для любых векторов а и b пространства не коллинеарных друг другу (т. е. таких, что ни для одного вещественного X), справедливо строгое неравенство Коши — Буняковского

Это означает, что для доказательства неравенства (12.1.3) нам достаточно убедиться в том, что векторы не кол-Линеарны, т. е. убедиться в том, что ни для одного вещественного К не может быть справедливо равенство

Если бы равенство (12.1.4) было справедливо для такого К, для которого было бы невозможно равенство

Справедливость равенства (12.1.4) для противоречила бы тому, что точки и 1/2 являются различными.

Наконец, справедливость равенства (12.1.4) для —1 означала бы, что , а этот случай мы исключили.

Итак, равенство (12.1.4) несправедливо ни для одного вещественного а потому доказательство неравенства (12.1.3) завершено.

Сопоставляя равенство (12.1.2) с неравенством (12.1.3), получим, что

Тем самым доказательство неравенства (12.1.1) завершено. Но это неравенство означает, что у множества Q нашлась точка более близкая к х, чем точки а это противоречит тому, что каждая из точек является проекцией точки х на множество Q, т. е. является точной нижней гранью расстояния для всевозможных у, принадлежащих

Полученное противоречие показывает, что наше предположение о том, что существуют две различные проекции точки х на множество Q, является ошибочным.

Доказательство леммы 1 полностью завершено.

Перейдем теперь к определению выпуклой функции.

Определение 2. Функция заданная на выпуклом множестве Q пространства называется выпуклой вниз или просто выпуклой на этом множестве, если для любых двух точек множества Q и для любого вещественного числа t из сегмента справедливо неравенство

Определение 3. Функция заданная на выпуклом множестве Q пространства называется строго выпуклой на этом множестве, если для любых двух точек множества Q и для любого вещественного числа t из интервала справедливо строгое неравенство

Ясно, что всякая строго выпуклая на множестве Q функция f(x) является выпуклой на этом множестве.

Легко установить достаточное усдашие выпуклости [соответственно строгой выпуклости] дважды дифференцируемой на выпуклом множестве Q функции

Лемма 2. Пусть функция задана и два раза дифференцируема на выпуклом множестве Тогда, для того чтобы эта функция являлась выпуклой [строго выпуклой], на множестве Q достаточно, чтобы второй дифференциал этой функции во всех точках Q являлся квазиположительно определенной [строго положительно определенной] квадратичной формой.

Доказательство. Пусть — любые две фиксированные точки множества Рассмотрим на сегменте следующую функцию одной независимой переменной

Напомним, что второй дифференциал функции независимых переменных в данной точке равен

Дифференцируя функцию (12.1.7) два раза по t по правилу дифференцирования сложной функции, получим

где — координаты точек соответственно.

Сопоставляя соотношения (12.1.8) и (12.1.9), мы убедимся в справедливости равенства

в котором в выражении для приращения взяты равными

Дальнейшие рассуждения ради определенности проведем для случая, когда второй дифференциал во всех точках Q является квазиположительно определенной квадратичной формой.

В этом случае для всех t из сегмента правая (а значит, и левая) часть (12.1.10) неотрицательна, т. е. для всех t из сегмента

В силу определения 2 и соотношения (12.1.7) нам достаточно доказать, что для всех t из сегмента справедливо неравенство

Для доказательства неравенства (12.1.12) используем соотношение (12.1.11) и легко проверяемые равенства

Предположим, что внутри сегмента существует хотя бы одна точка в которой Тогда функция достигает своего максимального на сегменте значения в некоторой внутренней точке этого сегмента, причем . В этой точке функция имеет локальный максимум, а потому Но из неравенства (12.1.11) вытекает, что производная не убывает на всем сегменте а потому и на сегменте Отсюда и из условия следует, что производная неотрицательна всюду на сегменте 1, а поэтому функция не убывает на этом сегменте. Это приводит нас к неравенству

противоречащему второму соотношению (12.1.13).

Полученное противоречие доказывает, что наше предположение о том, что на сегменте существует хотя бы одна точка в которой является ошибочным, т. е. доказывает справедливость всюду на сегменте неравенства (12.1.12).

Тем самым первая часть леммы (о выпуклости при условии, что является квазиположительно определенной квадратичной формой) доказана.

Вторая часть леммы (о строгой выпуклости при условии, что является строго положительно определенной квадратичной формой) доказывается аналогично.. Исходя из неравенства (12.1.11), справедливого на этот раз со знаком и из равенств (12.1.13) и предположив, что внутри сегмента существует хотя бы одна точка в которой мы придем к выводу, что имеет внутри сегмента точку локального максимума причем Но тогда, поскольку мы получим из (12.1.11), что всюду на полуинтервале , а это означает, что

Мы снова получаем противоречие со вторым соотношением (12.1.13), которое доказывает, что всюду на интервале , т. е. доказывает строгую выпуклость на множестве Q.

Лемма 2 полностью доказана.

Доказанная лемма естественно наводит на мысль о рассмотрении следующего еще более узкого класса выпуклых на выпуклом множестве Q и два раза дифференцируемых на этом множестве функций.

Определение 4. Два раза дифференцируемая на выпуклом множестве Q функция называется сильно выпуклой на этом множестве, если существуют такие две положительные постоянные что второй дифференциал этой функции, определяемый соотношением (12.1.8), во всех точках х множества Q удовлетворяет неравенствам

(В этих неравенствах через обозначен вектор с координатами , а символ обозначает скалярный квадрат этого вектора, т. е. скалярное произведение

Из левого неравенства (12.1.14) сразу же вытекает, что второй дифференциал сильно выпуклой функции представляет собой строго положительно определенную во всех точках множества Q функцию, а потому (в силу леммы 2) сильно выпуклая на множестве Q функция заведомо является строго выпуклой на этом множестве.

Вместе с тем класс сильно выпуклых функций достаточно широк и важен в прикладных задачах, и мы ограничимся этим классом при изложении теории градиентного метода поиска минимума.

Начнем с выяснения вопроса о существовании и единственности минимума.