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