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