Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 18
Текст из файла (страница 18)
Различные варианты метода стохастической аппроксимация, строгое обоснование этого метода, различные приложения можно найти в (180). Глава 2 ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ О ЗАДАЧАХ НА ЭКСТРЕМУМ В этой главе собраны основные факты о задачах на экстремум функцкй конечного числа переменных, обычно излагаемые з учебниках но математическому анализу ~10, 160, 165, 233Ь а также некоторые другие зсномогательные формулы и оценки, необходимые для дальнейшего изложения. й 1. Постановка задачи минимизацни.
'Теорема Вейерштрасса 1. Сначала введем обозначения, напомним некоторые определения из линейной алгебры и математического анализа. Через К" будем обозначать п-мерное нещественное линейное пространство, состонщее из вектор-столбцов с действительными координатами и', р', и>', ... (1=1, ..., и); сумма и+и двух вектор-столбцов и произведение аи вектор- столбца и на действительное число а в К" определяется так: и+и= " ", аи= вектор-столбец о=~ "1 называется нулевым.
Вектор-строку, полученную транспонированием вектор-столбца и, обозначим через и'=(и', ..., и"). Там, где не могут возникнуть недоразумения, вектор-столбец или вектор-строку из К" для краткости мы часто будем называть просто вектором или точкой, а знак транспонирования аТ» будем опускать. постАновкА зАдАчи минимизАции 69 Если в К" ввести скалярное произведение двух векторов (и, и) = ~~э~ и1э1, и, и ~ К", то К" превращается в п-мерное евклидово пространство, которое будем обозначать через Е". Длина вектора или норма вектора в Е" определяется так: ,1 э 11/з ) и ) = 1'и, и',11м = ~ ~; ! и1 )1 ~ 1=1 Величину / и 1 1/1 р(11 э) (и э! ~» !111 111(1 1=1 называют евклидовым расстоянием ме1кду точками и, и 1н Е".
Для любых точек и, и, и1 шЕ" справедливо неравенство 1и — и) (!и — й! +!и1 — э), называемое неравенством треугольника. Когда важно подчеркнуть, что скалярное произведение, норма, расстояние взяты именно в Е", мы будем писать <и, э)вэ, ~ 11 (ки, ~ и — 1 (яэ. 2. Перейдем к постановке задачи минимизации. Пусть У вЂ” некоторое непустое множество из Е", а У(и) — функция, определенная на этом множестве. Всюду ниже, если не оговорено противное, мы будем рассматривать лишь функции, принимающие во всех точках иш У конечные вещественные значения. Определения таких понятий, как точка минимума и максимума, наименьшее и наиболыпее значение, ограниченность снизу и сверху, кин1няя и верхняя грань функции У(и) на множестве У, минимизирующая и максимизпрующая последовательность, точка локального и строгого локального минимума и максимума функции, сходимость последовательности к заданному множеству в пространстве Е" получаются из определений 1.1Л вЂ” 1Л.6, 1ЛЗ— 1.1ЛО, нужно лишь под и понимать точку и=(и1, ..., и") из Е, под !и! — норму и в Е".
Поэтому здесь мы не будем воспроизводить определения перечисленных понятий. Примеры 1ЛЛ вЂ” 1.1.5 могут служить иллюстрацией к этим понятиям и в Е", так как функция одной переменной является частным случаем функции и переменных. Нижнюю грань функции 1(и) на множестве У по-прежнему будем обозначать через 1п1 У (и) = Хз, О а множество точек минимума У(и) на У вЂ” через Пэ = (ьи и ен У, У(и) = Уэ). >гл. з 70 пгвдВАРнткльныв сввдкнпя Для обозначения задачи минимизации функции У(и) на мно>кестве У часто будем пользоваться следующей краткой стандартной записью: У(и) - 1п1; и ш (,>. Как и в $1Л, будем различать задачи минимизации двух типов.
В задачах первого типа ищется точное или приближенное значение величины Уз, и здесь неважно, будет ли множество (Уз пустым нли непустым. В задачах второго типа наряду с величиной У„ищется точка и~ У, которая достаточно близка к множеству (Уз или дансе принадле>кит (Уз, — здесь естественно требовать, чтобы Уз) — со, ГзФ8. Для приближенного решения задач обоих типов на практике обычно строят какую-либо минимизирующую последовательность (и„): изен(У, Й = 1, 2, ..., 11шУ(иь) = Уз (чри 5' ~Я возможно, напркмер, из= — ивен(Уз, й=1, 2, ...).
Тогда, как нетрудно видеть, в качестве приближения для Уа мол>но взять величину У(и,) прн достаточно большом й. В том случае, если (и,) сходится к множеству Гз, т. е. р(ию ь>з) = = >п1)иь — и[ — «О при й —, точку и, н соответствующее зкаи« ченне функции У(и,) при достаточно большом Й можно привять за приближенное решение задачи второго типа. Однако, как мы видели в примере 1Л.5, условие 1пп р(иь, 6>з) = 0 имеет место не всегда. Поэтому в задачах второго типа построение минимизирующих последовательностей, сходящихся к (>ч, в общем случае требует привлечения специальных методов. В то же время имеются классы задач второго типа, у которых любая минимизирующая последовательность (и„) сходится к У„.
Эти классы задач хороши тем, что для пх приближенного решения достаточно построить произвольную минимизирующую последовательность (и,) и затем пару (и„У(и,)) при достаточно большом й принять за приближенное решение. Один такой класс задач будет описан ниже в теореме 1. Эту теорему будем называть теоремой Вейерштрасса, поскольку она является некоторым обобщением хорошо известной из учебников по математическому анализу теоремы Вейерштрасса о достижении нижней грани непрерывной функции на замкнутом ограниченном множестве из Е" [10, 160, 165, 233). 3.
Для формулировки теоремы Вейерштрасса пам понадобятся понятия компактного множества, полунепрерывности снизу функции и некоторые другие понятия из математического анализа. Кратко напомним их определения. постановил злдлчп ъшциъпгзхции % О 71 Пусть (и,) = (и„и„...) — некоторая последовательпостгч (и„) яЕ", т. е. и,иЕ" ((г = 1, 2, ...). Точка о называется предельной точкой последовательности (и,), если существует подпоследовательность [и,„), сходящаяся к о. Последовательность (иг) называется ограниченной, если существует постоянная л( ) О такая, что ~и„~ ~ ЛХ для всех й = 1, 2, ...
Множество У пз Е" называется ограниченным, если существует постоянная Л ) О такая, что [и[ < Л для всех и ж Г Множество 0(о, е)= (и: и ~иЕ", ~и — о[( е), представляютцее собой открытый шар с центром в точке о п радиусом е) О, называется з-окрестностью точки о. Точка о ~кЕ" называется предельной точкой множества У ~Е", если любая ее з-окрестность содержит точки из У, отличные от о. Нетрудно видеть, что для любой предельной точки о множества У существует последовательность (и,) ~ У (и„Ф о), сходящаяся к о,— для построения такой последовательности достаточно при каждом (с =1, 2, взять точку и,~ 0(о, 1!Й) (и„ть о). Верно и обратное: если в У существует последовательность (и,) (и, Ф о), сходящаяся к точке о, то о — предельная точка множества К Множество У из Е" называется гаагкнутым, если оно содержит все свои предельные точки. Определение 1.
Множество У из Е" называется компактным, если любая последовательность (и,) ш У имеет хотя бы одну предельную точку о, причем о~ У. Согласно теореме Больцано — Вейерштрасса всякая ограниченная последовательность имеет хотя бы одну предельную точку. Пользуясь атой теоремой, нетрудно доказать, что в Е" компактными являются все замкнутые ограниченные мноягества и только они. Числовая последовательность (х,) =(х„хи ...) называется ограниченной снизу [сгерху], если существует число А такое, что х,) А [х,(А] при всех у =1, 2, ... Коли (х,) пе ограничена снизу [сверху], то существует подпоследовательпость [хг ] такая, что (пп хг = — оо [(пв хг = оо~. Фй ™ (т Определение 2.
Число а называется нижним [герхним] пределом ограниченной снизу [сверху] числовой последовательности (х„) и обозначается через (пп хг = а [П1пха = а|, если: г ',г 1) существует хотя бы одна подпоследовательность [хь ], сходящаяся к а; 2) все предельные точки (х,) не меньше [не больше] числа а, т. е. число а является наименьшей [наибольшей] предельной точкой последовательности (х,).
Иначе говоря, ив нижний [верхний] предел (х,), если для любого е ) О: 1) существует номер У такой, что х„) а — е [х„~ а+ е] для всех (г>Л; 2) для любого номера пг найдется помер (г ) т такой, 72 пгкдздгнтвльнык сэкдвння [гл. 2 что хд (а+ е[хд )а — з].
В том случае, когда (х„) не ограничена снизу [сверху), то по определению принимают )дш хд = — оо [1(шхд — — оо]; если Ншхд = — — оо, то полагают [д ю д д ю Нш хд — — — со; если 1ппха = оо, то 1ппхд = оо. д со д о д м Например, если х,=( — 1)' (Й=1, 2, ...), то 1ппхд — — — 1, д ю Нвтхд= 1; если хд =( — 1)дй (й = 1, 2, ...), то 1пп хд = — со, д о д 1пп хд = оо; если хд = [1 + ( — 1)~])з (й=1, 2,...), то 1пп хд = О, д ~ю дНш хд = оо; если хд = й ' (а = 1, 2,...), то Нш хд = Нш хд = О. д ю д д Для того чтобы числовая последовательность (х„) имела предел, необходимо и достаточно, чтобы Ншхд = Нш хд = а; тогда д о д 1пп хд = а. Определение 3.
Пусть функция Х(и) определена на множестве УшЕ". Говорят, что функция 7(и) полунепрерыепа снизу [сверху) в точке иш У, если для любой последовательности (и„) дн У, сходящейся к точке и, имеет место соотношение 1пп Х(ид)~)У(и) [НшУ(ид)~(У(и)~. Функцию У(и) называют д э ~[д м полупепрерыепой снизу [сверху) на множестве У, если она полу- непрерывна снизу [сверху) в каждой точке этого множества.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
