Ф.П. Васильев - Методы оптимизации, страница 3

Последовательность х„= к (к =1,2,...) является минимизирующей, так как 1!ш Дх,) =О, но р(х„, Х,) = к не стремится к нулю. Теперь перейдем к формулировке задачи минимизации функции г" (х) на множестве Х. Здесь возможны различные подходы. Обычно принято разли- чать задачи двух типов. К первому типу относят задачи, в которых требу- ется определить величину Т, = !и! Т(х). Сразу жс подчеркнем, что в задачах хЬХ первого типа неважно, будет ли множество Х. точек минимума г"(х) на Х непустым или оно пусто.

Ко второму типу задач относят те задачи, у кото- рых множество Х, непусто и требуется наряду с Т„найти какую-либо точку х, е Х,. Здесь возможно дальнейшее уточнение постановки задачи. Можно искать точку х. Е Х„обладающу1о каким*либо дополнительным свойством (например, ближайшую к началу координат). Бывают ситуации, когда важ- но найти все множество Х„или какую-либо ее часть, представляющую, скажем пересечение Х„с некоторым заданным множеством. Заметим, что получить точное решение задачи первого или второго типа удается лишь в редких случаях.

Поэтому на практике при решении задач первого типа обычно строят какую-либо минимизирующую последователь- ность (х,) для функции Т(х) на Х и затем в качестве приближения для г"„ берут величину ('(х„) при достаточно большом к. Аналогично для прибли- женного решения задач второго типа достаточно построить минимизирую- щую последовательность (х„), которая сходится ко множеству Х, в смысле определения 5, и в качестве приближения для 1'„ и точки 'х, Е Х, взять соответственно величину Т(х„) и точку х„' при достаточно большом к. Как показывает пример 5, в отличие от задач первого типа не всякая минимизирующая последовательность может быть использована дпя полу- чения приближенного решения задач второго типа. Построение минимизи- рующих последовательностей, сходящихся ко множеству Х., в общем слу- чае требует привлечения специальных методов. В настоящей главе будем рассматривать лишь такие задачи второго типа, у которых любая минимизи- рующая последовательность сходится к Х,.

Один такой класс задач дается следующей теоремой, называемой теоремой Вейерштрасеа !327; 350; 352; 534]. Те о р ем а 1. Лусть Х вЂ” замкнутое ограниченное множество из В, функция Г"(х) непрерь1вна на Х. Тогда 1(х) ограничена снизу на Х, множество Х„точек минимума Т(х) на Х непусто, замкнуто и любая минимизирующая последовательность (х,) сходится к Х,. Несколько более общий факт будет установлен в $2.1, из которого также будет следовать теорема 1. Предлагаем читателю вернуться к примерам 1- 5 и выяснить, в каких случаях и какое из условий теоремы 1 нарушено и к чему это приводит, Возможна и более широкая постановка задач минимизации второго ти- па — когда ищутся не только точки минимума в смысле определения 1, но и точки так называемого локального минимума. Определение 6.

Точка ь. е Х называется точкой локального ми- нимума функции Т(х) на множестве Х со значением с= Т(ь.), если сущест- вует такое число а > О, что у(ь,) < ! (х) для всех х Е Х П(х *1х — ь ~ < а) = = 0„(ь,). Если при некотором а > 0 равенство г" (ь,) = г'(х) для х е О,(ь,) возможно только при х = ь„, то ь, называют точкой строгого локального минимума.

13 12 Гл. 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ $1. ПОСТАНОВКА ЗАДАЧИ Для функции, график которой изображен на рис 1.1, точки х, х„х4 являются точками строгого локального минимума, а в точках, удовлетворяющих неравенствам хз < ( х ( хз и хз ~ (х ~ (хэ, реализуется нестрогий локальны и м ин им ум. Функция из примера 1 в точках х„ = = 1/й (й = Ы, х2/ имеет строгий локальныи минимум на Х = К, а в точке х. = Π— нестрогий локалвный минимум. Точки локального мини- мума, в которых минимум о=а *1 2 *з з з аз *т хз *э =х'о достигается в смысле опре- деления 1, часто называют Рис. 1.1 точками глобального или абсолютного минимума функции /(х) на множестве Х. Выделим класс функций, у которых все точки локального минимума являются точками глобального минимума.

Определен не 7. Функциго /(х) назовем унимодальной на отрезке Х = [а, [)], если она непрерывна на [а, [)] и существуют' числа с2,,9 (а< ( а ()2 < 6) такие, что: 1) /(х) строго монотонно убывает при 'а ( х < ст (если а< сх); 2) /(х) строго монотонно возрастает при !2 < х < [г (если !2 < [г); 3) /(х) = /„ = [и[ /(х) при ст < х <,д, так что Х, = [ст, Я, Случаи, когда один или два из отрезков [а,сг], [ст,)2],[?3, 6] вырождаются в точку, здесь не исключаются. В частности, если сг = )3, то /(х) назовем строго унимодальной на отрезке [а, 6].

Функция из примера 2 унимодальна на любом отрезке [а, [?]; функция из примера 1 строго унимодальна на [2/3,2], но не будет унимодальной на отрезке [1/2, 2]. Нетрудно видеть, что если функция /(х) уннмодальна на [а,[г], то она остается унимодальной и на любом отрезке [с, д]С [а,[г], В заключение кратко остановимся на задаче максимизации функции. Определен не 8. Функция /(х) называется ограниченной сверху на множестве Х, если существует такое число В, что /(х) < В при всех х е Х.

Функция /(х) не ограничена сверху на Х, если существует последовательность (х,) е Х, для которой !пп Дхь) =+оо. Функцию /(х) называют ограниченной на Х, если она ограничена на Х сверху и снизу. Определение 9. Если функция /(х) ограничена сверху на Х, то число /" называется верхней гранью /(х) на Х в том случае, когда: 1) /(х) < /* для всех х Е Х; 2) для любого числа е > О найдется такая точгса х, е Х, что /(х,) > /' — е. Если /(х) не ограничена сверху на Х, то по ойределению принимается /'=со.

Последовательность (х ~е Х называется максимизируюгцей для /(х) на Х, если [пп /(ха) =/*. сли существует такая точка х' е Х, что /(х*) =/*, то х" называется точкой максимума /(х) на Х, а величина /(х") — наибольшим или максимальным значением /(х) на Х, Множество точек максимума /(х) на Х будем обозначать через Х", верхнюю грань — через /'= зцр /(х). *ах Заметим, что верхняя грань и максимизирующая последовательность всегда существуют, а максимальное значение может не существовать.

Если выполнены условия теоремы 1, то /" < со, Х' ф [с) и любая максимизирующая последовательность (х„) сходится к Х'. В задачах максимизации также можно различать задачи двух типов: в задачах первого типа ищется величина /*, а в задачах второго типа ищется /' и какая-либо точка х" е Х*. Нетрудно видеть, что зпр /(х) = — !п( ( — /(х)), асх аех причем любая точка максимума и любая максимизирующая последовательность для /(х) на Х является точкой минимума и соответственно минимизирующей последовательностью для функции — /(х) на Х.

Это значит, что любая задача максимизации функции /(х) на Х равносильна задаче минимизации функции — /(х) на том же множестве Х. ! !оэтому мы можем ограничиться изучением лишь задач минимизации. Наконец, немного о точках локального максимума, О п р е д е л е н и е 10. Точка и" я Х называется точкой локального максимума функции /(х) на множестве Х, если существует такое число ст >О, что/(о*) >/(х) для всех х~Хй(х: [х-и*! < сг) =О„(п). Если при некотором ст > О равенство /(и') = у'(х) для х е 0„(о*) возможно только при х = и*, то о' называют точкой строгого локального максимума. Для функции, график которой изображен на рис.

1.1, точки х„х„х„х,о являются точками строгого локального максимума, а в точках, удовлетворяющих неравенствам х, < х < х и х, < х < х„реализуется нестрогий локальный максимум; х, — точка глобального максимума. Множество всех точек локального минимума и максимума функции на множестве Х принято называть точками локального экстремума функции на этом множестве или, проще, точками экстремума. Для обозначения задач минимизации (или максимизации) функции /(х) на множестве Х часто пользуготся следующей краткой символической зап исыо: /(х) — г1п[г х е Х (у(х) е зпр, х Е Х), при необходимости дополнительно уточняя постановку задачи; при этом минимизируемуго (максимизируемую) функцию /(х) называют целевой функцией, множество Х вЂ” допустимым множеством.

Упражнении 1. Построить минимизирующую и максимизирующую последовательности для ~ункции ?(х) = агс!их на Х = В. Достигает ли функция своих нижней и верхней граней на м. 3. Пусть ?(х) = [хз — 1[ при хи' 1 и г(1) = 1. Найти множество Х, точек минимума 2"(х) на Х = и. Могкно ли утверждать, что любая минимизирующая последовательность для этой функции будет сходиться к Х,? 3. Найти все точки локального экстремума функции г'(х) = [[[х~ — 1[ — 1[ — 1! иа отрезке [а, 6[ при различных а, 6.

При каких а, Ь эта функция будет унимодальной на [а, Ь)? 2 4, Выяснить, на каких отрезках будут унимодальными функции г(х)= е ?(х) = х г(х)= = -хз, У(х) = т/[х[, 2" (х) = соз х. б. Если функция С(ь) унимодальна на отрезке [с, а), то функция г"(х) = О((а — с)(х— — а)/(6 — а)+ с) унимодальна на отрезке [а, Ь!. Доказать. 15 14 Гл. 1, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ З 2, КЛАССИЧЕСКИЙ МЕТОД 6.