Ф.П. Васильев - Методы оптимизации (1125241), страница 10
Текст из файла (страница 10)
В первом случае, когда Рй, < Рй, из дальнейших рассмотрений исключим точку пу и вместе с нею те точки х сетки (2), для которых !ху — и. ] < (4) Заметим, что некоторые из этих точек могли оказаться исключенными уже на предыдущих шагах. Для нас здесь важно лишь то, что среди исклю- ченных точек заведомо нет таких, в которых значение функции /(х) было бы меньше, чем Р„',. В самом деле, прежде всего /(пу ) = Рй > Р'„ы Для остальных исключенных точек ху имеем: /(ху) — Рва, =/(ху) — /(пу )+ Рй— — Рйа, > — 5!ху — пу ~ + Рй — Рй,, > 0 в силу (6.2) и (4). Таким образом, без дополнительных вычислений значений функции /(х) мы сумели выяснить, что исключенные точки не являются перспективными с точки зрения получения в них значений функции, меньших Рй Рассмотрим вторую возможность, когда Рй ь, = Я;.
< /(пй+,). Тогда из дальнейшего перебора исключаем точку пй, вместе с точкамй ту сетки (2), для которых ]зу- . ]< /(ой ~) — ?гй (5) Нетрудно убедиться, что и в этом случае в исключенных точках значения функции не могут быть меньше Рй„ы В самом деле, здесь /(ху) — Рй =/(ху) — Р, =/(ху) — /(пй „,)+/(и„,) — Рй ) — т ]му — пй ..]+/(пй ~,) — Р > 0 в силу (6,1) и (5).
Общий шаг метода описан. Так как на каждом шаге метода берется новая точка сетки (2), которая еще не исключена из перебора и в которой значение функции /(х) еще не вычислялось, то ясно, что на каком-то шаге такие точки будут исчерпаны и описанный процесс закончится за Ьг шагов, )т/ < и, перебором точек пп ц„..., пн сетки (2) и вычислением Р„= ппп /(пй)аа ш!и /(хй). 1 кй<в ! <й<а Теорема 3. Лусть сетка тачек (хы..., х„) определены согласно (2), пусть /(х) — произвольная функция из класса Я(Ь). Тогда найденная методом последовательного перебора (4), (5) величина Р„= шш Р(х,.) решает задачу (1).
Док аз ател ьство. Поскольку система отрезков [хй — Ь/2, хй+ Ь/2], з =1,..., и, образует покрытие отрезка [а, 6], то для любой точки и е [а, 6] найдется точка ту сетки (2) такая, что ]х — х,.~ < Ь/2. Тогда /(х) =/(х)— — /(х,)+/(ху) > — х.]х — ху]+Р, > — ЬЬ/2+Р,„=Р— г для любого хе[а, 6], Следовательйо, /, > Є— г, т. е. выполняется неравенство (1).
Теорема 3 доказана. П Метод (4), (5), как и метод (3), в худшем случае может превратиться в метод простого перебора точек сетки (2), В то же время ясно, что для многих функций /(х) Е Я(Ь ) этот метод гораздо эффективнее метода простого перебора, так как если величины Рй — Р„', ы /(пйа.) — Рй в (4), (5) доста. точно большие, то многие точки сетки (2) могут оказаться исключенными из перебора без вычисления в них значений функции.
К методу покрытий мы еще вернемся в й 5.13. Упражнения П Пусть одним из вышеописанных методов покрытий найден ппп /(хй) = /(хй). Можно 1<й< ли принять хй за приближение к миожеству Х,? Оценить погрешность р(хй, Х„) для метода (2) иа классе Я(ь); рассмотреть функцию /(х) = ь(х — а) — е/2 при а < х < а+ е/о, /(х) = е(б — х]/(2(ь -а- е/й)) при а+ в/< х < б, где е > о — малое число. Оценить р(хй, х ) для методов (3) и (4), (б) иа классе Я(Ь).
2. Найти оптимальный пассивный и оптимальный последовательный методы иа классе фуикций Я(С) (218; 611; 755!. 32 г е методы минимизлции ФУНКций однОЙ пн еменной 5 8. ВЫПУКЛЫЕ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ 33 5 й. Выпуклые функции одной переменной Рассмотрим класс функций, для которых существует более эффективный вариант метода ломаных, когда ломаные составляются из отрезков касательных и лучше аппроксимируют минимизируемую функцию.
Речь идет, о выпуклых функциях, играющих важную роль в теории экстремальных задач. Определение 1. Функция /(х), определенная на отрезке [а, Ь), называется выпуклой на этом отрезке, если /(гви+(1 — се)е) < св/(и)+(1 — св)/(е) (1) при всех и, е Е [а, Ь), гв Е [О, 1]. Когда а пробегает отрезок [О, 1], точки (гви+(1 — а)е, гв/(и)+(! — ы)/(е)) на плоскости "переменных (х, /) пробегают хорду АВ, соединяющую точки А = = (и, /(и)) и В = (е, /(е)) на графике функций = /(х), Поэтому неравенство (1) имеет простой геометрический смысл: график А выпуклой функции на любом отрезке [и, е) С [а, 6] находится не выше хорды, соединяющей точки грао фика (и, /(и)) и (е, /(е)) е е (рис.
1.3). Примерами функций, выпуклых на любом отрезке, могут служить функции /(х) = х~, /'(х) = [х[, /(х) = х. Наряду с выпуклыми функциями в литературе рассматривают вогнутые функции. О п р еде л е н и е 2. Функция /(х) называется вогнутой на отрезке [а, 6], если /(сии+ (! — св)е) > ги/(и) + (! — сх)/(е) при всех и, е Е [а, Ь], ги Е [О, 1], Между выпуклыми и вогнутыми функциями существует простая связь; если /(х) вогнута на [а, 6], то -/(х) выпукла на этом же отрезке. Учитывая эту связь, достаточно ограничиться изучением свойств выпуклых функций. Т е о р е м а 1, Для выпуклости функции /(х) на отрезке [а, 6) необходимо и достаточно, чтобы (/(и) — /(е))/(и — е) < (/(ю) — /(е))/(ю — е) < (/(ю) — /(и))/(ю — и) (2) привсвхи,е,ю, а<е<и<ю<6, Доказательство.
Необходимость. Пусть функция /(х) выпукла на [а, 6). Нетрудно проверить, что и = ае+ (1 — св)ю, где гв = (ю— — и)/(ю — е) (О < гв < 1), Отсюда с учетом выпуклости функции /(х) имеем /(и) < (ю — и)/(е)/(ю — е) + (1 — (ю — и)/(ю — е))/(ю), или (ю — е)/(и) < (ю — и)/(е) + (и — е)/(ю).
Последнее неравенство можно переписать в двоякой форме: (ю — е)(/(и) — /(е)) < (и — е)(/(ю) — /(е)), или (>с — ий/(ес) — /(е)) < (ю — еН/(ю) — /(и)), от да будет следовать (2), /[ о с т а т о ч н о с т ь. Пусть /(х) удовлетворяет одному из неравенств (2). Отправляясь от этого неравенства и проделав предыдущие преобразования в обратном порядке, убеждаемся в том, что /(х) выпукла на отрезке [а, 6].
П Йетрудно понять геометричесхий смысл неравенств (2) (см. рис, 1.3), если вспомнить, что (/(и) — /(е))/(и — е) представляет собой угловой коэффициент хорды АВ, соединяющеи точки А =(и, /(и)) и В = (е, /(е)) на графике функции / = /(х). Тес рема 2. Выпуклая на отрезке [а, Ь) функция /(х) в кахсдой внутренней точке и отрезка [а, Ь] непрерывна и имеет конечную правую производную 1пп (/(и+ Ь) — /(и))/Ь =/'(и+0), конечную левую производную 1пп (/(и) — /(и — т))/т = /'(и — О), причем /'(и — О) < /'(и+О) при всех и е (а, Ь). Доказательство. Из теоремы 1 следует, что (/(и) — /(и — т))/т < (/(и) — /(и — Ь))/Ь < < (/(и+ Ь) — /(и))/Ь < (/(и+ т) — /(и))/т (3) при всех т, Ь, лишь бы 0 < Ь < т и точки и, и х Ь, и х т е (а, 6) (рис.
1А). Неравенства (3) означают, что величина (/(и+ Ь) — /(и))/Ь монотонно убывает при убывании Ь и ограничена снизу, например, величиной (/(и)-/(и+ + т))/т, не зависящей от Ь, Отсюда следует существование правой производной Г(и + 0). Аналогично доказывается существование левой производной /'(и — 0). Из (3) при Ь- + 0 получаем неравенство /'(и — 0) < < /'(и+ О). Из существова- О х яра~ой производных следует непрерывность функции /(х) при всех Рис. Е4 значениях х Е (а, Ь). П Заметим, что на концах отрезка [а, Ь) выпуклая функция может не иметь соответствующей односторонней производной и, более того, здесь она может терпеть разрыв.
Пример 1. Пусть /(х) = х при О < х < 1, /(0) = /(1) = 2, Очевидно, эта функция выпукла на [О, 1), но на концах отрезка терпит разрывы. Пример 2. Функция /(х) = — ЕУ[ — хз выпукла и непрерывна на отрезке [ — 1, 1], но на концах отрезка не имеет конечных производных /'(!— — 0), /( — 1+ 0). 2 Ф.п, Васильев 6 8.
ВЫПУКЛЫЕ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ 35 34 Гк !. МЕТОДЫ МИНИМИЗЛЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ Т е о р е м а 3. Пусть функция /(х) выпукла на отрезке [а, Ь] и имеет конечныв производные /'(а+ 0), /'(Ь вЂ” 0). Тогда /'(а+ 0)(и — е) < /(и) — /(е) < /'(Ь вЂ” 0)(и — е) (4) при всех и, е (а < е < и < Ь), так что /(х) на [а, Ь] удовлетворяет условию Липиьица (6.1) с постоянной 7, = тахЩ'(а+ 0)[; [/'(Ь вЂ” О)!). Доказательство. Из теоремы 1 имеем (/(а+ Ь) — /(а))/Ь < (/(е) — /(а))/(е — а) < с (/(и) — /(е))/(и — е) < (/(Ь) — /(и))/(Ь вЂ” и) < (/(Ь) — /(Ь вЂ” Ь))/Ь для всех Ь > О, а+ Ь < е < и < Ь вЂ” Ь. Отсюда при Ь- +О получаем /'(а+ 0) < (/(и) /(е))/(и — е) < /'(Ь вЂ” 0), что авносильно (4) при любых и, е (а< е < и < 6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
