Исследование по билинейному программированию и кластерному анализу тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ИССЛЕДОВАНИЕ ПО БИЛИНЕЙНОМУ ПРОГРАММИРОВАНИЮ И КЛАСТЕРНОМУ АНАЛИЗУ

01.01.09 — Математическая кибернетика

АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 1997 г.

Работа выполнена на кафедре исследования операций матема-тико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель — доктор физико-математических наук, профессор Малоземов Василий Николаевич

Официальные оппоненты — доктор физико-математических наук, профессор Фрадков Александр Львович

кандидат физико-математических наук, доцент Сокирянская Елена Наумовна

Ведущая организация — Санкт-Петербургский Государственный Электротехнический Университет

сов на заседании диссертационного совета К 063.57.49 по защите диссертаций на соискание ученой степени кандидата наук в Санкт-Петербургском государственном университете по адресу: 198904, г. Санкт-Петербург, Петродворец, Библиотечная пл., 2, матема-тико-механический факультет.

С диссертацией можно ознакомиться в научной библиотеке университета по адресу: 199034, г. Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан "_"_ 1997 г.

Защита состоится

Ученый секретарь диссертационного совета

А. И. Шепелявый

Общая характеристика работы

Актуальность темы. Задача выпуклой максимизации (вогнутой минимизации) представляет собой типичный пример задачи глобальной оптимизации. Она состоит в нахождении глобального максимума выпуклой функции на выпуклом замкнутом множестве С

f(x) sup.

¡¡¡en

Ее характеристическое свойство состоит в том, что максимум достигается в экстремальной точке множества планов.. Как правило, задача имеет большое число локальных экстремумов, что делает неэффективным применение методов, используемых в выпуклой минимизации. Ввиду вычислительной сложности задачи, в настоящее время возможно решать лишь задачи умеренной размерности, где \N\ не превышает нескольких десятков.

На основе детерминистского подхода, развиваемого Туем, Хор-стом, Тхоаи, Тхиеу, Конно и другими, разработан ряд конечных методов нахождения глобального максимума. Один из них, алгоритм внешних аппроксимаций, основан на построении последовательности вложенных множеств

MN D Z(0) D Z{1) _ D n

и решении последовательности более простых задач вида fix) —> max, s — О,1,... .

В алгоритмах Тхиеу-Тама-Бана и Хорста-Тхоаи-Де Ври для многогранных множеств Г2 известны все вершины и крайние рецессивные направления внешних аппроксимаций на которых оцениваются значения целевой функции. Максимум на внешней аппроксимации дает верхнюю оценку максимума на Л. Каждая следующая внешняя аппроксимация получается из предыдущей добавлением еще одной опорной гиперплоскости, отсекающей текущий глобальный максимум. Процесс продолжается до тех пор, пока такую гиперплоскость удается построить. В упомянутых методах она выбирается среди ограничений множества планов Q.

Вычислительная сложность метода обусловлена необходимостью перебора всех вершин и крайних рецессивных направлений многогранного множества Поэтому желательно, чтобы внешние аппроксимации были максимально просты. На общую скорость вычислений влияет также эффективность алгоритма перебора вершин и крайних рецессивных направлений многогранного множества. В контексте алгоритма внешних аппроксимаций используются переборные методы, разработанные Тхиеу, Тамом, Баном и Хорстом, Тхоаи, Де Ври. Имеются также работы Ависа, Фукуды и других, посвященные исключительно этой задаче, вне связи с задачей выпуклой максимизации.

В диссертационной работе построена разновидность алгоритма внешних аппроксимаций для решения задачи билинейного программирования. Метод эффективно использует вырожденность задачи, если таковая имеется. Для вырожденных задач внешние аппроксимации имеют упрощенную структуру. Усовершенствован также метод перебора вершин и крайних рецессивных направлений многогранного множества.

Второй основной темой диссертации является задача кластерного анализа. Она возникает при обработке больших массивов данных и состоит в определении наиболее естественной в некотором смысле классификации совокупности объектов. Каждую из точек хп в пространстве с массой (1„ требуется отнести к одному из |Р| кластеров. В качестве критерия часто используется дисперсионный критерий минимизации внутриклассового разброса. В некоторых приложениях на разбиение накладываются дополнительные ограничения, например, требование равенства всех масс кластеров.

Традиционно в кластерном анализе либо довольствуются нахождением одного из локально оптимальных разбиений, либо применяют для глобальной оптимизации методы динамического программирования. Гордон и Хендерсон сформулировали задачу кластерного анализа как задачу невыпуклой оптимизации на многогранном множестве. Для этого было предложено задавать разбие-

ние в виде 0-1-матрицы, как это делается в задаче о назначениях.

В диссертационной работе установлено, что сформулированная задача может быть сведена к задаче выпуклой максимизации. Задача имеет большую размерность, что не позволяет использовать для ее решения имеющиеся методы глобальной оптимизации. Тем не менее, целевая функция оказывается сильно вырожденной. Предложен модифицированный метод внешних аппроксимаций пригодный для решения этой задачи.

Цель работы.

1. Определить возможность детерминистского нахождения глобального оптимума задачи кластерного анализа.

2. Разработать метод решения специальных вырожденных задач невыпуклой оптимизации большой размерности.

3. Реализовать и оттестировать алгоритм глобальной оптимизации на персональном компьютере.

Методика исследования. Исследование опирается на теорию выпуклых многогранных множеств, метод внешних аппроксимаций и объектно-ориентированный подход в программировании.

Научная новизна. В диссертации получены следующие основные результаты.

1. Разработан новый метод генерации отсекающей гиперплоскости в алгоритме внешних аппроксимаций для задачи билинейного программирования;

2. Предложена модифицированная версия алгоритма внешних аппроксимаций, эффективно использующая вырожденность целевой функции;

3. Проведено детальное исследование строения множеств уровня опорной функции и продемонстрирована геометрическая интерпретация алгоритма внешних аппроксимаций и двойственности в билинейном программировании;

4. Изучен граф многогранного множества и разработан новый алгоритм построения внутреннего представления многогранного множества;

5. Задача кластерного анализа сведена к задаче выпуклой максимизации;

6. Описан детерминистский алгоритм нахождения глобального экстремума задачи кластерного анализа;

7. Алгоритм внешних аппроксимаций реализовал в виде программы в среде программирования DELPHI (ПАСКАЛЬ).

Практичёская ценность. Результаты диссертации могут быть использованы для решения задачи выпуклой максимизации на многогранном множестве, задач билинейного программирования, классификации с дополнительными ограничениями, нахождения всех вершин и крайних рецессивных направлений многогранного множества.

Апробация работы и публикации. По результатам диссертации сделаны доклады на семинаре по нелинейным экстремальным задачам при С.-Петербургском университете, на С.-Петербургском городском семинаре по сложности алгоритмов, на Всесоюзном семинаре "50 лет линейного программирования" (1989). По теме диссертации опубликованы три работы.

Структура и объем работы. Диссертация состоит из введения, четырех глав, разбитых на 12 параграфов, пяти приложений и списка литературы. Объем диссертации — 150 страниц основного текста. Список литературы насчитывает 40 .наименований. В диссертации имеется 10 рисунков и 4 таблицы.

Содержание работы

Во введении дан краткий исторический обзор, проанализированы имеющиеся подходы к решению задач и сформулированы основные результаты диссертации.

В главе I рассматривается задача билинейного программирования

у) (в, Фу) sup , X с С

где X и У — многогранные множества. В §1 проводится предварительный анализ задачи. Рассматриваются функции

V>(y) - таxF{x,y)ty G Шм, ф) = тж?{х,у),х 6 ЖЛ\ хел

Вследствие билинейности функции значения ¡р vi ф вычисляются решением соответствующих задач линейного программирования. Исходная задача формулируется как задача максимизации выпуклой кусочно-линейной функции

<р(х) —¥ тгос.

Ей соответствует двойственная задача

А. —» min ,

XClevAV5

где levA tp — {х 6 Rw|<p(x) < А} есть множество уровня А функции у?. Множество уровня, содержащее допустимую область X, следует "сжимать" до тех пор, пока не произойдет касание. Точка, где X касается 1еуд ip, доставляет глобальный оптимум поставленной задаче.

В §2 для решения задачи билинейного программирования предлагается алгоритм, основанный на методе внешних аппроксимаций. При упрощающем предположении, что множества X и Y непусты и ограничены, алгоритм формулируется следующим образом.

Шаг 0. Построить симплекс Л включающий X. Это начальная внешняя аппроксимация множества планов. Найти ее внешнее представление в виде пересечения опорных полупространств

= {х € KN\(hk, х) — к G #(0)}, и внутреннее представление в виде выпуклой комбинации экстремальных точек

z® = ConvK »е /(0)}. Шаг 1. На s-й итерации имеется многогранник Z^ Э X, известны его внешнее и внутренннее представления. Вычислить

значения целевой функции в каждой из вершин многогранн-ника Z^ и найти максимальное из них,

¿М = arg таху?(^), = =

В силу выпуклости ц>, точка z^ доставляет ей максимум на всем множестве Z^'h Так как X С Z^s\ то значение является верхней оценкой максимума ip на X. Шаг 2. Вычислить

у[з) = arg max , у), <p(z(s>) = T{z[s), у w) уеУ

:c(s) = arg maxf(i,j,W), ^(yw) = T{x^s\y{s)) xax

Так как xW e X и yW e Y, то значение Л^3) = <

/э^ дает нижнюю оценку максимума <р на X. Шаг 3. Если Л^^ = то пара есть глобально опти-

мальный план поставленной задачи. Конец. Шаг 4. В противном случае положим h^ — Фу^ и = А^. Тогда с одной стороны

(Л<'\гМ) = («W,®yw) = pW > aW = 0W. С другой стороны,

Ух £ X (h{s\ х) = (х,Фi/W) < тах(:с, Фу«) = = А<'>.

Таким образом, полупространство

х е Ж7' | {/i^, х) включает множество X и не содержит точку z^. Шаг 5. Построить новую внешнюю аппроксимацию

найти ее внутреннее представление и перейти к шагу 1, увеличив переменную цикла s на единицу. Эта разновидность алгоритма внешних аппроксимаций сходится к глобально оптимальному план^за конечное число шагов, не превышающее числа вершин У. В §2 и в приложении В-метод сформулирован для произвольных допустимых множеств X и У без упрощающих ограничений.

Внешние аппроксимации с одной стороны воспроизводят множества уровней р^; с другой стороны, они аппроксимируют допустимую область X в районе глобального максимума. Последовательность множеств уровня 1еур<,) представляет собой "сжимающуюся" к X последовательность вложенных множеств.

Вычислительно наиболее сложным в алгоритме внешних аппроксимаций является построение на шаге 5 внутреннего представления множеств

Я«

Главная идея метода состоит в способе генерации отсекающей гиперплоскости на шаге 4. В §3 проводится геометрический анализ алгоритма на простейшем примере, когда матрица Ф единичная, а множества X, У с ограничены и включают окрестность нуля. Выясняется, что отсекающие полупространстваявляются опорными для множеств уровней 1еуд<»> <р. Таким образом, внешние аппроксимации "собираются" из опорных гиперплоскостей множеств уровня.

Построенный алгоритм существенно использует свойства целевой фунции. Как следствие, область его применимости уже, чем в алгоритме Тхиеу, который пригоден для произвольных квазивыпуклых функций. При этом эффективность растет за счет уменьшения количества отсечений.

В определенных обстоятельствах разработанный метод позволяет уменьшить размерность задачи. Так, если матрица Ф вырождена, то множества уровня содержат прямые, их реальная размерность не превосходит ранга матрицы Ф.

В наихудшем случае алгоритм сводится к перебору всех вершин множества У. Это происходит, когда множество уровня подобно множеству X. При этом любая из вершин X доставляет глобальный максимум целевой функции. Как показывает анализ множеств уровня, проведенный в следующей главе, такая ситуация нетипична.

Глава II посвящена исследованию структуры множеств уровня опорной функции произвольного множества X € RN

■Ф(у) =тах(х,у),у

Для многогранника X, содержащего окрестность нуля, и неотрицательных Л, множество уровня равно XX", где X" — поляра X. Известно двойственное взаимно однозначное соответствие между внутренними и внешними представлениями многогранника X и его полярой X"

X = {х € Rn\{ahx) < 1, j б J} = ConvK, i G 1} r = {ie Rn| (uux) < 1 ,»€/} = Conv{oj, j € J} В случае произвольного X ситуация иная, и множество уровня значительно сложнее.

Для анализа общей ситуации в §4 собраны и систематизированы свойства оболочек множества X. Рассматриваются выпуклая, линейная, аффинная, выпуклая коническая, а также выпуклые теневая и антитеневая оболочки. Установлены взаимосвязи между ними, а также уточнены теоремы отделимости в частных случаях.

В §5 исследованы сопряженные оболочки, в том числе сопряженный конус, поляра, ортогональное подпространство и другие. Рассмотрен показательный пример.

Ключевым для главы является §6, где сформулированы две те оремы о строении сопряженных оболочек. Получены выражения для них через внешнее представление множества X. Установлены условия, при которых множество уровня содержит прямые.

На основе построенного формализма в §7 изучаются свойства опорной функции произвольного многогранного множества X. Обобщены результаты о двойственном соответствии внешних и внутренних представлений многогранных множеств и сопряженных к ним. Получены выражения для множества уровня опорной функции. Установлено, что оно представляет собой многогранное множество, а его опорные гиперплоскости порождаются компонентами внутреннего представления X.

Из проведенного исследования можно заключить, что множе-

ство X, заданное в своем внешнем представлении с относительно небольшим количеством опорных гиперплоскостей, и множество уровня 1еуд <р далеки от подобия. Это позволяет надеяться, что в практических ситуациях алгоритм внешних аппроксимаций, описанный в главе I, окажется достаточно эффективным.

Новый метод последовательного построения внутреннего представления многогранного множества Q е описан в главе III. Метод не накладывает ограничений на вид множества il В частности, оно может содержать прямые. Необходимость разработки такого алгоритма вызвана тем, что для задачи билинейного программирования с вырожденной матрицей Ф линейная составляющая многогранного множества существенно ненулевая. Алгоритм вычислительно проще методов Тхиеу-Тама-Бана и Хорста-Тхоаи-де Ври.

Внутреннее представление О, есть прямая сумма Q = Conv V + ConеС + Lin С, где С — базис линейной составляющей множества Q, V — множество вершин пересечения

iîn(Lin£)x = Й, и С — множество неограниченных ребер Q.

Основная идея метода состоит в том, что следует запоминать не только координаты компонент внутреннего представления, но и информацию о соседних компонентах, а также наборах гиперплоскостей, их образующих.

В §8 описывается построение графа 0 множества fi. Каждой невырожденной вершине V^ г € I, множества Q размерности M < |./V| ставится в соответствие узел Vi графа 0. Для него запоминаются координаты х[г, iV] вершины V{, множество p[i, 1 :М] номеров гиперплоскостей, пересечение которых образует вершину Ц, а также набор индексов u[i, 1 :М] вершин, соседних-с Ц.

Наборы р[г, 1 :М] хранятся отсортированными в порядке возрастания. Множества u[i, 1:М] также упорядочены. Этот порядок задается с помощью следующего правила. Возьмем два соседних

узла VI, Уу. В наборе р[г, 1 :М\ имеется ровно один элемент, которого нет в наборе р[у, 1:М]. Обозначим его номер через т. Положим и[г,т] = з- При этом порядок в строке гг[г, 1:М] задается однозначно. На рис. 1 приведен пример построения графа © для призмы, образованной пятью гиперплоскостями. Соответствующие значения х, ри и собраны в табл. 1

5

Рис. 1: Граф многогранника.

V X _Р и

А -1 0 2 1 2 4 В С

В 1 0 2 1 3 4 Е А й

С -3 2 0 1 2 5 F Б А

И 3 2 0 1 3 5 Е С В

Е 3 -2 0 3 4 5 Р 1> В

^ -3 -2 0 2 4 5 Е С А

Табл. 1: Представление узлов для рис. 1.

Так, номер вершины Г в строке и[А, -] равен 1, поскольку ребро А К образовано гиперплоскостями {2,4}, обе эти гиперплоскости присутствуют в строках р[Л, ■] и •], а гиперплоскость

с номером р[А, 1] = 1 отсутствует в строке ■].

Для обработки вырожденных вершин используется еще один прием. Если очередная отсекающая гиперплоскость проходит через некоторую вершину, то эта вершина остается в множестве Î2. В отличие от нее, соответствующий ей узел графа © отсекается, вместо него появляется M новых узлов с одинаковыми строками х. Благодаря этому приему, все узлы графа имеют одинаковую степень, что упрощает реализацию алгоритма.

Для узлов, соответствующих неограниченным ребрам fi, набор р состоят только из M — 1 элементов. Они записываются в конец строки р, а первый ее элемент устанавливается равным нулю. В результате такие узлы оказывается возможным обрабатывать на общих основаниях. Этот прием можно интерпретировать как введение фиктивной "бесконечно удаленной" опорной гиперплоскости.

В §9 описывается механизм изменения графа 0 при добавлении еще одного опорного полупространства во внешнее представление Q. Вследствие однозначности задания строк р и и, оказывается вычислительно несложным определение узлов и дуг преобразованного графа.

Обработка базиса линейной составляющей является предметом обсуждения §10. По мере добавления опорных полупространств размерность Lin С убывает, а размерность M множества О растет.

Благодаря тому, что алгоритм применим для множеств с ненулевой линейной составляющей, отпадает необходимость в решении подзадачи нахождения начальной внешней аппроксимаци Действительно, пространство R,v очевидно содержит X, выпукло, и имеет тривиальное внутреннее представление, что позволяет использовать его в качестве Z

Метод внешних аппроксимаций, изложенный в главе I, а также алгоритм построения внутреннего представления из главы III реализованы в виде программы в среде DELPHI на объектно-ориентированном расширении языка ПАСКАЛЬ. Исходные тексты основных модулей с комментариями представлены в приложении Е.

В главе IV, §11, задача кластерного анализа при фиксированных массах кластеров формулируется как задача выпуклой максимизации вида

рёр тпЫ

e[N,P]xl[P} = fj,[N}, l[N]xe[N,P] = m[Pl e[N, Р] > О[N, Р]. Здесь fi[N] и ш{Р] заданы. Это массы классифицируемых объектов и фиксированные массы кластеров. Ограничения имеют транспортный вид. Матрица R[N, JV] есть матрица Грама координат классифицируемых объектов. Ее размер |JV| обычно очень велик (больше сотни), а ранг не превосходит десяти. В виду неотрицательной определенности матрицы R, эта задача может решаться как соответствующая задача билинейного программирования большой размерности и малого ранга. Разработанная в первой главе модификация алгоритма внешних аппроксимаций эффективно работает в подобных обстоятельствах.

В §12 рассматривается общая задача кластерного анализа, без ограничения на массы кластеров. В этом случае функция Q принимает дробно-квадратичный вид

ш _ v er\p,N}xR[N,N]xe[N,p} 4Ke]~kr 1[АГ] х e[N,p] Удалось показать, что она выпукла на множестве планов задачи. Построен алгоритм внешних аппроксимаций решения поставленной задачи; при этом отсечения строятся в пространстве малой размерности. Указан способ нахождения отсекающей гиперплоскости.

В диссертации имеется пять приложений, В приложения вынесены основные понятия и обозначения, используемые в тексте, обобщение алгоритма внешних аппроксимаций для неограниченных допустимых множеств, два примера, и описание программной реализации с исходными текстами основных модулей.

Текст диссертации имеется в TgX и PostScript форматах на ftp-сервере

ftp://ftp.ids.spb. ru/d/ftpd/AlexeyRBarantsev/thesisru.zip

Основное содержание диссертации опубликовано в работах:

1. А. Р. Баранцев. Кластерный анализ и его связь с билинейным программированием. / В отчете о НИР "Разработка и применение аппроксимационных методов к задачам автоматизированного проектирования АПОИ" (промежуточный отчет). НИИММ, ЛГУ. Руководитель НИР доктор физ. мат. наук В. Н. Малоземов. JL, 1987. Инв. №02880050011 во ВНТИЦентре. С. 88-103.

2. А. Р. Баранцев. Конечный алгоритм решения одной задачи билинейного программирования. / В отчете о НИР "Разработка и применение аппроксимационных методов к задачам автоматизированного проектирования АПОИ" (заключительный отчет). НИЙММ, ЛГУ. Руководитель НИР доктор физ. мат. наук В. Н. Малоземов. Л., 1989. Инв. ^ №02890041972 во ВНТИЦентре. С. 79-100.

3. А. Р. Баранцев. Множества уровня опорной функции. Деп. ВИНИТИ от 15.07.96, № 2354-В96. 28 с.