3. Поиск минимума сильно выпуклой функции.

Мы доказали, что сильно выпуклая функция заданная на замкнутом выпуклом множестве Q, имеет на этом множестве единственную» точку локального минимума.

Обратимся к построению и обоснованию алгоритма, с помощью которого отыскивается эта точка Аффиксируем произвольную точку множества Q и произвольное число а, удовлетворяющее неравенствам

где — постоянная из неравенства (12.1.14), определяющего сильную выпуклость функции

Отправляясь от как от первого приближения, составим итерационную последовательность с помощью рекуррентного соотношения

В настоящем пункте мы докажем следующее утверждение.

Основная теорема. Пусть функция является сильно выпуклой на замкнутом множестве Q, и пусть — произвольная точка множества Тогда итерационная последовательность определяемая рекуррентным соотношением (12.1.26)

при любом а, удовлетворяющем неравенствам (12.1.25), сходится к точке локального минимума функции

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

Доказательству основной теоремы предпошлем четыре леммы.

Лемма 4. Если Q — выпуклое замкнутое множество — произвольная фиксированная точка , а у — произвольная точка множества Q, то

Доказательство. Предположим, что неравенство (12.1.27) несправедливо. Тогда существует точка у множества Q такая, что

Из (12.1.28) сразу же вытекает, что точка у не совпадает с

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

Так как x и у фиксированы, — любое число из сегмента то в силу неравенства (12.1.28) мы можем взять t удовлетворяющим неравенству

При таком выборе

и мы получим из (12.1.29), что

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

Лемма 5. Пусть дифференцируема и выпукла на замкнутом выпуклом множестве Если при некотором положительном а проекция точки на

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

Доказательство. Используя лемму 4, запишем неравенство (12.1.27) для точек , где — любой вектор, для которого точка принадлежит . В результате получим

Учитывая, что получим из последнего неравенства следующее соотношение:

Это соотношение, справедливое для любого вектора для которого точка принадлежит Q, в силу леммы 3 устанавливает, что функция имеет в точке локальный минимум.

Лемма 5 доказана.

Предположим, что функция является сильно выпуклой на ограниченном замкнутом выпуклом множестве Обозначим через минимальное значение на множестве Q, а через число, строго большее так что

Фиксируем число строго большее и обозначим через Q — подмножество тех точек х множества Q, для которых

Множество Q как подмножество ограниченного множества Q само является ограниченным.

Убедимся в том, что множество является замкнутым. Пусть — произвольная сходящаяся последовательность точек множества Требуется доказать, что предел этой последовательности также принадлежит множеству Так как каждая точка принадлежит множеству то для каждого номера

Сильно выпуклая функция во всяком случае непрерывна на Q, а поэтому из сходимости последовательности в силу определения непрерывности функции по Гейне вытекает сходимость последовательности к числу Так как все элементы сходящейся числовой последовательности удовлетворяют неравенствам (12.1.31), то и предел этой последовательности удовлетворяет неравенствам

(см. гл. 3, следствие 2 из теоремы 3.13), а это и означает, что точка принадлежит множеству Доказательство замкнутости множества завершено.

Итак, множество Q всех точек х из множества Q, для которых справедливы неравенства (12.1.30), является замкнутым и ограниченным.

Докажем теперь следующую лемму.

Лемма 6. Пусть функция сильно выпукла на выпуклом замкнутом множестве — любая точка Q, а — любое положительное число, символ обозначает разность

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

Если же множество Q, кроме того, ограничено и точка х принадлежит подмножеству Q тех точек Q, для которых справедливы неравенства (12.1.30) при то найдется строго положительное число у такое, что справедливо неравенство

Доказательство. Докажем сначала неравенство (12.1.33). Фиксируем произвольную точку х множества Q и, привлекая лемму 4, запишем неравенство (12.1.27), взяв в нем вместо х точку а вместо у точку х. При этом получим неравенство

которое с учетом обозначения перепишется в виде

Из последнего неравенства и из свойств скалярного произведения вытекает, что

а это и приводит к неравенству (12.1.33).

Остается доказать, что при дополнительном предположении о том, что Q ограничено и что х принадлежит подмножеству , существует такое, что справедливо неравенство (12.1.34). Рассмотрим неотрицательную функцию точки х вида

Убедимся в том, что эта функция является непрерывной на множестве Q функцией точки х.

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

справедливое для любых векторов

В силу леммы 4 справедливы неравенства

Используя эти неравенства и неравенство Коши—Буняковского получим цепочку соотношений

из которой и вытекает неравенство (12.1.36).

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

является непрерывной на множестве Q векторной функцией точки х.

Модуль указанной векторной функции, т. е. скалярная функция (12.1.35) тем более является непрерывной на множестве Q, а потому и на его подмножестве

Итак, функция (12.1.35) непрерывна и неотрицательна всюду на замкнутом ограниченном множестве . В таком случае, по второй теореме Вейерштрасса (см. теорему 12.7) эта функция достигает на множестве (5 своего неотрицательного минимального значения у. Указанное минимальное значение у заведомо строго положительно, ибо если бы у равнялась нулю, то на множестве Q нашлась бы точка такая, что а это означало бы в силу леммы 5, что в этой точке множества Q функция имеет единственный на множестве Q локальный минимум (в то время как этот минимум по определению Q лежит вне Итак, и неравенство (12.1.34) доказано.

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

Лемма 7. Пусть функция сильно выпукла на выпуклом замкнутом множестве — любая точка Q, а — любое число, удовлетворяющее неравенствам (12.1.25), — разность вида (12.1.32). Тогда при переходе из точки х в точку значение функции не возрастает, причем

Если же множество Q, кроме того, ограничено и точка х принадлежит подмножеству Q тех точек Q, для которых справедливо неравенство (12.1.30) при то неравенство (12.1.37) переходит в неравенство

где — постоянная из леммы 6.

Доказательство. Достаточно для любой точки х множества Q установить неравенство (12.1.37), ибо из этого неравенства и из неравенства (12.1.34) сразу вытекает и неравенство (12.1.38) (для точек х, принадлежащих Q, при условии, что Q ограничено).

Сначала докажем неравенство (12.1.37) для случая, когда, точка х является внутренней точкой множества Имея в виду, что точка принадлежит множеству Q, на) котором функция сильно выпукла, выразим значение формуле Тейлора с центром в точке х, взяв остаточный член в форме Лагранжа. При этом получим

где

Используя неравенство (12.1.33) и правое неравенство (12.1.14), мы получим из формулы Тейлора (12.1.39)

так что для случая внутренней точки х неравенство (12.1.37) доказано.

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

Для каждой точки по формуле Тейлора с центром в этой точке мы получим

где

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

Лемма 7 доказана.

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

Возьмем произвольную точку множества Q и составим итерационную последовательность точек, определяемых рекуррентным соотношением (12.1.26), при условии, что число а удовлетворяет неравенствам (12.1.25).

Из леммы 7 (а точнее, из неравенства сразу же вытекает, что

Таким образом, последовательность является невозрастающей. Так как, кроме того, эта последовательность ограничена снизу (минимальным значением функции на множестве то она является сходящейся (см. теорему 3.15 из гл. 3). Обозначим предел последовательности через Ясно, что где — минимальное значение на множестве

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

Докажем, что для предела справедливо равенство

Предположим, что это равенство несправедливо, т. е. предположим, что ц>т. Тогда если обозначить через максимальное значение на множестве Q, а через Q подмножество тех точек Q, для которых справедливы неравенства (12.1.30), то в силу леммы 7 найдется строго положительная постоянная у такая, что справедливо неравенство (12.1.38), которое приводит к следующему неравенству:

справедливому для любого номера k.

Суммируя неравенства (12.1.42), записанное для номеров равных мы получим, что для любого номера

или, что то же самое,

Неравенства (12.1.43), справедливые для любого номера противоречат неравенству (12.1.41), ибо величина, стоящая в правой части (12.1.43), при достаточно большом номере становится меньше числа

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

Остается доказать, что сама итерационная последовательность сходится к той точке в которой это минимальное значение достигается

Фиксируем произвольное положительное число и обозначим через открытый -мерный шар радиуса с центром в точке Далее обозначим через ту часть множества Q, которая не содержит точек шара Се. Ясно, что — замкнутое ограниченное множество, так что функция достигает (в силу второй теоремы Вейерштрасса) своего минимального на этом множестве значения, которое мы обозначим через те.

Можно утверждать, что ибо в противном случае нарушалось бы условие существования у функции на множестве Q единственной точки локального минимума.

Далее, можно утверждать, что на множестве имеется лишь конечное число точек последовательности (ибо последовательность которой имеется бесконечное

число элементов, удовлетворяющих неравенству не может сходиться к числу

Значит, мы доказали, что для любого найдется номер N, начиная с которого все элементы последовательности лежат в шаре радиуса с центром в точке Это и означает, что последовательность сходится к точке

Тем самым для случая ограниченного замкнутого выпуклого множества Q основная теорема доказана.

Пусть теперь Q — неограниченное замкнутое выпуклое множество. Снова фиксируем произвольную точку этого множества и составим итерационную последовательность (12.1.26) при условии, что число а удовлетворяет неравенствам (12.1.25).

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

Там же установлено, что подмножество множества Q является ограниченным выпуклым замкнутым множеством и что всюду вне значения превосходят

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

Значит, итерационную последовательность (12.1.26) можно заменить на

после чего все дальнейшие рассуждения сведутся к ограниченному замкнутому выпуклому множеству т. е. к уже рассмотренному выше случаю.

Основная теорема полностью доказана.

Замечание 1. Особенно просто выглядит последовательность (12.1.26) для случая, когда множество Q совпадает совсем пространством Ет. В этом случае для любой точки х справедливо равенство и потому рекуррентная формула (12.1.26) принимает вид