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