ilin1 (947407), страница 107
Текст из файла (страница 107)
п. 8 3 4 гл. 12) предел при 1- О+О правой части (12.1.17) в точности равен произведению, стоящему в правой части (12.1.16). Поэтому в силу соотношений (12.1.15) и (12.1.16) этот предел неотрицатеяен. Учитывая, что левая часть (12.1.17) не зависит от 1, мы получим в пределе при г -О+О из неравенства (12.1.17), что Г(хо+Лх) ((хо) М. Последнее неравенство, справедливое для любого вектора Лх, для которого точка хо+Лх принадлежит Я, доказывает, что функция [(х) имеет в точке хо локальный минимум. Достаточность доказана. Лемма 3 полностью доказана.
3 а м е ч а н и е 1. Из приведенного нами доказательства очевидно, что для случая, когда точка хо является в нутре н ней точкой множества Я, т. е. когда речь идет о внутреннем локальном минимуме, в формулировке леммы 3 знак ~ в неравенстве (12.1.15) можно заменить на знак =. 3 а м е ч а н и е 2. При доказательстве необходимости леммы 3 мы не использовали требования выпуклости функции [(х). Поэтому доказательство необходимости проходит без требования выпуклости функции [(х). Иными словами, справедливо следующее У т в е р ж д е н и е.
Если функция 1(х) дифференцируема на выпуклом множестве (,) и имеет локальный минимум во внутренней [в граничной) точке хо этого множества, то для любого вектора Лх для которого точка хо+Лх.принадлежит Я, справедливо неравенство (пгай [(хо), Лх) =0 [(пгад)(хо), Лх) ) 0). Перейдем к вопросу об единственности и о существовании точки локального минимума. Теорема (об единственности локального минимума у строго выпуклой функции). Если функция [(х) дифференцируема и строго выпукла на выпуклом множестве Я, то она может иметь локальный минимум только в одной точке этого множества. Гл. !2. Функции нескольких переменных Д о к а з а т е л ь с т в о..
Предположим, что функция 1(х) имеет локальный минимум в двух р а з л и ч ны х точка х1 и хе множества 9. Тогда условие выпуклости (!2.1.5) для точек хй и хе можно записать в виде [[х, + г(х,— х,!! — [(х,! (12.1.18)~ (здесь ( — любое число из интервала 0<(<1). Меняя в соотношении (12.1.8) точки х~ и хе ролями, мы получим неравенство ~(х,) — [(х ) >[[ ' ( ' [( ' .
(12.1.19) В пределе при (- О+О правая часть (12.1.18) [соответственно правая часть (12.1.19)] дает производную функции [(х) яо направлени1о вектора хе — х~ [соотвстственно вектора х~ — хе], взятую в точке х~ [соответственно в точке х,], умноженную на !хе — х|[.
Так как обе точки х1 и хе являются точками локального минимума, то обе указанные производные по направлению неотрицательны, т. е. пределы правых частей (12.1.18) и (12.1.19) при (- О+О оба неотрицательны. Таким образом, из неравенств (12.1,18) и (12.1.19) в пределе при (- О+О мы получим 1(хе) — ! (х,) ~0, [(х,) — [(хе) ~0. Сопоставление двух последних неравенств приводит к заключе. нию о том, что ( (х~) =( (хз). Используя равенство !(х~) =!(хз), мы получим из условия строгой выпуклости (12.1,6), что [[х~+!(хе — х1)]<[(х~) (12.1.20) для всех ( из интервала 0<(<1. Неравенство (12.1.20) противоречит тому, что функция 1(х) имеет локальный минимум в точке х1 (в точке х,+1(хе — х1), как угодно близкой при малом ( к точке хь функция ((х) имеет значение, меньшее значения !(х~)). Полученное противоречие доказывает, что наше предположение о том, что функция ((х) имеет локальный минимум в двух различных точках множества Я, является ошибочным.
Теорема доказана. Существование локального минимума докажем при более сильных ограничениях, чем единственность. Теорема (о существовании локального минимума у сильно выпуклой функции). Если функция [(х) сильно выпукла на замкнутом выпуклом множестве (,[, то 525 Дополнение 1 у этой функции существует на множестве (г точка хс локального минимума *.
Д о к а з а т е л ь с т в о. Сначала отметим, что теорема заведомо справедлива для случая, когда выпуклое замкнутое множество () является, кроме того, ограниченным. В этом случае по второй теореме Вейерштрасса (см. теорему 12.7) функция )(х), будучи во всяком случае непрерывной на множестве Я, достигает в некоторой точке хь этого мноиества своего минимального на Я значения. Указанная точка хе и является точкой локального минимума. Остается доказать теорему в случае, когда выпуклое замкнутое множество Я не является ограниченным. В этом случае мы фиксируем некоторую внутреннюю точку х1 множества Я и разложим функцию 1(х) по формуле Тейлора с центром в,точке хь взяв остаточный член )ся(х) в форме Лагранжа ** (см.
и. 3 0 5 гл. 12). Указанное разложение будет иметь вид [(х) = [(х,)+ ф(х,)+ — йэ~ [х, + 0 (х — хт)], (12.1.21) где 0 — число из интервала 0<0<1, так что точка к~+0(х — х1) принадлежит отрезку, соединяющему точки х, и ха э**, Если обозначить через Ьх вектор х — хь то для й)(х1) будет справедливо равенство й)(х1) = (угад)(х~), Лх). Из этого равенства вытекает.
что (Щ(х,) ) ~ )агат(((х~) ( (Лх). (12.1,22) Далее, используя левое неравенство в определении сильной выпуклости (12.1.14), мы придем к неравенству с(я[ [х, +0(х — х,) [ ъй, (Лх)я. (12.!.23) Из соотношений (12.1.21) — (12.1.23) заключаем, что 7 (х) — 7 (хт) ) — (ау (хт)(+ — йз7 [х, + 0 (х — х,) [ ) ) — (угад~(х,)) (ах(+ — '(Ьх(з, * Так как сильно выпуклая на выпуклом множестве Я функция 1(х) является строго выпуклой на этом множестве, то по предыдущей теореме точка хэ будет един ственной точкой локального минимума.
ээ мы учитываем, что сильно выпуклая на множестве О функция 1(х) два раза днфференцируема на этом множестве. "' Какова бы ии была точка х множества О, отрезок, соединяющий точки х~ и х, принадлежит множеству Я в силу выпуклости этого множества. В сноске к теореме Тейлора 12.15 отмечалось, что в качестве окрестности центра разложения можно брать любую звездную окрестность этого центра, т.
е. можно брать все множество ы'. Гл. !2. Функнии нескольких переменных 52З так что 1(х) — 1(х,) > !Ьх! ~ — '!Ьх( — !Пгаг(Г'(х,) ~ ~, (12.1.24) (12.1.25у Учитывая, что точка х1 фиксирована и величина ~асад!(х~) ( представляет собой некоторое фиксированное число, мы заведо- мо можем выбрать положительное число Я настолько большим, чтобы при !Лх~>Я выражение в квадратных скобках к (12.1.24) было положительным. Это означает, что при 1Ьх~ >Я справедливо неравенство 1(х) >1(х~), т.
е. всюду вне замкнутого шара Сн радиуса )1 с центром в точке х1 значения ~(х) превосходят значение 1(х,) (в центре указанного шара). Обозначим через Яя пересечение множества 1,! с указанныьг шаром Ся. Так как оба множества Я и С„являются выпуклыми и замкнутыми; то и их пересечение Яя также является выпук- лым и замкнутым.
Так как, кроме того, множество Ян является. ограниченным, то по доказанному выше функция 1(х) имеет на множестве Яя единственную точку хо локального минимума. Поскольку мы доказали, что во всех точках 1З, лежащих за пРеделами Яи, значениЯ 1(х) пРевосходЯт )(х~), то эти значениЯ тем более превосходят )'(хо), т. е. точка хо является точкой ло- кального минимума 1(х) и на всем множестве ьс. Теорема полностью доказана. 3.
Поиск минимума сильно выпуклой функции. Мы доказалк, что сильно выпуклая функция 1(х), заданная на замкнутом вы- пуклом множестве Я, имеет на этом множестве единственную точку хо локального минимума. Обратимся к построению и обоснованию алгоритма, с по. мощью которого отыскивается эта точка хо. Фиксируем произвольную 'точку х~ множества 1с и произ- вольное число а, удовлетворяющее неравенствам 0(а( —, 2 где йе — постоянная из неравенства (12.1.14), определяющего сильную выпуклость функции 1(х). Отправляясь от х1 как от первого приближения, составим итерационную последовательность (хе) с помощью рекуррентно- го соотношения хь+1=Ро(хе — айгад((хе)), й=1, 2, 3, ....
(12.126)' В настоящем пункте мы докажем следующее утверждение. О с и о в н а я т е о р е м а. Пусть функция 1(х) является силь- но выпуклой на замкнутом множестве !4, и пусть х1 — произ- ьольная точка множества Я. Тогда итерационная последователь- ность (хе), определяемая рекуррентным соотношением (12.!.26)„ Дополнение 1 при любом а, удовлетворяющем неравенствам (12.1.25), сходится к точке хо локального минимума функции 1(х). Подчеркнем, что эта теорема дает алгорит отыскания любого (внутреннего или краевого) локального минимума функции )(х), являющейся сильно выпуклой на произвольном (не обязательно ограниченном) замкнутом выпуклом множестве. Доказательству основной теоремы предпошлем четыре леммы. Л е м м а 4.
Если Я вЂ” выпуклое замкнутое множество Е'", х — произвольная фиксированная точка Е", а у — произвольная точка множества (г, то (х — Ро(х), у — Ро(х)) ~0. (12.1.27) Д о к а з а т е л ь с т в о. Предположим, что неравенство (12.1.27) несправедливо. Тогда существует точка у множества (,) такая, что (х — Ро(х), у — Ро(х)) >О. (12.1.28) Из (12.1.28) сразу же вытекает, что точка у ие совпадает с Ро(х). В силу выпуклости множества Я любая точка г=РЧ(х)+ +1(у — Ро(х)) отрезка, соединяющего точки Ро(х) и у, принадлежит множеству Я. Вычислим расстояние между любой такой тОчкОЙ г и точкОЙ х: ро(г, х) = (х — Ро (х) — 1(у — Рд (х) ), х — Ро (х) — 1(у — РО(х) ) ) = =р'(х, Ро(х) ) — 21(х — Рч(х), у — Ро(х) )+Рр'(у, Ро(х) ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
