Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 12
Текст из файла (страница 12)
3. Пусть /(х) выпукла нз [а, 6). Доказать, что / (о-О) <ь/ (о+О) </ (и-О) </ (и+О) при всех и, е (а < е < и < Ь). Пользуясь этими неравенстве ми, покзэзть, что /(х) дифференцируемз в точке и (а < е < Ь) тогда и только тогда, когда одна из функций /'(х+ 0) или /'(х — 0) непрерывнз в тачке и. 4. Пусть /(х) выпукла нз [а) Ь]. Пользуясь упрамснениями 2, 3, доказать, что множества точек непрерывности функции / (х+0) и / (х-0) совпадают. Вывести отсюда, что множество точек, в которых /(х) недифференцируемз, не более чем счетно, б.
Пусть функция /(х) непрерывна нз отрезке [а, Ь], дифференцируемэ нз отрезках [а, а~), [аы аз1,..., [а„па„], [а„, Ь] (а< а~ <... < а < Ь), причем нз каждом таком отрез. ке производная /'(х) суммируемз, не убывает и /'(аг — О) < /'(а,. -1-О) (3 = 1,..., и). Доказать', что тогда /(х) выпукла нз [а, 6). б. Для выпуклости функции /(х) нв интервале (а, 6) необходимо и достаточно, чтобы существовзлв функция 1(е) (а е (а, Ь)) такая, что /(х) > /(е) + 1(о)(х — е) при всех х е (а, 6).
Необходимость доказана з теореме 4, докажите достаточность. Покажите, что 1(е) = /1(е) почти всюду нз (а 6) т. Пользуясь теоремой 3, доказать, что выпуклзя нз отрезке [а, Ь] функция /(х) абсолютно непрерывна нз любом отрезке [а,33] с (а, 6). б. Если функция д(1) возрзстзет нз отрезке [а, Ь) и суммируемз нз этом отрезке, то функция /(х) = 1 д(1)щ выпукла нз [а, ь]. Доказать. Верно ли обратное утверждение? 9. Пусть /(х) выпуклз нз [а, 6) и имеет обратную функцию. Можно ли утверждать', что обрзтнзя функция также будет выпуклой? Рассмотреть функции /(х) = е*, /(х) = е *. 10.
Пусть /(х) выпукла не [а, Ь] и !пп У(и) = /(а), Лю /(и) = /(Ь), в Х, — множеь аьо ь ь-о ство точек минимуме /(х) нз [а, Ь]. Докзззть, что Х, гз[а, 13] ф Я, (Х, с !и! [а, 13]) тогда и только тогда, когдз / (а — О) < О, / (д Ч О) > О, (/ (а — О) < О, / (/3+ 0) > О); здесь а < а < 33 < Ь. 11. Доказать, что выпуклая ни отрезке [а„Ь] функция /(х), отличная от постоянной, не может достигать своей верхней грани внутри отрезка [а, Ь]. 12. Пусть функция /(и) выпукла и монотонно возрастает нз отрезке [а, Ь], з функция з(х) выпукла нз [с, а], причем з(х) е [а, 6] при всех х в [с, В].
Доказать, что тогда сложнее функция д(х) = /(з(х)) выпукла нз [с,а]. 13. Назовем функцию /(х) выпуклой нз отрезке [а, Ь], если /((и+о)/2) ((/(и)+/(е))/2 при всех и, е е [а, Ь]. Доказать, что для непрерывных функций это определение выпуклой функции рзвносильно определению 1. Если не требовать непрерывности /(х), то новое определение выделяет более широкий класс функций — см. пример из [735, стр.1!9]. 39 Ь 9. МЕТОД КАСАТЕЛЬНЫХ 38 Гл.
1, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 14. Пусть Х(х) — выпуклая функция при х > О, Х(О) <'О. Доказать, что тогда функция Г«(х) = Г(х)/х монотонно возрастает при х > О. На примере функции Х(х) =! + х убедиться, что при ПО) >Олго утверждение неверно. Указа н ие: воспользоваться равенством Г(н) = =Х( м (и+ 6)+ — 0) (Ь >0). 1Б. Пусть функция Х(х) выпукла и дваькды дифференцируема прн х > О, прнчем Ох (ху'(х) — Х(х)) < О, Доказат~, что тогда Ь«(х) = Х(х)/х монотонно убывает при х > О. У к а з а н и е: вычислить производные функций Ьг(х) и хХ'(х) — Х(х). 16. Доказать, что (а+ Ь)" < 9« '(а«+ Ь") при всех и > 1, а> О, Ь >О.
Указание: воспользоваться выпуклостью функции Х(х) = х" при х > О, и > 1. 9 9. Метод касательных 1. Пусть функция г(х) выпукла и дифференцируема на отрезке [а, 6]. Согласно теоремам 8.3, 8.7 такая функция удовлетворяет условию Липшица и унимодальна на [а, 6]. Поэтому для минимизации 7(х) на [а, 6] применимы почти все описанные выше методы, в частности, метод ломаных из 9 6. Однако, если значения функции Х(х) и ее производной Х'(х) вычисляются достаточно просто, то здесь можно предложить другой, вообще говоря, более эффективный вариант метода ломаных, когда в качестве звеньев ломаных берутся отрезки касательных к графику Х(х) в соответствующих точках.
Зафиксируем какую-либо точку и е [а, 6] и определим функцию д(х, и) = = Х(и) + Х (и)(х — и), а < х < Ь. Согласно теореме 8.4 д(х, и) < 7(х) Чх е [а, Ь] В качестве начального приближения возьмем любую точку хо е [а, Ь] (например, х = а), составим функцию ро(х) = д(х, хо) и определим точку и, е [а, 6] из условия ро(х1) = ппп ро(и) (ясно, что при Х'(то) ~0 будет х, = а или 6) «е1«,ь) Ь Далее, берем новую функцию р,(х) = шах(ро(х); д(х, х,)) и следующую точку х е [а, 6] найдем из условия р,(х ) = ш!и р,(и), и т. д, Если точ«е1ч Ь1 ки х„х„..., х„(и > 1) уже известны, то составляем функцию р„(х) = = шах(р„,(х); д(х, х„)) = шах д(х, хг) и следующую точку х,+, опреде0<г<« ляем из условий р„(х„г,) = ш!и р„(и) (х„,, е [а, 6]).
Если при каком-либо е(«, Ь1 и > 0 окажется, что Х'(х„+О) > О, Х'(х„— 0) < 0 (если а< х„< Ь, то это равносильно условию ~'(х„) =0), то согласно теореме 8.5 х«е Х, — в этом случае задача минимизаций уже решена и итерации на этом заканчиваются. Нетрудно видеть, что р„(х) — непрерывная кусочно линейная функция и ее график представляет собой ломаную, состоящую из отрезков касательных к графику функции 7(х) в точках х,х„ ...,х„ (рис. 1.5).
Поэтому описанный метод естественно назвать методом касательных. Теорема 1. ХХусть функция Г(х) на отрезке [а, 6] выпукла и дифференцируема, а последовательность (х„) получена описанным выше методом касательных, причем х, (с Х„(и = О, 1,...). Тогда: 1) !пп Х(х„) = 1!гп р„(х„+,) = Х, и справедлива оценка ««с« 0 < Х(х„,) — ) < Х(х„+,) — р„(х„,), п = 1, 2,.
2) йгп р(х„, Х,) =О, или точнее, (х„) имеет не более двух предельнвгх точек, совпадающих с и, = !п1Х„или и„= зпр Х,. Доказательство. Поскольку величины Х'(а+0), 7'(Ь вЂ” 0) конечны по условию, то в силу теоремы 8.3 функция Х(х) удовлетворяет условию Липшица с постоянной Х = шах([Х'(а)[, [Х'(Ь)[). Кроме того, согласно (1) и определению функции р„(х) имеем р.,(х) < р.(х) < У(х), х 6[а, 6], та=1,2, (2) Тогда Х(хг) = д(хг, хг) < р„(хг) < г(хг), т. е. Х(хг) = р„(хг), ь = О, 1,..., ть. (3) Наконец, угловые коэффициенты касательных д(х, х,) равны Х'(хз), причем [Х'(х;)] < Х, Из теоремы 6.1 тогда следует, что р«(х) удовлетворяет условиго Липшица с постоянной Х,. Отсюда с учетом (2), (3) с помощью тех же рассуждений, которые применялись при доказательстве теоремы 6.3, нетрудно убедиться в справедливости всех утверждений доказываемой теоремы.
Остается лишь заметить, что из того, что функция Х(х) унимодальна и х„фХ,=[и.,и] (п>0), О равенство 1!гп р(х„, Х„) =0 возможно только в том случае, если предельными для (х„) будут лишь точки и, илй и„. Ю 2. Метод касательных обладает всеми достоинствами метода ломаных из 9 6. Недостаток этого метода Рис. 1,б. АР— график д(х, хо), сР— график д(х, хь) лшпь в слу АЛР гр~ф~к Рг(х) Рь«г ггафнк д(х хз) график Рз(х), ГР— график д(х, хз), АмггБР— график чае, когда минимизируемая функция выпукла и значения функции и ее производных вычисляются достаточно просто.
Можно предложить более удобную для использования на ЭВМ вычислительнуго схему метода касательных, которая не требует хранения в машинной памяти информации обо всей ломаной р (х) при х е [а, 6]. А именно, возьмем а, = а, Ь, = Ь, вычислим Х'(а ) = Х'(а+ 0), )'(Ь,) = Х'(Ь вЂ” 0). Если Г(а ) > 0 или р)(Ь ) < О, то по теореме 85 ае Х, или Ь Н Х, — задача решена. !1оэтому, пусть Г'(а,) < О, ~'(6,) > О, что согласно теореме 8.6 означает Х„с (а, Ь).
Пусть отрезок [а „Ь„,] (и > 2) уже построен, причем Х'(а„,) < О, Г'(Ь„,) > О, Х„с (а„„Ь„,). Обозначим через х, точку пересечения касательных д(х, а„,) и д(х, Ь„,). Ясно, что а„, < х„< Ь Вычислим Х'(х„). Если Х'(х„) =О, то х е Մ— задача решена, итерации на 40 Гл. 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ этом заканчиваются. Если /'(х„) зА О, то положим а „г'(х„) > О, ~' х, /'(х„) > О, (4) / (х ) < О, [ Ь„„ /'(х.) < О По построению /'(а ) < О, /'(Ь„) > О, и согласно теореме 8.6 Х„с (а, Ь).
Индуктивное описание метода закончено. Из геометрических построений нетрудно усмотреть (см. рис. 1.5), что этот метод совпадает с описанным выше методом касательных, в котором за начальную точку берется х = а. В то же время приведенная схема метода более проста и удобна для реализации на ЭВМ, на каждом шаге метода здесь достаточно хранить в памяти ЭВМ величины ага Ь„, /(а.), /(Ь„), /'(а„), /'(6„). Нетрудно выписать явное выражение для точкй х„„„определяемой условием д(х, а„) = д(х, 6„) пересечения касательных в точках а„, Ь„при /'(а„) <О, /'(Ь„) > 0: У(а„) — У(Ь„) -Ь Ь„У (Ь ) — а„У (а ) (5) " |'4 г"'(Ь„) — У'(а„) 3. Поскольку ломаная из отрезков касательных аппроксимирует функцию /(х), вообще говоря, лучше, чем ломаные из 9 6, то следует ожидать, что метод касательных для выпуклых функций сходится быстрее метода ломаных из $ 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
