Введение к работе
Актуальность темы. Задача выпуклой максимизации (вогнутой минимизации) представляет собой типичный пример задачи глобальной оптимизации. Она состоит в нахождении глобального максимума выпуклой функции на выпуклом замкнутом множестве Q с R^
f(x) -> sup.
Ее характеристическое свойство состоит в том, что максимум достигается в экстремальной точке множества планов.. Как правило, задача имеет большое число локальных экстремумов, что делает неэффективным применение методов, используемых в выпуклой минимизации. Ввиду вычислительной сложности задачи, в настоящее время возможно решать лишь задачи умеренной размерности, где \N\ не превышает нескольких десятков.
На основе детерминистского подхода, развиваемого Туем, Хор-стом, Тхоаи, Тхиеу, Конно и другими, разработан ряд конечных методов нахождения глобального максимума. Один из них, алгоритм внешних аппроксимаций, основан на построении последовательности вложенных множеств
RN D Z(0) D Z(l) _ D n
и решении последовательности более простых задач вида f(x) —> max, s — 0,1,... .
В алгоритмах Тхиеу-Тама-Бана и Хорста-Тхоаи-Де Ври для многогранных множеств Q известны все вершины и крайние рецессивные направления внешних аппроксимаций Z^s\ на которых оцениваются значения целевой функции. Максимум на внешней аппроксимации дает верхшою оценку максимума на Л. Каждая следующая внешняя аппроксимация получается из предыдущей добавлением еще одной опорной гиперплоскости, отсекающей текущий глобальный максимум. Процесс продолжается до тех пор, пока такую гиперплоскость удается построить. В упомянутых методах она выбирается среди ограничений множества планов Q.
Вычислительная сложность метода обусловлена необходимостью перебора всех вершин и крайних рецессивных направлений многогранного множества Z^. Поэтому желательно, чтобы внешние аппроксимации были максимально просты. На общую скорость вычислений влияет также эффективность алгоритма перебора вершин и крайних рецессивных направлений многогранного множества. В контексте алгоритма внешних аппроксимаций используются переборные методы, разработанные Тхиеу, Тамом, Баном и Хорстом, Тхоаи, Де Ври. Имеются также работы Ависа, Фукуды и других, посвященные исключительно этой задаче, вне связи с задачей выпуклой максимизации.
В диссертационной работе построена разновидность алгоритма внешних аппроксимаций для решения задачи билинейного программирования. Метод эффективно использует вырожденность задачи, если таковая имеется. Для вырожденных задач внешпие аппроксимации имеют упрощенную структуру. Усовершенствован также метод перебора вершин и крайних рецессивных направлений многогранного множества.
Второй основной темой диссертации является задача кластерного анализа. Она возникает при обработке больших массивов данных и состоит в определении наиболее естественной в некотором смысле классификации совокупности объектов. Каждую из точек хп в пространстве Шк с массой цп требуется отнести к одному из |Р| кластеров. В качестве критерия часто используется дисперсионный критерий минимизации внутриклассового разброса. В некоторых приложениях на разбиение накладываются дополнительные ограничения, например, требование равенства всех масс кластеров.
Традиционно в кластерном анализе либо довольствуются нахождением одного из локально оптимальных разбиений, либо применяют для глобальной оптимизации методы динамического программирования. Гордон и Хендерсон сформулировали задачу кластерного анализа как задачу невыпуклой оптимизации на многогранном множестве. Для этого было предложено задавать разбие-
ниє в виде 0-1-матрицы, как это делается в задаче о назначениях.
В диссертационной работе установлено, что сформулированная задача может быть сведена к задаче выпуклой максимизации. Задача имеет большую размерность, что не позволяет использовать для ее решения имеющиеся методы глобальной оптимизации. Тем не менее, целевал функдпя оказывается сильно вырожденной. Предложен модифицированный метод внешних аппроксимаций пригодный для решения этой задачи.
Цель работы.
-
Определить возможность детерминистского нахождения глобального оптимума задачи кластерного анализа.
-
Разработать метод решения специальных вырожденных задач невыпуклой оптимизации большой размерности.
-
Реализовать и оттестировать алгоритм глобальной оптимизации на персональном компьютере.
Методика исследования. Исследование опирается на теорию выпуклых многогранных множеств, метод внешних аппроксимаций и объектно-ориентированный подход в программировании.
Научная новизна. В диссертации получены следующие основные результаты.
-
Разработан новый метод генерации отсекающей гиперплоскости в алгоритме внешних аппроксимаций для задачи билинейного программирования;
-
Предложена модифицированная версия алгоритма внешних аппроксимаций, эффективно использующая вырожденность целевой функции;
-
Проведено детальное исследование строения множеств уровня опорной функции и продемонстрирована геометрическая интерпретация алгоритма внешних аппроксимаций и двойственности в билинейном программировании;
-
Изучен граф многогранного множества и разработан новый алгоритм построения внутреннего представления многогранного множества;
-
Задача кластерного анализа сведена к задаче выпуклой максимизации;
-
Описан детерминистский алгоритм нахождения глобального экстремума задачи кластерного анализа;
-
Алгоритм внешних аппроксимаций реализовал в виде программы в среде программирования DELPHI (ПАСКАЛЬ).
Практическая ценность. Результаты диссертации могут быть использованы для решения задачи выпуклой максимизации на многогранном множестве, задач билинейного программирования, классификации с дополнительными ограничениями, нахождения всех вершин и крайних рецессивных направлений многогранного множества.
Апробация работы и публикации. По результатам диссертации сделаны доклады на семинаре по нелинейным экстремальным задачам при С.-Петербургском университете, на С.-Петербургском городском семинаре по сложности алгоритмов, на Всесоюзном семинаре "50 лет линейного программирования" (1989). По теме диссертации опубликованы три работы.
Структура и объем работы. Диссертация состоит из введения, четырех глав, разбитых на 12 параграфов, пяти приложений и списка литературы. Объем диссертации — 150 страниц основного текста. Список литературы насчитывает 40 .наименований. В диссертации имеется 10 рисунков и 4 таблицы.