ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2008, том 48, < 2, с. 237-254
УДК 519.653.4
ЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧ БИЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ1)
© 2008 г. А. В. Орлов
(664033 Иркутск, ул. Лермонтова, 134, ИДСТУ СО РАН) e-mail: anor@icc.ru Поступила в редакцию 29.03.2007 г.
Рассматривается задача билинейного программирования с несвязанными переменными. Вначале представлен специальный метод генерации тестовых билинейных задач. Затем предложены приближенные алгоритмы локального и глобального поиска. Исследуется асимптотическая сходимость алгоритмов, и предлагаются критерии останова. В заключение приводятся и анализируются результаты численного решения случайно сгенерированных билинейных задач. Библ. 20. Табл. 3.
Ключевые слова: невыпуклые задачи оптимизации, билинейное программирование, генерация тестовых задач, локальный поиск, критическая точка, критерии останова, глобальный поиск, вычислительный эксперимент.
1. ВВЕДЕНИЕ
Как известно, в невыпуклых задачах вследствие существования большого количества локальных решений и стационарных (ККТ) точек применение стандартных методов выпуклой оптимизации оказывается неэффективным (см. [1]-[6]). Поэтому разработка новых методов глобального поиска (ГП) и численный поиск глобальных решений в невыпуклых задачах математического программирования является одной из актуальных задач современной оптимизации. При этом наряду с популярными "универсальными" подходами к решению подобных задач, такими как методы ветвей и границ, отсечений, аппроксимаций и т.д. (см. [3]), весьма продуктивными оказываются методики исследования и решения специальных классов невыпуклых задач с учетом их особенностей и свойств (см. [4]-[7]).
В настоящей работе исследуются задачи с билинейной целевой функцией, которая записывается в виде
F(x, y) = < с, x) + < x, Qy) + < d, y), (1.1)
где с, x e IRm, d, y e Rn, Q - матрица размера m x n. Нетрудно видеть, что невыпуклость функции F порождается нетривиальной матрицей Q в скалярном произведении <x, Qy). Можно показать, что функция (1.1) представима в виде разности двух выпуклых, т.е. является d.c.-функцией (см. [4]-[7]). Ясно также, что функция F аффинна по каждой из своих переменных при фиксированной другой. Эта специфика задачи и определила подход, предложенный ниже.
Чаще всего в литературе рассматривается задача максимизации функции F на многогранном множестве. При этом специалисты выделяют два типа задач билинейного программирования: со связанными переменными и с несвязанными переменными (см. [7]). Задачи последнего типа являются объектом исследования в данной работе и имеют следующий вид:
F(x, y) Т max,
(x'y) (BLP)
x e X = {x e Rm|Ax < a}, y e Y = {y e Rn|By < b}.
Здесь A - матрица размера m1 x m, B - матрица размера n1 x n, a e I 1, b e I1.
Ряд задач теории управления, исследования операций и экономики могут быть сформулированы в виде задачи (BLP). Например, одним из исторически первых ее приложений является за-
1)Работа выполнена при финансовой поддержке РФФИ (код проекта 05-01-00110) и гранта президента РФ МК-6580.2006.1.
дача поиска ситуации равновесия по Нэшу в биматричной игре (см. [8]—[10]). Кроме того, билинейной структурой обладают задача отделимости двух множеств в пространстве К" двумя гиперплоскостями (см. [11]), линейная задача дополнительности (см. [12]) и многие другие (см. обзор в [13]).
За более чем четыре десятилетия изучения билинейных задач с несвязанными переменными различные зарубежные авторы предложили ряд методов ее решения, в основном базирующихся на идеях отсечений и методике перебора вершин допустимого множества (см. обзор в [7]). В Советском Союзе для билинейных задач разрабатывались алгоритмы, основанные на методах дискретной оптимизации (см. [14]) и использующие локальный поиск (см. [8]). Среди последних работ по этой тематике следует отметить подход к решению билинейных задач, базирующийся на известном алгоритме внешних аппроксимаций (см. [15]), а также, по-видимому, один из самых эффективных в настоящее время методов, предложенный группой канадских исследователей (см. [16]) и основанный на развитии идеи вогнутых отсечений. Численное тестирование последнего подхода, представленное в [16], показало, что за разумное время удается находить глобальное решение в задаче (БЬР) с плотными матрицами размерности до 60 х 60.
В настоящей работе для поиска глобальных решений в задаче (БЬР) предлагается использовать подход, который основан на теории глобального поиска, разработанной в [4]. Этот подход развивает предложенную ранее методику поиска ситуации равновесия по Нэшу в биматричной игре (см. [9], [10]) и заключается в сведении сложной невыпуклой задачи к последовательности выпуклых (частично линеаризованных). При этом на каждом этапе глобального поиска особое внимание обращается на специфику исследуемой задачи (см. [4], [5]).
Статья организована следующим образом. Прежде всего, в разд. 2 отдельно исследуется вопрос о генерации тестовых задач вида (БЬР) с известными свойствами. Далее, разд. 3 посвящен важнейшей составляющей ГП - локальному поиску. В разд. 4 предлагается алгоритм ГП в билинейных задачах и обсуждаются особенности его реализации. Наконец, в разд. 5 приводятся результаты вычислительного эксперимента по решению случайно сгенерированных задач и дается его анализ.
2. ГЕНЕРАЦИЯ ТЕСТОВЫХ ЗАДАЧ
Для проверки работоспособности и эффективности новых методов решения задач оптимизации почти всегда возникает проблема отыскания или генерации тестовых задач с известными решениями и свойствами. В некоторых случаях можно воспользоваться существующими библиотеками тестовых задач (такими, как, например, Б1МАС8 для задач дискретной оптимизации), в некоторых исследуемая задача имеет решение при любых исходных данных или, скажем, известно значение целевой функции в глобальном решении (например, этим условиям удовлетворяют биматричные игры, см. [9], [10]). В задачах вида (БЬР) нельзя гарантировать существование решения при произвольных исходных данных. Более того, для такого сорта задач не удалось отыскать достаточно репрезентативные тестовые библиотеки. Вместо этого был применен оригинальный метод генерации тестовых задач вида (БЬР) с известными локальными и глобальными решениями, предложенный в [17].
Схема генерации тестовых задач из [17] состоит в следующем. Сначала вводятся так называемые билинейные задачи-ядра небольшой размерности. Затем из них конструируется билинейная задача специального вида. К последней применяется некоторое преобразование, и в результате получается случайная билинейная задача общего вида с известными локальными и глобальными решениями. Опишем эту схему более подробно.
Для к = 1, 2, ..., М определим задачи следующего вида:
рк (Хк, У к) = < С к, Хк) + < Хк, йУк) + < й,, у к) Т тах,
(у,) (БЬРк)
Хк е X, = {Хк е К2| А,Хк < а,}, у, е У, = {У, е К2|В,у, < Ь,},
ЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧ где ск = йк = (1, 1), ак = (2, -2, 2), Ьк = (0, 2Хк - |ь 0),
Ок =
-1 0 0 -1
\ / 0 1 г - Хк \ 1
А = -2 -1 , Вк = Хк- |к 1
/ 2 V -1 / ч |к -2,
Здесь Хк, |к - параметры, в зависимости от значений которых выделяются 4 класса задач-ядер: 1-й класс 1 < Хк < 3, |к = 0; 2-й класс Хк = 3, |к = 0; 3-й класс Хк > 3, |к = 0; 4-й класс Хк = 5/2, |к = 3/2.
Можно показать, что для всех случаев множества Хк и Ук являются ограниченными многогранниками. Значит, эти задачи имеют решение. Кроме того, справедливы следующие утверждения (см. [17]).
Предложение 1. Задачи 1-го класса (БЬРк) имеют четыре локальных решения (хк1}, у(1)) = (0, 2, 2, 0), (х(к), ук2)) = (2, 2, 0, 0), (43), уГ) = (1, 0, 1Дк), (уГ) = (1, 2, 1, 0).
Первые две точки являются глобальными решениями задачи со значением функции Ек(хк,
(') л л ■ 1 о Г) с ^ (3) (3), - 1 , (4) (4), а
Ук ) = 4, г = 1, 2. В то же время хк , ук ) = Хк + 1, Рк(хк , Ук ) = 3.
Предложение 2. В задачах 2-го и 3-го классов имеются те же четыре локальных решения (хк0, ук0 ), г = 1, ..., 4 (других нет). Для задач 2-го класса глобальными решениями являются первые три: (хк, ук), г = 1, 2, 3. В задачах 3-го класса глобальное решение только одно: (хк3, ук3),
= Хк + 1.
Предложение 3. В 4-м классе задач единственным глобальным решением является точка
, (2) (2К _(2) . т, ч , (3) (3),
(хк , ук ), Ек = 4. Кроме того, существует одна точка локального максимума (хк , ук ),
Е(к] = Хк + 1.
Если оценивать сложность задачи каждого класса по соотношению количества локальных и глобальных решений, то задачи 3-го класса являются самыми сложными, а 2-го - самыми простыми. Следующий этап генерации - это процесс объединения некоторого числа М задач-ядер в одну задачу.
Предложение 4 (см. [17]). Если точки (хк, ук) являются глобальными (локальными) решениями задач (БЬРк), к = 1, 2, ..., М, то точка (х1, ..., хМ, у1, ..., уМ) является глобальным (локальным) решением следующей билинейной задачи:
Е(х, у) = (с, х) + (х, Оу) + (й, у) Т тах,
(х, у)
где х е ^2М, у е
Ах < а, Ву < Ь, £2М, ст = [с^, ..., сМ], йт = [йт, ..., йМ], О = diag(Ql,
, ом), а = diag(a1, ..., ам),
Г, Ьт = [Ьт, ..., ЬМ] е
„3М
В = diag(B1, ..., ВМ), ат = [а1, ..., аМ ] е
Будем обозначать эту задачу через БЬР(с, й, О, А, а, В, Ь). Легко видеть, что она представляет собой объединение М задач-ядер (БьРк) (размерность каждой из переменных хк и ук в некоторых равняется 2, а количество ограничений на каждую переменную 3) в одну задачу, так что общее количество переменных в ней равно 4М, а общее количество ограничений 6М. Сформулированное предложение говорит о том, что в билинейной задаче БЬР(с, й, О, А, а, В, Ь) довольно легко вычислить глобальное (локальное) решение. Для этого достаточно объединить известные глобальные (локальные) решения всех задач-ядер в один вектор.
Далее обозначим через N г = 1, ..., 4, количество задач-ядер, принадлежащих классу г N + + И2 + N + И4 = М). Справедливо следующее
Следствие (см. [17]). Задача БЬР(с, й, Q, А, а, В, Ь), сконструированная из М задач-ядер, имеет
Ы1 + Ы2 + Ы3 Ы1 ы2
4 ■ 2 локальных решений, в том числе среди них 2 ■ 3 глобальных.
Таким образом, можно сделать вывод о том, что
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.