Н.М. Новикова - Дискретные и непрерывные задачи оптимизации, страница 10

Показательство (от противного). Пусть существует направление у б Со(х), не входящее в К(Х, х), т.е. для любой'последовательности, фигурирующей в определении 5, найдется подпоследовательность (т»,у») —. (+О,у): х+ т»у» Е Х, следовательно, »»»4 и' индекс у, такой что уу(х+ т»у») > О. Возможных индексов — конечное число, а различных $ бесконечно много, значит, найдется ограничение, пусть »-е, которое нарушается бесконечное число раэ. Рассмотрим соответствующую подпоследовательность (ег): у;(х+»»„у»,) > О и, устремляя й — оо, получим, что у;(х) > О.

Но из условиях б Х справедливо обратное неравенство, откуда следует равенство, т.е. » б 7(х). Однако для этого» по определения» 4 будем иметь (»уу»(х), у) =' у;(х+ ту') — у»(х), у»(х+ т» у» ) — у;(х) (» ле) (+О,г) т з оо т»» Пришли к противоречию с у б Со(х). Отсюда получаем следующее уеловве регулярносв»в: (7) 0(х) = Со(х). Здесь и далее черта над множеством обозначает его замыкание. Утввгждвнив 6. В сделанных предположениях условие (7) обеспечивает регулярность Х в точке х. Пля ЛОЕАЗАтелъстВА достаточно заметить, что множество К(Х,х) является замкнутым, а включение Со(х) С К(Х,х) приводит к Со(х) С К(Х, х) после взятия операции замыкания. Утвкгждкник 7. Достаточным для (7) является (8) С (х) фй.

Доклэяткльство. Из ~8)для алгебраической суммы С и С следует:С+Со~Со т.е,С+СссСа аСеэОдаетС+Се~С И из линейности оператора замыкания и замкнутости С получаем (7). Для выпуклых Х выполненяе (8) и, следовательно, регулярность (в любой точке) ограничений (3) гарантируется условием Слзйзаера (пх' б Х: у,'(х) ( О УЛ б М). Линейные ограничения всегда регулярны (множество С совпадает с контингентным конусом), хотя условие Слэйтера илн (8) для них может не выполняться. Другие типы условий регулярности, а также условия регулярности.для смешанных систем ограничений равенств и неравенств см. в [4-6].

В частности, классическим условием регулярности для ограничений-равенств является лннейнзл независимость градиентов ограничений в экстремальной точке. УПРАЖНЕНИЕ 8. Получить теорему двойственности ЛП как следствие теоремы Куна-'Танкера (для случая оэЛП). Условия оптимальности служат основным инструментом теоретического исследования задач условной оптимизации. Чтобы численно (приближенно) найти условный экстремум с их помошью, применяют методы безусловной оптимизации для поиска седловой точки функции Лагранжа или комбинируют штрафную функцию с функцией Лагранжа для получения точного гладкого штрафа. К сожалению, все зти методы останавливаются в первом попавшемся локальном экстремуме. Глобальный оптимум можно искать, перебирая локальные оптимумы, но для задач неодномерной минимизации не понятно, как находить все локальные оптимумы.

Некоторые из сушествуюших подходов к решению задач глобальной оптимизации приводятся в следующем параграфе. 4. СПОСОБЫ РЕШЕНИЯ ПЕРЕБОРНЫХ ЗАДАЧ Литература: 2. Пападимитрну Х., Стайглиц К. Комбинаторная оптимизация. Мл Мир, 1985. 6. Мину М. Математическое программирование.

Мл Наука, 1990. 110. Рмобвльиаа оптимизация. Метод ветвей и границ Слрчаааыа а последоеательныб перебор. Метод еетееа а ерааии е елобальаой опеьимиэаиии. Описапае а стратегии метода. 1. Как уже отмечалось ранее, задачи глобальной оптимизапии (т.е. в невыпуклом случае задачи оптимизации вообще) являются переборными. Переборные алгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решении каждой конкретной задачи существенным образом зависит от способа организации перебора. Если мы готовы оставить возможность или невозможность решения нашей задачи на волю случая, то естественно использовать случайный перебор.

Этот способ перебора обычно является самым простым и, как правило, экономит память. Лля задачи поиска глобального миыимума ему соответствует следующий метод Моите-Карло. Пусть решается задача (1) иэ 18, где (для упрощения изложениа) множество ограничений Х вЂ” единичный и-мерный куб. Выбираем в соответствии с равномерным распределением на Х случайные точки х', в которых вычисляем значение целевой функции, запоминаем текущее наименьшее значение — реаорд — и реализующую его точку. Тогда Уе > О вероятность Р(~выпях ) — ~'~ > е) - О при $ - оо. Сходимость такого метода будет довольно медленной. При этом не известно, на каком расстоянии от точки минимума находится полученная реализация. Сузим класс рассматриваемых задач (1), предположив вдобавок к предыдущему, что функция цели липшицева на Х с константой Ьг У чЬ!р(Х,Ь), т.е.

)У(х) — У(х')) < Ц)х — х'~) 'ех,х' б Х. И ые рассчитывая найти точное решение, зададимся подходящим е > О с 51 пелью поиска с-приближенного решения х': /(х') < /(х*) + с. (На близость х' и х* никакик условий не накладывается.) Теперь мы можем применять методы детерминированного перебора.

Пассивный (не использующий при выборе очередной точки информацию, полученную для предыдуших) способ поиска приводит к полному перебору: разобьем Х на подкубы Ху так, чтобы зх, х' б ХУ: 11х — х')~ < 6 =' с/Ь, в каждом ХУ берем произвольную точку хг и полагаем /(х') =' пип/(х~). Очевидно, х' и есть искомое с-приближенное решение. (Лействительно, Уу, Ух б ХУ /(х') < /(хэ) < /(х) + с по условию Липшица, и, в частности, для х = х' имеем /(х') < /(х') + с — соответствие с определением.) Однако сторона каждого у-го подкуба равна с/(Ь~/и), а всего подкубов и, следовательно, вычислений значений целевой функции будет (Ь~/и/с)" в любом случае, чтб не мыслимо даже для десятка переменных. Поэтому разрабатываются методы последовательного перебора, позволяющие учитывать уже вычисленные значения и адаптироваться к нехудшему случаю.

Предположим, что уже вычислены значения функции в точках х',...,х1 ' и рекордным оказалось значение /(х') = Ю. Тогда, если /(хз) < /(х"),то обновляем рекорд г:= у, И:= /(х1), а если /(хз) > р/(х"), то можно не вычислять значений функции на множестве Ту(Л) =' (х б Х: ~)х — хэ)~ < (/(х1) — Н)/Ц, так как это не даст новогорекорда(иберах б Т /(х') — /(х) < Ц!х-ФЦ < /(хз)-/(х'), т.е. /(х) > /(х') = ГС, и значит, среди них нет глобально-оптимального решения). Обновление рекорда в принципе позволяет "отбросить" аналогичные множества Т (1с) для 1 = 1,..., у — 1. Естественно, в Т;, Т; могут попасть и точки х с уже вычисленз ным значением /(х") (которые таким образом вычислялись зря). Поэтому хотелось бы так организовать перебор, чтобы по возможности уменьшить число подобных "зряшных" вычислений. К сожалению, оптимальной стратегии организации перебора для многомерных задач нет.

Использование случайных точек х' приводит к проблеме хранения и обновления сложного множества ОТ;(И) заведомо не оптимальных точек. Метод послойного перебора дает возможность сокращения лишь по одной переменной. Лля задач большой размерности 52 предлагается (различными авторами) следуюший метод перебора по схеме вгптвгй и гранич. 2.' Мгглод вгтвесй и границ (МВГ) для глобальной минимизации.

Пусть х' — пентр куба Х. Вычисляем )(хт) и присваиваем это значение рекорду Я:= у(хт). Разбиваем куб на 2" одинаковых подкубов Хтт со стороной 1/2 и вычисляем значения целевой функции в их центрах: у(хтт), т' = 1,...,2", обновляя по ходу вычислений значение рекорда П:= штп; у(хтт). Проверяем выполнение условия Х" С Ттт(К), т = 1,..., 2" и отбрасываем соответствующие подкубы. Каждый из оставшихся разбиваем на 2" одинаковых подкубов Хэ'т со стороной 1/4 и поступаем, как прежде. На любом шаге у нас формируется множество К "кубиков" со сторонами 2 ', 1 ) 2, целое. Правило выбора очередного кубика для разбиения называется нраеилом егптвлгния — возможные варианты приводятся ниже.

Кубики со стороной не больше г/(Ь~/к) исключаются из множества К вЂ” дробление кубика заканчивается. Также исключаются кубики, попавшие в множество ТьЩ (с индексом й — номером кубика) для текущего значения рекорда, — араеило оптсгчгния вгтивгй. Рекорд обновляется при получении меньшего значения целевой функции (аревало нолучгния гранич, тн.г.

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

Если кубик еше не включен в К, его вершина еше нг раскрытие. Порядок закрытия вершины определяется правилом отсечения (своим для каждой массовой задачи — см. также в 111), порядок раскрытия — правилом ветвления (своим для каждой индивидуальной задачи). Различают два вида правил ветвления по типу построения дерева решений (выбора вершин для раскрытия): "в ширину", когда сначала раскрываются 53 все вершины одного яруса до перехода к следуюшему, и "в глубину" — всякий раз раскрывается лишь одна (обычно с лучшим значением рекорда) вершина на ярусе до конца ветви. На практике реализуют некоторую смесь, например, первое правило, пока хватает машинной памяти (в К не слишком много элементов), затем переключаемся на второе.