Геометрические свойства локально минимальных сетей (1097521), страница 30
Текст из файла (страница 30)
Глава 3. Чокальная структура минимальных сетей. 136 Если вместо надграфика функции З" взять ее подграфик С (1), который определяется как подмножество Во+1, состоящее из всех точек вида (х, Е), таких что х 6 Х и 1 < Д(х), и рассмотреть функции, подграфики которых являются выпуклыми подмножествами в Й"+', то мы получим определение функций, вы щуплых вверх. Очевидно, что если функция 1' выпукла вниз, то функция — 1 выпукла вверх и наоборот. Поэтому для выпуклых вверх функций имеет место анаюг предложения 3.3. в котором следует заменить знак неравенства на обратный.
Хорошо известно, см. например (63], что выпуклые функции обладают рядом полезных свойств, основные из которых перечислены в следующем предложении. Предложение 3.4 Пусть З": Х ь 2 - - выпуклая вниз функция. Тогда она обладает следующими свойствами: ° функция д непрерывна во всех внутренних то ках множества Х; ° функция 1" почи~и всюду дифференцируема, причем, если 1' дифференцируема в точке х 6 Х, то она непрерывно дифференцируема ° в каждой внутренней точке х 6 Х существует производи я Д(х) функции З по любому направлению е 6 Й', т.е.
существует конечный предел ) (х + 1е) — Д(х) с — ~о-ь ° для любого конечного множества точек хм...,хь лсножесспва Х и любых неотрицательных чисел Лм....Ль, таких что их сумма ~, Л,, равна 1, выполнено неравенство ь Л1Д(х1) + . + ЛьД(хь) > ~(Л~х~ + + Льхь); (Точка Л1х1 + .. + Льхь принадлежит множестпву Х, так как Х вьтукло.) ° линейная комбинация выпуклых функций с неотрицательными коэффициентами сама является выпуклой функцией. При решении задач на минимум и максимум для дифференпируемой функции 1 обычно работают с градиентом йгас1~ или, что все 3.1.
Параметрические сети. 137 равно, с касательными плоскостями к графику С(1). Выпуклые функции не являются, вообще говоря, дифференцируемыми, однако, оказывается, понятия касательной плоскости и градиента можно естественным образом обобщить так, чтобы они имели смысл в каждой точке области определения выпуклой функции (а не только в тех точках, где функция дифференцируема). Мы приведем здесь соответствующую конструкцию для функций выпуклых вниз. Для функций выпуклых вверх можно проделать все то же самое, заменяя, где необходимо, знаки неравенств на обратные.
Пусть 1: Х вЂ” ~ К выпуклая вниз функция, и С(у) Е 2"+1 ее график. Рассмотрим семейство гиперплоскостей (П) Е 2" +', проходящих через некоторую точку (х,Д(х)) графика С(Д. Плоскость П из этого семейства называется опорной к надградУику С+(Д е то ске (х, у(х)), если надграфик С+® целиком лежит в одном из замкнутых полупространств, на которые П разбивает яс"+'.
Если П не параллельна оси 1, то это полупространство содержит каждый луч, выпущенный из произвольной точки плоскости П в направлении вектора (0,1) Е К"+'. Ясно., что это условие однозначно определяет рассматриваемое полупространство. Каждая гиперплоскость П, проходящая через (х, 1(х) ) задается у равнением вида (1у,д — х) — 1(1 — 1"(х)) = О, где у Е 2", (у,1) Е Ия+', и (Х, — 1) вектор из 2" е1, ортогональный к П. Ясно, что П является опорной, если и только если для любой точки (у,1) надграфика Се(1) выполнено неравенство (1У, д — х) — (й — 1(х)) < О: в этом случае вектор (1У, — 1), отложенный в точке (х, Д(х)), направтен наружу надграфика С+(Д.
В частности, для точек вида (у, у(у)), принадлежащих надграфику для любого д Е Х, получаем, что (1У, д — х) < 1(у) — 1(х) для произвольной точки у Е Х. Каждый вектор Х Е 1Г, удовлетворяющий последнему соотношению, называется субградиентем д1ункиии у" е точке х. Множество всех субградиентов в точке х, рассматриваемое как подмножество пространства 2", называется субгродиенгпным множеством е точке х и обозначается через Яу(х), Таким образом, каждый субградиент является проекцией на координатное пространство (1 = 0) некоторого вектора (1У, — 1),нормального к опорнои гиперплоскости.
Может возникнуть впечатление, что понятие субградиента 'нелокально" действительно, в определении принимают участие все точки из множества Х. Однако, как видно из следующего предложения, это не так. Глава 3. Локальная структура минимальных сетей. 138 Предложение 3.5 Пусть, как и выше, Х . - выпуклое подмножество в йн. Вектор Х является субградиентом выпуклой вниз функции у: Х вЂ” ~ Гл~ в точке х, если и только если для любого вектора е Е К" выполнено неравенство где через Д(х) обозначена производная функции з' по направленню е в точке х. Понятие субградиентного множества обобщает стандартное понятие градиента в смедующем смысле. Предложение 3.6 Пусть у': Х вЂ” ь К выпуклая внпз функция, и х произвольная внутренняя точка нз Х.
Тогда мноясеслнво Яу(х) С йв непусто, вьлпукло и ограничено. Более того, если яу(х) состоит ровно из одного вектора в, то функция у" дифференцируема в точке х и в = лхасса(х); если хсе Яу(х) состоит более чем из одной точки, то )' недифференцируема в х. Определение. Точку х Е Х назовем стационарной для выпуклой функции у, если среди опорных плоскостей в точке (х, )(х)) имеется горизонтальная плоскость,т.е.плоскость вида )с = сопвс).
Отметим,что точка х является стационарной для функции у если и только если субградиентное множество Яу(х) содержит О. Далее, непосредственно из определений вытекает, что каждая стационарная точка выпуклой вниз функции является ее точкой минимума, а каждая стационарная точка выпуклои вверх функции является ее точкой максимума. Обратно, каждая точка минимума или максимума выпукяои функции является, очевидно, стационарной точкой.
Таким образом, имеет место следующее предложение. Предложение 3.7 Пусть у": Х -+ 1к выпуклая вниз функция. Тогда точка х Е Х является точкой манимума функции у если и только если точка х . - стационарная, т.е. Яу(х) Э О. Оказывается, множество стационарных точек выпуклой функции устроено достаточно просто.
А именно, имеет лсесто следующий результат. Предложение 3.8 Пусть у оыпуклая функция на Х С Кп. Тогда мнозкество стационарных точек функции у" выпукло и, значит, линейно связно. В частности, все стационарные значения функции у" совпадают, т.е. каждый локальный минимум (максимум) является глобальным.
3.1. Параметрические сети. 139 Для дальнейшего нам будет полезно разобраться, как субградиентное множество выпуклой функции, являющейся линейной комбинацией выпуклых функций с неотрицательными коэффициентами, связано с субградиентными множествами исходных функций. Предложение 3.9 Пусть вьтунлая вниз функц я ~: Х вЂ” ь К представлена в виде 1" = ~, о,;~б где а, -- неотрицательные числа, а ~, --.
я вьтуклые вниз функции на множестве Х с й". Тогда в каждой внутренней тлочке х множества Х еубградиентное множество функции э" представимо в виде: т.е. каждый вектор в из 31(х) представим в виде линейной комбинации с коэффициентами ен некоторых векторов в,; из Яб(х), и, обратно, линейная комбинация любых векторов в; е Я~„.(х) с коэффициентами еи принадлежит Яу(х). 3.1.4 Общий случай: сильно локально минимальные параметрические сети Переидем теперь к исследованию локаяьного устройства сильно локально минимальных сетей.
Прежде всего отметим, что неравенства из предложения 3.2 представляют собой необходимое условие сильной локальной минимальности. Однако, оно уже не является достаточным. Принципиальное отличие сильно локально минимальных сетей от слабо локально минимальных состоит в том, что длина первых не увеличивается при деформации сетей с носителем, содержащим целиком компоненту вырождения произвольной вершины приведенной сети. Мы начнем с рассмотрения нескольких типичных примеров таких деформаций,что даст нам возможность сформулировать еще некоторые необходимые условия сильно локальной минимальности.
Пусть Ф произвольная параметрическая сеть, и Ф,*„, некоторая сильно локальная сеть для Ф. Предположим сначала, что все подвижные вершины Ъ;. сети Фгь, движутся под действием рассматриваемой вариации с одинаковой скоростью, т.е. все векторы Е, скорости подвижных вершин 1;; в начальный момент времени равны между собой и равны некоторому вектору Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
