XIV Аттетков и др. Методы оптимизации (1081420), страница 20
Текст из файла (страница 20)
Тогда в этих точках ~(х) достигает наименьшего значения ту. При этом для любого 1 Е (О, 1) имеем ~(х) = Х(1х'+ (1 — Х)х') < Ттрн+ (1 — 1)т1 —— ту, а это невозможно., так как ту — наименьшее значение функции. Противоречие показывает, что строго выпуклая функция может иметь нс более одной точки локального минимума. 1» Теорема 3.15. Пусть функция ~(х) выпукла на выпуклом множестве П с 2" и дифференцируема в точке х* Е й.
Для того чтобы точка х' была точкой локального минимума функции 1'(х), необходимо и достаточно, чтобы для любой точки х Е П выполнялось неравенство (бгадДх'), х — х*) > О. (3.25) Необходимость. Пусть х' Е П вЂ” точка локального минимума функции ~(х) и функция дифферснцируема в этой точке. Выберем произвольную точку х б й и рассмотрим сечение р(1) = ~(1х + (1 — 1) х'). Функция ~р(~) определена на отрезке ~0, 1), имеет в точке 1 = 0 локальный минимум и дифферснцируема в этой точке. Следовательно, ~р~(0) ) О.
По правилу дифференцирования сложной функции ~о (О) = — ~(1х+ (1 — 1)х*) ~ = (Огас1~(х*), х — х*), ~Й О=о откуда получаем неравенство (3.25). Достаточность. Пусть в точке х* выполнено неравенство (3.25). Выберем произвольную точку х Е П и рассмотрим сечение ~р(1) = ~(1х+ (1 — 1)х*). Так как ~(х) выпукла, то и ее 3.4. условия минимума вьтуклык функций 131 сечение ~р(с) выпукло.
Из неравенства (3.25) заключаем, что со'(0) ) О. Следовательно, у(1) — неубывающая функция на отрезке [О. Ц и ~р(0) < ~р(1). Последнее неравенство равносильно неравенству 1(х*) ( 1(х). Таким образом, в точке х* функция Дх) принимает наименьшее в Й значение. ~ Замечание 3.3. Во внутренней точке х' множества П неравенство (3.25) равносильно равенству гас11(х') = О.
Действительно, в этом случае для любого вектора Ь Е Ка для достаточно малого числа с ) 0 имеем х*+ сЬ Е й и х* — сЬ Е й. Следовательно, одновременно выполняются неравенства (бгас1 ~(х'), ей) ) О, (дас11'(х"), — сЬ) ) О. Отсюда заключаем, что (бгас1~(х*), Ь) = 0 для любого вектора Ь е Ка и рас1 ~ (х*) = О. Таким образом, неравенство (3.25) можно рассматривать как обобщение необходимого условия 3гас11(х') = 0 локального минимума функции на случай, когда точка не является внутренней точкой области определения функции. При этом следует учитывать, что неравенство (3.25) дает не только необходимое условие локального минимума, как равенство дгас1~(х') = = О, но и достаточное.
Такое обобщение стало возможным благодаря дополнительному условию выпуклости функции. Заметим, что условие (3.25) при х = х* переходит в равенство, и поэтому это условие можно записать в эквивалентной форме 1п1п1дгас111х ), х — х~) = О. иеп (3. 26) Замечание 3.4. Предположим, что внутренняя точка х* множества й является стационарной точкой функции Дх), определенной на множестве П. Если функция Дх) дважды непрерывно дифференцируема в некоторой окрестности П точки х', а ее матрица Гессе неотрицательно определена в каждой точке окрестности о', то эту окрестность можно уменыпить 3.
МИЕ1ИУ1ИЗЛЦИЯ ВЫПУКЛЫХ ФУИКЦИЙ 132 так, что она станет выпуклым множеством (любая е-окрестность — выпуклое множество), и тогда, согласно теореме 3.12, функция )'(х) выпукла в Г. Для такой функции условие ягас11(х*) = 0 является не только необходимым, но и достаточным условием локального минимума. Отметим, что выпуклая функция может иметь более одной точки локального минимума. Например, квадратичная функция 1(хмх2) = (х~ +х2) достигает в точке (О, 0) наименьшего значения, равного нулю. Но точками локального минимума являются также и все точки вида (1, — 1), 1Е Н.
3.5. Сильно выпуклые функции Определение 3.3. Функцию ~(х), определенную на выпуклом 24нолеестве Й С К", называют сильно выпуклой, если существует такая константа у ) О, называемая парамепзром сильной выпуклосгпи, что для любых точек х ., х Е Й и любого а Е [О, Ц справедливо неравенство 1 + с1 ) 2) < < а~(х1) + (1 — сэ)~(х2) — а(1 — а) у~х1 — х2~2. (3.27) Всякая сильно выпуклая функция является строго выпуклой функцией, но не наоборот. Действительно, при хс ф х2 и а Е (О, 1) из неравенства (3.27) вытекает строгое неравенство (3.6).
Однако выполнение этого неравенства не означает, что справедливо неравенство (3.27). Например, функция ~(х1, х2) = = хс+ х2 является строго выпуклой и для нее верно неравенство (3.6). Однако неравенство (3.27) при х' = (р, д) и х2 = (О, 0) равносильно неравенству а (р +о ) < сх(р +о ) — а(1 — а)'у(р +д ), или 2 + 2) < с1 + + 2)( 4 + 4) 3.5. Сильно выпуклые функции причем это неравенство должно быть верно при некотором фиксированном значении у и любых р, д и О Е (О, 1). Ясно, что при соответствующем выборе р, у и О оно нарушается (например, при р = д ( 1/2 и любом ех Е (О, 1)). Дадим геометрическую интерпретацию определения 3.3, рассмотрев функцию у = ~(х) одного переменного. Зафиксировав х1 и хо из области определения функции и обозначив х(се) = сьх~ + (1 — ее)хз, .будем изменять о от О до 1.
Яс- Р У но, что тогда значение х(ех) бу- ,В дет изменяться от хз до хм а точка (х, Дх)) пройдет по графику функции у = ~(х) от точ- и„х ки В = (хз, ~(хз)) до точки А = = (хы 7(х~)) (рис. 3.2). Уравнения с х = х(се), у = сейх1) + (1 — се) йхз) в плоскости хОу описывают прямун> Л (секущую), соединяющую точки А и В, а уравнения с х = х(о), у се~(х1) + (1 о)1(х2) М1 М ~(х1 х2) задают параболу Р вида у = ахз+ ба+ с, а = у(х~ — хз) ~, которая проходит через точки А и В. Неравенство (3.27) в этом случае означает, что график функции у = 7(х) на плоскости хОу расположен ниже не только секущей, соединяющей точки А и В, но и параболы Р, прогиб которой определяется параметром у, и его можно выбрать сколь угодно малым. Другими словами, в области, ограниченной секущей и графиком функции, можно построить параболу, соединяющую точки А и В.
Пример 3.13. Убедимся, что квадратичная функция вида 7"(х) = (Ях, х) + 2(с, х), с., х Е Кп, где ь, положительно 134 3. МИНИМИЗАЦИЯ НЫПУ1<ЛЫХ ФУНКЦИЙ определенная симметрическая матрица порядка и, сильно выпуклой на множестве И . В силу тождеств о = о — о(1 — о) и (1 — о) = (1 — о) — о(1 — о) заключаем, что ф(ох + (1 — о)х ), ох + (1 — о)х ) = г11З ~ «)+ ~1 )11,-) 1 г)+ 111 в 1))+ + 11 — о) (с,)хз, х ) = о фх, х ) + 11 — о) (Ях, х )— — о(1 — о) (Я(х — х ), х — х ) . Поэтому 1 '1ох + (1 — о) х ) = Я 1ох + (1 — о) х, ох + 11 — о) х ) + + (с, ох + (1 — о)х ) .= о(Ях', х") +(1 — о) (Ях, х ) + +о(с,х ) +(1 — о)1с, х ) — о(1 — о) (Я(х — х ), х — х ) = = о1(х') + (1 — о)1(х ) — о(1 — о) (1,)(х' — х )., х — х ).
Учитывая, что для положительно определенной матрицы 1,) справедливо неравенство ф(х — х ), х — х ) > Л~х — х ~, где Л ее наименьшее собственное значение,. приходим к выводу, что рассматриваемая функция удовлетворяет неравенству (3.27) при 7 ( Л и, значит, является сильно выпуклой. Теорема 3.16.
Для того чтобы функция 1(х), дифференцируемзя на выпуклом множестве 11, была сильно выпуклой, необходимо и достаточно, чтобы существовала константа р > О, для которой при любых х, х Е й выполняется неравенство (8гас111х') — бган,~(х ), .х — х~) > р~х' — х~~~. (3.28) 135 З.й.
Сильно выпуклые функции ~ Н е о б х о д и м о с т ь. Пусть выполнено неравенство (3.27). Тогда выполнено и неравенство (3.20). Используя оба неравенства в случае о = 0,5 и полагая Ь = х' — х~, получаем 0,257~Ь~~ < 0,5фх )+7(х~)) — 1(0,5(х'+х~)) = =0,5(((х ) — ~(0,5(х~+х~))) +0,.5(~(х~) — ~(0,5(х +х~))) < < 0,5(8гас1 1(х'), 0,5Ь) — 0,5(бгас1('(хз)., 0,.5Ь) = = 0,25(8гас1~(х') — 8гас1~(х~), Ь).
Таким образом, пришли к неравенству (3.28) с парамегром гс = 'у. Достаточность. Покажем, что если верно (3.28), то верно и неравенство (3.27). Полагая Ь = хс — хл, можем записать ох~ + (1 — о) х~ = х~ + оЬ и У(х')+(1- )~(х')-~( '+(1- ) ') = = сг(7(х ) — 7(х )) — 7(х +оЬ) +у(х ). Это позволяет представить неравенство (3.27) в эквивалентной форме о(~(хв+Ь) — ~(хл)) — Дхв+оЬ) + ~(хз) > 'уо(1 — о) ~Ь~з. (3.20) Рассмотрим функцию ~р(1) = офх'+ Ж) — ~(хз)) — фх'+ МЬ) — Дх'))., непрерывно дифференцируемую на отрезке (О, 1].
Запишем для производной р'(с) этой функции формулу Ньютона Лейбница ! р(1) — д(0) = р'(1) 11. о з. минилтизлция иып~ клык функций 130 Согласно правилу дифференцирования сложной функции, с2'(~) = сг(рас1~(х~+~Ь) Ь) — (дгас1~(х2+сЛъ) сгЬ) = = сг(дгас11(х2+Ж) — 8гас1~(х +сг1Ь), Ь) = (8гас1 ('(у' ) — 8тас1 1'(у ), у' — у )., где у' = х2+1Ь и у2 = х2+ сгЖ Используя неравенство (3.28) для пары точек у и у, получаем оценку д'И) > р ~и' — и2Г = ~ (1 — ) и~М' Таким образом, ~с2(1) — ц~(0) = ~р~(с) ссс'; > сг(1 — сг)р/Ь!2 1сГГ = — сг(1 — сг)р/Ь!~. 2 Непосредственным подсчетом убеждаемся., что ~р(0) = 0 и д(1) = оЯх'+Ь) — Пх')) — ЯХ+оЬ) — 1( ')), т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
