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