автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы решения квадратично-линейных задач двухуровневой оптимизации

4648259

Я2U

МАЛЫШЕВ АНТОН ВАЛЕНТИНОВИЧ

МЕТОДЫ РЕШЕНИЯ КВАДРАТИЧНО-ЛИНЕЙНЫХ ЗАДАЧ ДВУХУРОВНЕВОЙ ОПТИМИЗАЦИИ

05.13.01 - Системный анализ, управление и обработка информации (в технике, экологии и экономике)

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

2 6 МАЙ 2011

Иркутск - 2011

4848259

Работа выполнена в Учреждении Российской академии наук Институте динамики систем и теории управления Сибирского отделения РАН (ИДСТУ СО РАН).

Научный руководитель:

доктор физико-математических наук, профессор

Стрекаловский Александр Сергеевич.

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

профессор

Измаилов Алексей Феридович;

доктор физико-математических наук Лакеев Анатолий Валентинович.

Ведущая организация:

Институт математики и механики УрО РАН (г. Екатеринбург).

Защита состоится 14 июня 2011 г. в 13 ч. 30 мин. на заседании диссертационного совета Д 003.021.01 при Учреждении Российской академии наук Институте динамики систем и теории управления СО РАН по адресу: 664033, Иркутск, ул. Лермонтова, 134.

С диссертацией можно ознакомиться в библиотеке и на официальном сайте ИДСТУ СО РАН www.idstu.irk.ru.

Автореферат разослан 13 мая 2011 г.

Ученый секретарь диссертационного совета д.ф.-м.н. ' А.А. Щеглова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

На протяжении последних десятилетий иерархические задачи оптимизации все больше привлекают внимание специалистов. Такие задачи характеризуются неравноправным положением участников (игроков) и, как правило, возникают при моделировании сложпоорганизованных систем управления (социальных, экономических, эколого-экономических и др.)1- Неизбежность возникновения иерархической структуры в «достаточно сложных» системах подчеркивал акад. H.H. Моисеев в своих работах по теории оптимальных систем2. В частности, задачи двухуровневой оптимизации соответствуют двухуровневой иерархии управления. Уже в таких иерархических задачах присутствует неопределенность понятия решения, связанная с возможной неоднозначностью поведения игрока нижнего уровня. Для снятия этой неопределенности общепринятыми являются два подхода: оптимистический (кооперативный) и гарантированный (пессимистический).

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

Впервые задачи двухуровневой оптимизации, насколько известно, были рассмотрены H.F. von Stackelberg3 при изучении моделей рыночной экономики. В настоящее время исследованию различных классов задач двухуровневой оптимизации посвящено большое количество работ, из которых можно выделить две монографии J.F. Bard4 и S. Dempe5, ставшие уже классическими в этой области. В них рассматриваются вопросы существования и устойчивости решений двухуровневых задач, приводятся различные необходимые и достаточные условия оптимальности, предлагаются подходы к решению таких задач и описаны некоторые практические приложения.

В России иерархические задачи исследовались с точки зрения поиска гарантированных решений, начиная с 70-х годов XX века, группой ученых под

хГорелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М.: Радио и связь, 1982.

2Моисеев H.H. Элементы теории оптимальных систем. М.: Наука, 1975.

3Stackelberg H.F. Marktform und Gleichgewicht. Berlin (Germany): Springer-Verlag, 1934.

4Bard J.F. Practical Bilevel Optimization. Dordrecht (The Netherlands): Kluwer Acad. Pub!., 1998.

bDempe S. Foundations of Bilevel Programming. Dordrecht (The Netherlands): Kluwer Acad. Publ., 2002.

руководством Ю.Б. Гермейера6 (В.В. Федоров, Д.А. Молодцов, И.А. Ватель, Ф.И. Ерешко, А.Ф. Кононенко, В.А. Горелик и др.). Пионерами исследования иерархических задач оптимизации с дискретными переменными в Сибирском отделении РАН были В.Т. Дементьев, B.J1. Береснев, Э.Х. Гимади, A.A. Колоколов и др.

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

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

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

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

Предмет и объект исследования. Объектом исследования являются квадратично-линейные задачи двухуровневой оптимизации (с квадратичной целевой функцией на верхнем уровне и линейной — на нижнем) с линейными ограничениями. Предмет исследования — построение эффективных методов поиска оптимистических и гарантированных решений в таких задачах.

Методы исследования. В диссертации поиск оптимистических решений разбивается на два этапа:

"Термейер Ю.Б. Игры с кепротнвоположными интересами. М.: Наука, 1976.

TTsoukalas А., Wiesemann W., Rustem В. Global Optimization of Pessimistic Bi-Level Problems // Lectures on global optimization / Ed. by P.M. Pardalos, T.F. Coleman. Toronto (Canada), 2009. Vol. 55. P. 215-243.

— сначала осуществляется редукция исходной двухуровневой задачи к эквивалентной ей в определенном смысле серии невыпуклых одноуровневых задач оптимизации;

— затем редуцированные задачи исследуются посредством аппарата выпуклого анализа, современной теории экстремума и методов оптимизации, а также теории глобального поиска, предложенной A.C. Стрекаловским8.

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

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

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

Для квадратично-линейной двухуровневой задачи в оптимистической постановке получены следующие результаты:

а) построен и обоснован специальный метод локального поиска;

б) разработан алгоритм глобального поиска;

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

Кроме того, для квадратично-линейной двухуровневой задачи в гарантированной постановке получены следующие результаты:

а) обосновано ее сведение к серии задач двухуровневой оптимизации специального вида в оптимистической постановке;

б) предложен и обоснован специальный метод локального поиска;

в) построен алгоритм глобального поиска;

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

8Стрекаловский A.C. Элементы невьшуклой оптимизации. Новосибирск: Наука, 2003.

д) разработаны и протестированы программы, реализующие предложенные алгоритмы локального и глобального поиска, которые позволили решить тестовые задачи суммарной размерности до 105.

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

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

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

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

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

Исследования по теме диссертации проводились в рамках проектов по программам СО РАН: «Поиск глобальных решений в невыпуклых задачах исследования операций и оптимального управления » (№ гос. регистрации 01.2.007 08581) с 2007 г. по 2009 г., «Нелокальные методы в теории управления динамическими системами» (№ гос. регистрации 01201001345) в 2010 г., программа «Теория управления динамическими системами и методы их исследования», а также в рамках комплексного интеграционного проекта СО РАН 1.3 «Исследование задач двухуровневого и равновесного программирования» (2006-2008 гг.) и проекта РФФИ № 05-01-00110-а «Невыпуклые задачи оптимизации, исследования операций и оптимального управления» (2006-2007 гг.).

Соответствие диссертации паспорту научной специальности.

В соответствии с паспортом специальности 05.13.01 в диссертации проведено исследование сложных оптимизационных задач, разработаны методы и специальное математическое и программное обеспечение для их решения (пп. 1, 4, 5 области исследований).

Апробация работы. Результаты диссертации докладывались и обсуждались на IX школе-семинаре молодых ученых «Математическое моделирование и информационные технологии» (Иркутск-Ангасолка, 2007), ежегодных конференциях «Ляпуновские чтения и презентация информационных технологий» в ИДСТУ СО РАН (Иркутск, 2007-2009), XIV Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (Иркутск-Северобайкальск, 2008), Всероссийской конференции «Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях» (Иркутск, 2009), IV Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2009), XI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Иркутск-Байкал, 2010), II Международной школе-семинаре «Нелинейный анализ и экстремальные задачи» (Иркутск, 2010), VI Московской международной конференции по исследованию операций (Москва, 2010), XIV Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2011).

Результаты диссертации обсуждались на семинаре кафедры исследования операций факультета ВМК МГУ, на семинаре отдела математического программирования ИММ УрО РАН и неоднократно на семинарах ИДСТУ СО РАН.

Публикации и личный вклад автора. По материалам диссертации опубликовано 12 работ, список которых приведен в конце автореферата. В число указанных работ входят статьи [1-5], опубликованные в журналах, рекомендованных ВАК РФ.

Из совместных публикаций с A.C. Стрекаловским и A.B. Орловым на защиту выносятся только результаты, полученные автором лично. Постановка исследуемых в работе задач осуществлена A.C. Стрекаловским. A.B. Орлову принадлежит идея о применении последовательной минимизации по группам переменных при разработке алгоритмов локального поиска.

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

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 134 наименования. Общий объем диссертации составляет 129 страниц, из которых 115 страниц основного текста, включающего 5 рисунков и 15 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В § 1.1 приведена постановка задачи. Далее осуществляется сведение исследуемой двухуровневой задачи к серии невыпуклых одноуровневых задач оптимизации. Пусть х е JRm, у е R" — векторы стратегий игроков верхнего и нижнего уровня, а их цели состоят в минимизации критериев

F(x, у) = Сх) + (с, х) + -(у, С1У) + (сь у) и G(y) = (d, у) соответственно. Рассмотрим задачу двухуровневой оптимизации

F(x, у) 1 min, (.х,у) е {(х,у) € JRm х IRn \ Ах + By < а, х> 0}, у в ВД й Argmin{G(¿) I г € F(z)},

z

Y(x)ü{y&R"\A1x + Bly<b, у> 0},

где с <Е Шт, cud е R'\ а е IR?, be JR\ A,B,AuBuC,Ci - матрицы соответствующего размера. Матрицы С и С\ являются неотрицательно определенными (С > 0, Ci > 0).

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

му постановка задачи (BV0) называется оптимистической, а ее решение — оптимистическим (или кооперативным).

С помощью замены задачи нижнего уровня (или, другими словами, экстремального ограничения у € К (ж)) ее необходимыми и достаточными условиями оптимальности тина Каруша-Куна-Таккера и с использованием метода штрафов задача (BV0) сводится к ^-параметрическому семейству одноуровневых задач

Ф(х, у, v) = F(x, у) + ßh(x, у, v) 1 min,

(x,y)eZ^{(X)y)\Ax + By<a, A\x + B\y < 6, (V{ß))

x>0, у > 0}, V G V = {и I d + vBi > О, V > 0}, J

где v — вектор множителей Лагранжа для задачи нижнего уровня, h(x, у, v) = (d, у) — {Aix—b, v) — невязка двойственности для задачи нижнего уровня, ц > 0 — штрафной множитель.

Отметим, что целевая функция задачи (V(ß)) при фиксированном значении параметра р > 0 невыпукла и может быть представлена в виде разности двух выпуклых функций, а допустимое множество выпукло. Таким образом, задача {Т{ц)) является задачей d.c. минимизации9. Поиск глобальных решений в задаче (Р(/х)) осуществляется с помощью теории глобального поиска, разработанной A.C. Стрекаловским. В соответствии с этой теорией одним из этапов алгоритма глобального поиска является алгоритм локального поиска, учитывающий специфику задачи, разработке которого посвящен § 1.2.

Заметим, что ограничения в задаче (V(ß)) накладываются на пару (х, у) и на переменную v отдельно, а целевая функция Ф(х, у, v) является выпуклой квадратичной по переменным х, у, линейной по переменной v и билинейной по х и. v (будем называть такую функцию квадратично-билинейной). Эти факты используются в § 1.2 для построения алгоритма локального поиска в задаче (V(i-i)). А именно, в случае квадратично-билинейной целевой функции адаптируется идея последовательной минимизации по группам разделенных переменных10. При фиксированном значении переменной v задача (P(ß)) становится выпуклой квадратичной задачей оптимизации по переменным х, у, а при фиксированном значении (х,у) — задачей линейного программирования (ЛП) по переменной v. Такие выпуклые задачи могут быть успешно решены с использованием классических методов оптимизации11 и известных пакетов прикладных программ.

Стрекаловский A.C. О минимизации разности двух выпуклых функций на допустимом множестве // Журнал вычислительной математики и математической физики. 2003. Т. 43, №3. С. 399-409.

10Стрекшювский A.C., Орлов A.B. Биматричные игры и билинейное программирование. M.: Физмат лит, 2007.

иВасильев Ф.П. Методы оптимизации. М.: Факториал-пресс, 2002.

Итак, пусть задана некоторая начальная точка (x0,yo,vo) € JRm+n+g, которая не является, вообще говоря, допустимой в задаче (V(p)). Тогда осуществляется следующая процедура локального поиска (р, > 0, s = 0,1,...), называемая V-процедурой:

Шаг 0. Положить s 0, v3 := Vq.

Шаг 1. Найти приближенное у-решеиис (a;s+1, ys+1) задачи

Ф(х,у,г;8)1шт! (х, у) € Z. (*.»)

Шаг 2. Найти приближенное —решение v3+l задачи ЛП

${xs+1,ys+l,v) |min, v&V. (CV(xs+l))

v

Шаг 3. Положить s := s + 1 и перейти на шаг 1. #

Отметим, что для начала работы V-процедуры не требуется задание тройки (хо,уо, vq), достаточно лишь задать ее часть vq, поэтому процедура и носит такое название.

В диссертационной работе доказана следующая теорема сходимости У-ироцедуры.

00

Теорема 1. 1. При условии ра> 0, s = 0,1,2,..., Ps < +°°> нисло-

s~0

воя последовательность значений функции Ф(-)> генерируе-

мая V-процедурой, является сходящейся.

2. В случае, если (xs,ys,v3) —+ (x,y,v), предел (x,y,v) удовлетворяет неравенствам

у, и) < Ф(ж, у, v) V(x, у) GZ, (1)

Ф(ж, у, v) < Ф(ж, у, v) Vv G V. (2)

Тройку (x,i},v), удовлетворяющую (с точностью 5 > 0) неравенствам (1) и (2), будем называть (приближенно 6-)критической точкой задачи {V{p)). Нетрудно видеть, что критическая точка (ж, у, v) является частично глобальным решением задачи ("P(/i)) по паре (х,у) при фиксированном значении v и по переменной v при фиксированных значениях х, у. В работе показано, что любое локальное решение задачи (P{ß)) является критической точкой этой задачи.

В работе предложены и обоснованы критерии останова F-процедуры, выполнение которых после шага 2 позволяет получить приближенно критическую точку с заданной точностью. Например, при выполнении условия Ф{х*,узУ) -$(xs+1,ys+\vs) < г

тройка (x3,ys,vs) является приближенным частично глобальным (г + -решением задачи по (х, у) и приближенным частично

глобальным (т + + -решением по переменной v.

\ Л ¿i J

Также в работе предложен и обоснован другой вариант алгоритма локального поиска — .ЛГУ-процедура, в которой вспомогательные выпуклые задачи оптимизации решаются в обратном порядке. Заметим, что получаемые с помощью ЛГУ-процедуры критические точки в некоторых задачах оказываются лучше по значению целевой функции, чем критические точки, найденные с помощью К-процедуры.

В § 1.3 приведены результаты тестирования процедур локального поиска из §1.2. Автором были составлены программы на С++, реализующие разработанные процедуры локального поиска. Для решения вспомогательных задач квадратичного программирования был запрограммирован метод особых точек12, а для решения задач ЛП использовался пакет GLPK13.

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

Результаты тестирования показали, что при значении штрафного параметра /1 = 10 уже с помощью процедур локального поиска удается находить глобальные решения в некоторых сгенерированных задачах. Это значение ц используется в дальнейшем при тестировании алгоритма глобального поиска.

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

В § 1.4 решение задачи (Р(ц)) с использованием теории глобального поиска в задачах d.c. минимизации разбивается на следующие этапы: локальный поиск, доставляющий критическую точку, и процедуры выхода из текущей критической точки, основанные на условиях глобальной оптимальности15. Все этапы общей стратегии глобального поиска в задачах d.c. минимизации конкретизированы для задачи (V(fi)).

В § 1.5 осуществляется тестирование разработанного алгоритма глобаль-

12Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

13URL: http://www.gnu.org/software/glpk/.

uCalamai P., Vicente L. Generating Linear and Linear-Quadratic Bilevel Programming Problems // SIAM Journal on Scientific Computing. 1993. Vol. 14, №4. P. 770-782.

15Стрекаловский A.C. Элементы невьшукдой оптимизации. Новосибирск: Наука, 2003.

ного поиска на сериях случайно сгенерированных задач, включающих в себя задачи из § 1.3. Автором были написаны два варианта программы на языке С++, реализующей алгоритм глобального поиска из § 1.4. В первом случае на этапе локального поиска вспомогательные выпуклые задачи оптимизации решались с помощью подпрограмм, разработанных в § 1.3. Во втором случае использовался известный пакет Xpress16.

В результате вычислительного эксперимента с точностью £ = Ю-4 за приемлемое время удалось найти (глобальные) оптимистические решения во всех тестовых задачах размерности до 50 х 50 (то = 50, п = 50) с использованием первого варианта программы глобального поиска и во всех тестовых задачах размерности до 150 х 150 — с использованием второго варианта. При этом не потребовалось увеличения выбранного в § 1.3 значения параметра штрафа ß = 10.

Кроме того, было проведено численное сравнение алгоритма глобального поиска (АГП) с известным пакетом KNITRO17, ориентированным, в частности, на задачи с комплементарными ограничениями, к которым сводятся двухуровневые задачи вида (BV0). На серии тестовых задач алгоритм глобального поиска продемонстрировал преимущество над KNITRO как по количеству решенных задач (100% задач решено АГП, 61.1% — пакетом KNITRO), так и по времени решения задач (максимальное время решения задачи размерности до 30 х 30 с помощью АГП не превысило 5 минут, а решение одной из задач размерности 30 х 30 с помощью пакета KNITRO заняло более 2 часов).

Результаты главы 1 опубликованы в работах [1-3, б].

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

В § 2.1 приведена постановка пессимистической задачи двухуровневой оптимизации и исследована ее взаимосвязь с задачей поиска оптимистического решения вспомогательной двухуровневой задачи со штрафом на нижнем уровне18.

Пусть х € Мт, у € Rn — стратегии игроков верхнего и нижнего уровней, а их цели заключаются в минимизации функций

F(x,y) = ~{x,Cx) + (c,x)--(y,Ciy) + (ci,y)nG{y) = {d,y) соответственно. Рассмотрим следующую задачу двухуровневой оптимизации:

16URL: http: //wwb.f ico.com/en/ProductB/DMTools/Pages/FICO-Xpress-Optimization-Suite.aspx.

17URL: http://uHw.ziena.com/knltro.htm.

18Молодцов Д.А. О решении одного класса неантагонистических игр // Журнал вычислительной математики и математической физики. 1976. Т. 16, №6. С. 1451-1456.

W(x,e) = sup{F(x,y) I у € У.(а:,е)} J. min, у 1

x € X = {x I Лж < a, x > 0}, Y.(x,e) = {y G Y(x) I G(y) < Inf[G(z) | г € Y(x)] + £} , >

{BVg{e))

где Y(x) = {у | Ахх + Вху < Ь, у > 0}, с е Rm, cud е Rn, а £ ЕР, Ь е R9, а Y,(x, е) — множество приближенных е-решений задачи нижнего уровня, е > 0.

Отметим, что в задаче (BVg(e)), в отличие от задачи (BV0) из главы 1, действия игрока нижнего уровня не согласованы с интересами игрока верхнего уровня. Поэтому целевой функцией здесь является оценка эффективности W(x, е) стратегий игрока верхнего уровня.

Наряду с задачей (ВРд(е)) рассмотрим квадратично-квадратичную двухуровневую задачу в оптимистической постановке, ассоциированную с (BV3(e)):

F(x,y) | min, х € X,

veY„(x,S)ü{yeY(x) I G(y) - vF{x, у) < inf[G(z) - uF(x, z) \ z € Y(x)} + ö\,

z ) )

(BVo{6,v))

где 5 > 0 — точность решения задачи нижнего уровня, v > 0 — множитель, с которым критерий эффективности игрока верхнего уровня исходной задачи штрафует нижний уровень.

Далее при выполнении предположений:

X — ограниченное множество, (3)

3Y:YD Y(x) УхеХ, Y- компакт, (4)

исследуются взаимосвязи задач (ВТд{е)) и (BV0(S. и)).

В частности, в работе доказано, что при фиксированном значении х £ X любое приближенное ¿-решение задачи нижнего уровня в задаче {BV0{5, г/)) является также приближенным решением задачи нижнего уровня в задаче (BVg(e)) с точностью £ = 5 + vF+, где

F+ = max{F(T,y) | х € X, у е Y} - min{F(a;,y) | х е X, у € Y).

Х,у X,у

Получены оценки на значение целевой функции задачи (ВР0(5, v)) в любой ее допустимой точке (х, у) : х € X, у € У»*(х, <5), значениями целевых функций задач (BVg(е)), соответствующих различной точности решения задачи нижнего уровня:

W(x, е) - < F(x, у) < W(x, 6 + t>F+). (5)

■

Из оценок (5) вытекают взаимосвязи значений задач (BV0{ô,v)) и (ВРд(с)) (значений целевых функций задач в их глобальных решениях):

V(SP,(e))V(&P0(Ô, и)) < V(BVg(ö + uF+)),

где y{BVg{e)) — значение задачи (BVg(e)), V(BV0(S, v)) — значение задачи (BV0{5,v)).

Кроме того, доказана сходимость V(BVs(e)) J. V(BVg(0)) при монотонном стремлении е к нулю (е || 0). Отметим, что утверждения данного параграфа обобщают результаты Д.А. Молодцова и В.В. Федорова19 на случай зависимости допустимого множества задачи нижнего уровня от стратегий игрока верхнего уровня (Y = Y{x)) для задач (BVg(e)), (ВТ>0{8, v)).

В § 2.2 рассматривается задача нижнего уровня задачи (BVg{e)). Исследуются свойства ее решений и значения, а именно, доказывается непрерывность отображений, определяющих зависимости множества решений и значения этой задачи от переменных верхнего уровня.

В §2.3 с использованием результатов §2.1 и §2.2 осуществляется сведение задачи (BVg(Q)) в гарантированной постановке к семейству задач (BV0(Ö, „)).

Теорема 2. Пусть выполнены предположения (3), (4) и последовать

телъности {4}, {"*}, {тк} таковы, что 6к Ц 0, vk Ц 0, — J. 0, т> J. 0

Vk

при к —» +00. Пусть далее пара (хк,ук) является приближенным Тк-решением задачи (BV0(ök, Vk)), к = 0,1,2,... Тогда любая предельная точка (Xg,yg) последовательности {(xk, ук)} является решением задачи (BV(0)).

Более точно, это означает, что xg € X, уя £ Y»(xs, 0) и

F(xg,yg) = W(xg,0) = V(BVm

Далее осуществляется сведение задачи (ВР„(6, v)) при фиксированных значениях параметров 6 — 0, v > 0 к семейству задач d.c. минимизации (см.

§1.1) д .

Ф(х,у,и) = F{x,y) +nh{x,y,v) | min,

Ах<а, х>0, Axx + Biy<b, у> О, {Н^))

d - ud + vCxy + vBi > 0, v > 0,

где h(x, у, v) = {d - vci + vCxy,y) + (b- A\X, v), /л > 0 — штрафной множитель. Для нахождения глобального решения задачи (V(n, и)) при фиксированных значениях параметров ц, v используется теория глобального поиска в задачах d.c. минимизации.

"Молодцов Д.А., Федоров В.В. Аппроксимация игр двух лиц с передачей информации // Журнал вычислительной математики и математической физики. 1973. Т. 13, №6. С. 1469-1484.

§ 2.4 посвящен одному из важных этапов глобального поиска — локальному поиску. Несмотря на то, что все переменные в задаче и)) связаны, их удается разбить на группы по свойствам целевой функции Ф(ж, у, v).

Так, если параметры штрафа удовлетворяют условию ц> —, то функция Ф(x,y,v) оказывается выпуклой квадратичной по переменным х, у, линейной по переменной v и билинейной по а: и и, что позволяет осуществить последовательную минимизацию по группам переменных.

Предложены два варианта алгоритма локального поиска, заключающегося в последовательной минимизации целевой функции Ф(аг, у, и) задачи (V(n, г/)) по паре (ж, у) и по переменной v. В отличие от § 1.2 при локальном поиске в задаче (P(ß, v)) допустимые множества вспомогательных выпуклых задач оптимизации изменяются от итерации к итерации в силу связанности переменных. Несмотря на эту трудность, удалось доказать сходимость алгоритма локального поиска к критической точке, являющейся частично глобальным решением по паре (х,у) и по переменной v в отдельности, а также предложить и обосновать критерии останова, позволяющие обнаружить приближенно критическую точку с заданной точностью.

В заключительном § 2.5 представлен алгоритм глобального поиска в задаче (V{ii,v)), основанный на стратегии глобального поиска, все этапы которой конкретизированы для задачи (7?(/х. i/)).

Результаты главы 2 опубликованы в работах [4, 5, 7-12].

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

В § 3.1 построен новый метод генерации тестовых квадратично-линейных двухуровневых задач с известным гарантированным решением, основанный на идеях упомянутой выше методики Р. Calamai, L. Vicente.

Автором были составлены и решены аналитически задачи-ядра вида

W(x) = sup{z2 - 8х +piyi - 2у1\ у £ У,(я)} 1 min, х G [0; 6], '

д 8 * >

У,(ж) = Argmmf-y! | уг + у2 < х, ух < 3, ух >0, у2> 0}, У

где значение параметра p¡ определяет количество локальных решений, не являющихся глобальными.

Далее объединением задач-ядер (/CP¿) при различных значениях параметров Pi строятся двухуровневые задачи произвольной размерности, к которым затем применяется невырожденное линейное преобразование координат с целью избавиться от сепарабельности. При этом в полученной задаче двухуровневой оптимизации оказываются известными все локальные и глобальные гарантированные решения.

Предложение. Двухуровневая задача вида (ВР(0)), в которую входит г\ задач-ядер (К.Р^ при р; = 3, г2 задач-ядер (К,Р{) при Р1 = 4 и гз задач-ядер (1К,Р¿) при р{ = 6, имеет 2Г1+Г2+Гз локальных решений, из которых 2Г2 являются ее глобальными решениями.

В § 3.2 осуществляется тестирование разработанного в § 2.4 алгоритма локального поиска на серии из 20 задач размерности от 2 х 4 до 20 х 40, сгенерированной методом, предложенным в § 3.1. При этом при построении невырожденных матриц, задающих указанное линейное преобразование координат, использовался генератор псевдослучайных чисел компилятора С++ из пакета вСС20. Возникающие в алгоритме локального поиска вспомогательные выпуклые задачи оптимизации решались при помощи упомянутой выше реализации метода особых точек и пакета вЬРК.

На языке С++ были написаны программы, реализующие построенные в § 2.4 процедуры локального поиска. На первом этапе тестирования осуществлялся выбор начальных значений параметров штрафа ц, V, которые в дальнейшем используются при глобальном поиске. В ходе вычислительного эксперемента были найдены значения параметров ц, и, при которых уже локальным поиском удалось с точностью е = Ю-4 найти глобальные решения в некоторых сгенерированных задачах.

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

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

Наконец, в § 3.3 на серии задач из § 3.2 был протестирован алгоритм глобального поиска, предложенный в §2.5. При этом для локального поиска применялись подпрограммы, разработанные в § 3.2, а для решения частично линеаризованных задач, возникающих в алгоритме глобального поиска, была использована программная реализация метода особых точек, упомянутая выше.

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

20иш,: http://gcc.gnu.org/.

успешно протестирован на сериях тестовых задач размерности до 35 х 70.

В результате тестирования алгоритма глобального поиска за приемлемое время удалось найти гарантированное решение во всех сгенерированных задачах размерности до 105 (по совокупности переменных верхнего и нижнего уровня). При этом изменения выбранных в § 3.2 значений параметров штрафа /1, v не потребовалось.

Результаты главы 3 опубликованы в работах [5,10-12].

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Стрекаловский А.С., Орлов А.В., Малышев А.В. Локальный поиск в квадратично-линейной задаче двухуровневого программирования // Сибирский журнал вычислительной математики. 2010. Т. 13, № 1. С. 75-88.

2. Стрекаловский А.С., Орлов А.В., Малышев А.В. Численное решение одного класса задач двухуровневого программирования // Сибирский журнал вычислительной математики. 2010. Т. 13, № 2. С. 201-212.

3. Strekalovsky A.S., Orlov A.V., Malyshev A.V. On computational search for optimistic solutions in bilevel problems // Journal of Global Optimization. 2010. Vol. 48, № 1. P. 159-172.

4.'Малышев А.В., Стрекаловский А.С. О взаимосвязи некоторых задач двухуровневой и нелинейной оптимизации // Известия вузов. Математика. 2011. № 4. С. 99-103.

5. Малышев А.В., Стрекаловский А.С. Глобальный поиск гарантированных решений в квадратично-линейных задачах двухуровневой оптимизации // Известия ИГУ. Математика. 2011. Т. 4, № 1. С. 73-82.

6. Малышев А.В., Орлов А.В. Поиск оптимистических решений в квадратично-линейных двухуровневых задачах // Материалы IX школы-семинара молодых ученых «Математическое моделирование и информационные технологии» (Иркутск — Ангасолка, 22-27 октября 2007 г.). Иркутск, 2007. С. 107-110.

7. Стрекаловский А.С., Малышев А.В. О поиске гарантированного решения задачи двухуровневого программирования // Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения» (Иркутск, Байкал, 2-8 июля 2008 г.). Иркутск, 2008. Т. 1. С. 602-608.

8. Стрекаловский А.С., Малышев А.В. О взаимосвязи гарантированного и оптимистического решений задачи двухуровневого программирования // Алгоритмический анализ неустойчивых задач: тезисы докладов Международной конференции, посвященной 100-летию со дня рождения В.К. Иванова (Екатеринбург, 1-6 сентября 2008 г.). Екатеринбург, 2008. С. 306-307.

9. Малышев А.В. О поиске гарантированного решения в квадратично-линейных двухуровневых задачах // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 29 июня - 4 июля 2009 г.). Омск, 2009. С. 184.

10. Malyshev A.V., Strekalovsky A.S. Global search for pessimistic solution in bilevel problems // Proceedings of the Toulouse global optimization workshop 2010. Toulouse (France), 2010. P. 77-80.

11. Малышев А.В. Поиск гарантированного решения одного класса задач двухуровневого программирования // Труды VI Московской международной конференции по исследованию операций (ORM2010: Москва, 19-23 октября 2010 г.). М.: МАКС Пресс, 2010. С. 239-240.

12. Малышев А.В. Численный поиск гарантированного решения в одной задаче двухуровневой оптимизации // Тезисы докладов XIV Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 28 февраля - 4 марта 2011 г.). Екатеринбург: УрО РАН, 2011. С. 47-48.

Редакционно-издательский отдел Учреждения Российской академии наук Института динамики систем и теории управления СО РАН 664033, Иркутск, ул. Лермонтова, д. 134

Подписано к печати 3.05.2011 Формат бумаги 60x84 1/16, объем 1,2 п.л. Заказ 9. Тираж 130 экз.

Отпечатано в ИДСТУ СО РАН

Введение

1 Глобальный поиск оптимистических решений в двухуровневых задачах

1.1 Постановка задачи и ее редукция.

1.2 Локальный поиск.

1.3 Тестирование процедур локального поиска.

1.4 Алгоритм глобального поиска.

1.5 Тестирование алгоритма глобального поиска.

1.6 Заключительные замечания.

2 Теоретические основы поиска гарантированных решений

2.1 Постановка задачи и ее взаимосвязь с задачей поиска оптимистического решения специальной двухуровневой задачи.

2.2 Свойства задачи нижнего уровня.

2.3 Редукция к задачам d.c. оптимизации.

2.4 Процедуры локального поиска.

2.5 Алгоритм глобального поиска.

2.6 Заключительные замечания.

3 Численный поиск гарантированных решений

3.1 Генерация тестовых задач

3.2 Тестирование локального поиска.

3.3 Численный поиск гарантированных решений в сгенерированных задачах

3.4 Заключительные замечания.

На протяжении последних десятилетий внимание специалистов все больше привлекают иерархические задачи с конфликтами, возникающие в различных приложениях (в экономике, экологии, энергетике, технике и других областях). Эти задачи характеризуются неравноправным положением участников (игроков) и называются играми с иерархической структурой [7,8,11,60,74].

Игры с иерархической структурой, как правило, возникают при моделировании слож-ноорганизованных систем управления (социальных, экономических, эколого-экономнческих и др.) [7,8,11,60,74,118]. Неизбежность возникновения иерархической структуры в "достаточно сложных" системах подчеркивал акад. H.H. Моисеев в своих работах по теории оптимальных систем [33]. Иерархия в таких системах возникает по причине высокой трудоемкости своевременного сбора и переработки большого объема информации о контролируемых процессах единым управляющим центром, что приводит к принятию решений по неполной или устаревшей информации (т.е. в условиях неопределенности). Обработка информации и принятие решений отдельными элементами системы (подсистемами) позволяет обычно уменьшить влияние такого рода неопределенностей. Однако введение частичной децентрализации управления приводит к появлению другого вида неопределенности, связанной с самостоятельными действиями подсистем, определяемыми их интересами [11].

Первые исследования многоуровневых иерархических систем показали их непреодолимую на данном этапе сложность [8,11]. Поэтому естественным был переход к рассмотрению наиболее простых объектов с иерархией — игр двух лиц с фиксированным порядком ходов и передачей информации о первом ходе. К таким играм сводится исследование многих двухуровневых иерархических систем управления [7,8,11,60,74].

Впервые иерархические игры двух лиц были рассмотрены Генрихом фон Штакельбергом в монографии [118] при исследовании практических моделей рыночной экономики. В играх такого рода имеются два игрока, осуществляющие выбор своих стратегий х и у из множеств X и У. При этом считается, что интересы игроков полностью описываются их желанием минимизировать соответствующие критерии эффективности F(x,y) и G(x,y), которые, вообще говоря, могут быть различными. Игрок 1 (называемый игроком верхнего уровня или лидером) обладает определенным приоритетом, выражающимся в праве сделать свой ход первым. Ход игрока 1 состоит в выборе стратегии х € X, которая может быть, вообще говоря, функцией от информации об ожидающемся поведении игрока 2, и передаче сообщения о выбранной стратегии игроку 2 (игроку нижнего уровня). Поскольку после сообщения игроком 1 своей стратегии выигрыш игрока 2 зависит только от его выбора, естественно считать, что поведение игрока 2 определяется стремлением минимизировать функцию G(x, •). Однако, это не устраняет полностью неопределенность для игрока 1, даже если он знает функцию G(x, •), поскольку ее минимум может быть неединственным (если эта функция не является, скажем, строго выпуклой) [11,74].

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

F{x, у) |"min", хеХ,

S) у е Argmin{C?(:r, z) \ z Е Y}, Z которая называется задачей или игрой Штакелъберга [74].

Так называемые двухуровневые задачи оптимизации [60,74] обобщают задачу Шта-кельберга в том смысле, что множество допустимых стратегий игрока нижнего уровня (игрока 2) считается зависящим от стратегии игрока верхнего уровня (игрока 1) [74], и формулируются следующим образом:

F(x,y) j."min", zeX,

BP) у е Argmin{G(x, z) | z e z

Подчеркнем, что кавычки в постановках задач (S) и [BP) отражают отмеченную выше неопределенность выбора конкретной стратегии у игроком нижнего уровня из множества своих оптимальных стратегий. Для снятия этой неопределенности известны два подхода — оптимистический (кооперативный) и гарантированный (пессимистический), которые приводят к соответствующим определениям решений в задачах двухуровневой оптимизации [7,8,11,60,74].

В первом случае считается, что интересы игрока верхнего уровня могут быть согласованы с действиями игрока нижнего уровня, и, следовательно, игрок 2 из множества своих оптимальных стратегий выбирает стратегию наиболее благоприятствующую игроку 1. В этом случае задача (BV) принимает следующий вид:

F(x, у) J. min, х е X, х'у (BVo) у е Argmin{G(a;, z) \ z € Y(z)}. z

Решение задачи (BV0) называется оптимистическим решением задачи (BV) [60,74]. Отметим, что в случае оптимистического решения зачастую рассматривают более общую задачу, где ограничение на выбор допустимой стратегии игроком верхнего уровня х 6 X заменяется более общим ограничением на совокупность стратегий игроков (я, у) G D [74].

Во втором случае предполагается, что игрок 2 предпочитает действовать независимо, и игрок 1 вынужден это принять во внимание, исходя из обобщенного принципа гарантированного результата [8,11,74]. Здесь считается, что игрок нижнего уровня может действовать наихудшим по отношению к игроку верхнего уровня образом, вследствие чего возникает задача:

W(x) = sup{.F(:£, у) | у <5 У*(я:)} I min, х е X,

У*(х) = Argmin{C?(®, z) | г € У (ж)}, Z где W(x) — оценка эффективности стратегий игрока верхнего уровня [8].

Решение задачи (BVg) называется гарантированным или пессимистическим решением задачи (BV) [7,8,11,60,74]. Также будем далее называть задачу (BVa) двухуровневой задачей в оптимистической (кооперативной) постановке, а задачу {BVg) — двухуровневой задачей в гарантированной (пессимистической, некооперативной) постановке.

Сразу же отметим, что двухуровневая задача в гарантированной постановке является более сложной по сравнению с задачей в оптимистической постановке [79]. Здесь целевая функция верхнего уровня (оценка эффективности лидера) включает в себя операцию взятия точной верхней грани. Поэтому целевая функция лидера оказывается, вообще говоря, негладкой даже в том случае, когда функции F(-), G(-) — гладкие.

Кроме того, как будет показано ниже, даже двухуровневая задача в оптимистической постановке обладает структурной невыпуклостыо, причем даже в случае выпуклости функций .Р(-), £?(•) и множеств допустимых стратегий игроков.

Близким к двухуровневым задачам классом игровых задач являются задачи равновесного программирования [1,98,113,117], отличающиеся тем, что игроки в них являются равноправными. Кроме того, к двухуровневым задачам тесно примыкают так называемые задачи с равновесными ограничениями, задачи нижнего уровня в которых могут иметь вид вариационного неравенства, некоторой задачи равновесного программирования или дополнительности [19,101,104,112,113].

К настоящему времени опубликовано огромное количество работ, в которых рассматриваются задачи двухуровневой оптимизации (см., например, обзоры [67,72]). Приведем ссылки лишь на работы, наиболее близкие к тематике диссертации. Прежде всего необходимо отметить две монографии Дж Ф. Барда [60] и С. Демпе [74], ставшие уже классическими в этой области. В них рассматриваются вопросы существования и устойчивости решений различных классов двухуровневых задач, приводятся различные необходимые и достаточные условия оптимальности, предлагаются подходы к решению таких задач и описаны некоторые их практические приложения.

Большое количество публикаций посвящено теоретическому исследованию непрерывных двухуровневых задач. В них рассматриваются вопросы существования решения и алгоритмической трудности двухуровневой задачи [52,61], устойчивости решения [95,99], получения условий оптимальности [73,76-79,95,124,131].

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

1) Методы, в которых двухуровневая задача сводится к невыпуклой (одноуровневой) задаче оптимизации [13,53,55,81,82,90,92,100,109,127,128]. Обычно это сведение осуществляется при помощи замены задачи нижнего уровня ее необходимыми и достаточными условиями типа Каруша-Куна-Таккера [74]. К полученной в результате такого сведения невыпуклой задаче затем применяется один из алгоритмов глобальной оптимизации [43,93,132].

2) Методы штрафов [70,91,102,115,130] являются родственными методам из пункта 1. Здесь, как и в методах из п. 1, осуществляется редукция задачи к некоторой одноуровневой. Решение последней осуществляется с применением метода штрафов [6]. Чаще всего в качестве штрафной функции выступает сумма целевой функции верхнего уровня и невязки двойственности для задачи нижнего уровня со штрафным множителем [74].

3) Методы, в которых двухуровневая задача сводится к одноуровневой задаче оптимизации, часть переменных которой являются целочисленными [58,66].

4) Методы решения двухуровневых задач с линейными ограничениями на обоих уровнях перебором вершин многогранника, определяющего допустимую область задачи [65].

5) Методы допустимых направлений для задачи верхнего уровня с информацией о градиенте, получаемой из задачи нижнего уровня [84,97,116,125]. Такие методы обеспечивают лишь получение стационарной точки в задаче, так что их можно считать алгоритмами локального поиска.

6) Методы доверительной области [54,68,71,75]. Здесь рассматриваемая двухуровневая задача заменяется более простой модельной задачей и производится ее решение в некоторой заданной (доверительной) области. Затем полученное решение оценивается^ с точки зрения исходной задачи, на основании чего принимается решение об изменении текущей доверительной области.

7) Методы, основанные на редукции двухуровневой задачи к задаче векторной оптимизации [17,86,123].

8) Методы "параметрического программирования" [83], в которых допустимое множество задачи верхнего уровня представляется в явном виде, путем нахождения явного вида множеств оптимальных стратегий игрока нижнего уровня для каждой из допустимых стратегий игрока верхнего уровня.

9) Метод ветвей и границ [59,94,108,115,122], генетические алгоритмы [133], поиск с запретами [114] и другие алгоритмы глобальной оптимизации, пришедшие из дискретной оптимизации, применяемые к двухуровневым задачам напрямую (в отличие от методов из п.п. 1-3).

С точки зрения численного поиска оптимистического решения сравнительно эффективными себя показывают, как правило, только специальные численные методы для линейно-линейных двухуровневых задач, в которых критерии эффективности игроков и функции, задающие ограничения, являются линейными функциями. Так, в [58,115] приведены результаты решения таких задач с суммарным числом переменных до 200.

При численном поиске оптимистических решений в нелинейных двухуровневых задачах чаще всего авторы ограничиваются рассмотрением иллюстративных примеров^ размерности до 10 (см. [66, 83, 84, 90,100,108,109¡ 114,116,122,127,128,133]) и только в [59; 68,81,82,88] представлены результаты решения нелинейных двухуровневых задач размерности до 50, а в [94] — результаты решения-таких задач размерности до 100 с разреженными матрицами. В работе [92] представлены результаты численного решения-нелинейных двухуровневых задач размерности до 220, в которых целью игрока нижнего уровня является только лишь отыскание точки Каруша-Куна-Таккера в невыпуклой квадратичной задаче оптимизации. Входящая в решение такой двухуровневой задачи стратегия игрока нижнего уровня, вообще говоря, не является решением задачи нижнего уровня в силу невыпуклости этой задачи. Следовательно, отыскиваемое в [92] решение двухуровневой задачи не будет даже оптимистическим решением в смысле данного выше определения.

Что касается подходов к поиску гарантированного решения в двухуровневых зада- • чах, этот вопрос рассматривался группой исследователей под руководством Ю.Б. Гер-мейера [8,11,34,35]. В работах [34,35] было получено сведение неантагонистической игры двух лиц с передачей информации (задачи Штакельберга) в гарантированной постановке к семейству вспомогательных задач Штакельберга в оптимистической постановке. К сожалению, в 90-е годы XX в. исследование таких задач в этой группе было приостановлено по объективным причинам. В более поздней работе [103] результаты из [34] были несколько обобщены. А именно, были ослаблены предположения на функции, входящие в постановку редуцируемой двухуровневой задачи.

Единственным известным нам (и авторам публикации [121]) алгоритмом численного решения непрерывной задачи двухуровневой оптимизации в гарантированной постановке является алгоритм поиска гарантированного решения нелинейной задачи Штакельберга, предложенный и протестированный на задачах размерности до 4 в [121]. Этот алгоритм основан на сведении рассматриваемой двухуровневой задачи к так называемой задаче полубесконечного программирования.

Также в литературе имеются публикации, посвященные решению отдельных классов дискретных двухуровневых задач, часть переменных в которых может принимать лишь значения из конечного набора [3,9,10,15,51,80,88,96,126]. Некоторые из таких задач могут быть сведены к непрерывным двухуровневым задачам [88].

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

Основная цель диссертационного исследования состоит в разработке методов поиска оптимистических и гарантированных решений в (непрерывных) квадратично-линейных задачах двухуровневой оптимизации, эффективных с вычислительной точки зрения.

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

1) Определение размеров квот и дотаций производителям сельхозпродукции [69,111].

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

Пусть т — количество видов квот и дотаций, п — количество видов продукции, тогда стратегия игрока верхнего уровня определяется вектором х — (хх, .,хт), где хг — размер финансирования квоты или дотации вида г = 1 ,.,гтг, в свою очередь стратегия игрока нижнего уровня определяется вектором у — (уъ., уп), где у3 — объем производства продукции вида ] = 1, .,п. Известны ограничения х^ на максимальный размер финансирования квоты или дотации вида г, а также общие ограничения £+1ГП2 на максимальный суммарный размер финансирования квот или дотаций видов 7пг, .,тп2-Критерием эффективности игрока верхнего уровня является свертка т+1 критериев с весовыми коэффициентами wt > 0, г = 1,., га+1. При этом каждый из первых т критериев отражает стремление к достижению рекомендуемого уровня хг квоты или дотации вида г (например, по экологическим соображениям может быть определен желаемый размер посевных площадей), а максимизация (т + 1)-го критерия (Ь, х) + (с, у) означает стремление увеличить трудовую занятость населения, где Cj — размер заработной платы, соответствующий количеству рабочих мест, требуемых для производства единицы продукции вида j, bi — размер заработной платы, соответствует количеству рабочих мест, дополнительно возникающих в случае увеличения дотации вида г (такие рабочие места возникают, например, при дотациях на постройку новых ирригационных систем, которые позволяют увеличить посевную площадь; в том случае, когда дополнительных рабочих мест не возникает, Ьг — 0).

Целью игрока нижнего уровня является максимизация прибыли (d,y), где dj — стоимость единицы вида продукции j = 1 ,.,п, с учетом балансовых ограничений Ву < а + Ах, где — количество ресурса вида к — 1 ,.,q, требуемого для производства единицы продукции вида j, а к — запас ресурса вида к у производителя, Aki — количество ресурса вида к, соответствующее единице финансирования квоты или дотации вида г = 1, .,т. Кроме того, на нижнем уровне учитываются ограничения на максимальный спрос на продукцию вида j и ограничения у+1П2 на максимальный общий спрос на продукцию видов Щ, .,П2.

Таким образом, возникает следующая двухуровневая задача. m ги2(а;г - Xif) - wm+i((b, х) + (с, у)) | " min", i=i ж

ТП2

0 < хг < xf, i — 1,., т, Xi<x+ini2, (тит2)еМ, i=mi у е Argminf—(d, у) | Ву < а + Ах, у

Т12 о <у3< У+, j = 1,П, 2 Уз ^ VniП2> ("ь п2) € Л/"},

3=п 1 где х е Мт, у £ JRn, М = {(mi,m2) | 0 < тп^ < т2 < т, т\, тп2 — целые}, Л/" = {(ni,n2) | 0 < щ < п2 < п, щ,п2 — целые}.

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

2) Задача оптимального выбора тарифов телекоммуникационным оператором [110].

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

Предположим, что определен граф G = (V, U, А), где V — множество вершин графа, соответствующих узлам телекоммуникационной сети, U — множество ребер, соответствующих доступным каналам связи, а отношение инцидентности определяется матрицей А. Пусть |V| = га, \U\ = п. Множество U разобьем на два непересекающихся подмножества: U = U U2, где ребра, входящие в Ui, соответствуют каналам связи, которые обслуживает игрок верхнего уровня, а ребра, входящие в U2, соответствуют каналам, принадлежащим конкурирующим компаниям. Пусть \U\\ — rii, |i/2| = гг2.

Каждому ребру графа G, входящему в U\, сопоставим два числа: с] — некоторая фиксированная цена передачи данных по соответствующей линии, и ж* — тариф, опре-. деляемый игроком верхнего уровня. Стоимость передачи данных по каналу связи, соответствующему произвольному ребру из СД, равна Xi + с\, г — 1,2, .,п\. Каждому ребру из U2 сопоставлена некоторая известная стоимость передачи данных по соответствующей линии с?, г = 1,2, .,П2. Таким образом, х — (ж1,ж2, .,хП1) — вектор стратегии игрока верхнего уровня. Определены допустимые границы изменения тарифов:

1 д х € X = ]\[хг,хг] = {х е JRni I Xi € fe,^], ъ — 1,2,.,ni}. 1

Стратегия игрока нижнего уровня определяется вектором у — (ук) = ((ук,У2)), к = 1,2 каждый ук соответствует объему трафика, который необходимо передать из узла sk в узел гк. При этом ук = (у^,ук2,y\ni) — поток трафика по каналам связи, соответствующим ребрам из Ux, а у% = {укх,ук2,■ УъП2) — поток трафика по каналам, соответствующим ребрам из £У2. Накладываются ограничения на пропускную способность каждой линии: о <ук3<у), j — 1)2, .,п, и ограничение сохранения потока:

Аук = Skdk, где 6к — запрашиваемый объем трафика, dk G Rm — вектор, у которого только компоненты с индексами зк и гк отличны от нуля, причем с1як — 1, йгк = — 1.

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

К 7Ц " {хч У\) Т " шах", хеПМ, к=1 х г=1 у е Агётт{ £ «с1 + х, у£) + (с2, у%)) | Аук = 5к<1к, 0 <ук < у), "

У к= 1

У = 1,2,.,п, А; = 1,2,., А"}.

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

3) Проектирование сети шоссейных дорог [60,62].

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

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

Обозначим множество всех шоссейных дорог в транспортной сети через 7г, множество городов — через С.

Каждая компонента хг > 0 стратегии игрока верхнего уровня (проектировщика дорожной сети) играет роль планируемого увеличения пропускной способности г-той дороги, входящей в дорожную сеть.

Стратегии игрока нижнего уровня (агрегированного "пользователя" дорог) включают в себя транспортный поток > 0, I £ й, на каждой из дорог, транспортные потоки гц > 0, г 6 Л, ] Е С, по дороге г в город ] (с выполнением условия согласования ^ = у, \/г € Я), а также вспомогательные переменные щ, г^, -шц, г Е Я, ] 6 С, зес

I Е {1,2,.,^}.

Значения переменных > 0 и ^ > 0 аппроксимируют значения функций стоимости перевозки по дороге для проектировщика и "пользователя" дорог: г > - 9цХ{ + Эи, I = 1, .,

Щ > ГиУг - дих1 + / = где /¿, Зх — количество сегментов в кусочно-линейной аппроксимации соответствующей функции стоимости перевозки по дороге г ё й, Гц,дц,вц и Гц, диви — коэффициенты уравнений прямых, составляющих эти аппроксимации.

Дополнительная минимизация функции ^ и)ц при ограничениях

1=1 шц >х{- ян, и)ц >0, / = 1,., Ки на нижнем уровне обеспечивает то, что значение выражения ацХ{ + Ьц+ ^ {(11+1,1 - Щг)Щ{ 1=1 совпадает со значением кусочно-линейной аппроксимации некоторой функции затрат на расширение дороги г £ Я ж;) = ацХ{ + Ьц, Хг Е [<?г-1,г> Цц], I Е {1,2 ,.,Кг}.

Фиксированные объемы перевозок е^ из города к Е С в город з Е С, которые осуществляет игрок нижнего уровня, накладывают ограничения на транспортные потоки геАк геВк где множества /Ц и Вк. к Е С, содержат начальные и конечные пункты маршрутов соответственно.

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

В итоге, возникает следующая двухуровневая задача оптимизации:

Кг~1

У" jlii +т(аъХг +Ьи+ (а1+1,г - О/гМг)] | " mjn") гея г=1 г/, z, и, v, w) е Argmin { ^ (■vt + еиг + У^ wh) у,*,*,«,«/ ^ v /=1 J щ > гнУг - ghXi + shi i = l,.,/i, - -I- Su, I = 1, ., Jl5

Wh>Xi-Qh, l = l,.,Ki, Z/г! Ху ztj = jec ieAk ießk k,j e C, ie R, x>0,y>0, z > 0, и > 0, v > 0, w > oj, где r > 0 — множитель, позволяющий конвертировать стоимость затрат на расширение дорог в единицы, в которых измеряется стоимость перевозки, е > 0 — малый вещественный параметр, который необходимо выбирать так, чтобы компоненты у, г, v, w решения задачи нижнего уровня совпадали с таковыми при е = 0 при любом выборе стратегии х игроком верхнего уровня.

Отметим, что полученная задача является линейно-линейной двухуровневой задачей, причем ограничений в задаче верхнего уровня нет (кроме экстремального), а допустимое множество задачи нижнего уровня зависит от выбора стратегии игроком верхнего уровня. • Ф

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

Предложенный в диссертации подход к разработке методов решения квадратично-линейных двухуровневых задач состоит из двух этапов:

1) Редукция двухуровневой задачи к семейству одноуровневых задач оптимизации;

2) Разработка алгоритмов локального и глобального поиска в редуцированных задачах, основаных на теории глобального поиска, предложенной A.C. Стрекаловским [43].

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

Достаточно сложно привести полную классификацию задач невыпуклой (или глобальной) оптимизации. В частности, в литературе [43,93] выделяют следующие важные классы невыпуклых задач, содержащие d.c. функции (такие функции, которые могут быть представлены в виде разности двух выпуклых функций):

1) задача d.c. минимизации: д(х) - f(x) | min, xeS, {VC) X где функции /(•), д(-) и множество S выпуклы;

2) задача оптимизации с одним d.c. ограничением:

СVCC) h{x) | min, х е S, X д(х) - f{x) < (=) о, где /(•), д{-), h(-), S — выпуклы.

В диссертационной работе осуществляется редукция квадратично-линейной задачи в оптимистической постановке к задаче класса (VCC), которая затем сводится к серии задач класса {VC), для решения которых используется теория глобального поиска в задачах d.c. минимизации [43]. Основными этапами алгоритов глобального поиска, основанных на данной теории, являются:

1) Алгоритм локального поиска, учитывающий специфику невыпуклости конкретной задачи;

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

Алгоритмы, основанные на теории глобального поиска, неоднократно демонстрировали свою вычислительную эффективность при решении многих задач исследования операций (см., например, [5,36,38,43,47,119]). Необходимо отметить, что внутри алгоритмов локального поиска, составляющих один из основных этапов стратегии глобального поиска, работают классические методы выпуклой оптимизации [2,4,6,14,39].

Для решения квадратично-линейных задач в гарантированной постановке в работе прежде всего осуществляется их редукция к семейству задач поиска оптимистического решения вспомогательных квадратично-квадратичных двухуровневых задач (в которых критерий эффективности игрока нижнего уровня:— тоже квадратичная.функция). Тем самым осуществляется развитие подхода к поиску гарантированных решений в; задачах' Штакельберга, предложенного Д.А. Молодцовым и В.В. Федоровым [34, 35,103]; Дальнейшее, сведение к задачам die. минимизации осуществляется на базе описанного выше подхода к. поиску оптимистических решений квадратично-линейных двухуровне- .' вых задачах. При разработке- методов локального и глобального поиска в полученных при таком, сведении; задачах, как и ранее, /используется теория глобального; поиска- в . задачах d.c. минимизации. , •

Далее опишем структуру диссертации. Диссертационная;работа состоит из введения, трех глав, заключения исписка литературы из 134 наименований.

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

1) Предложены и обоснованы методы локального и глобального поисков оптимистических решений в квадратично-линейных двухуровневых задачах. Численное тестирование показало их эффективность на широком спектре случайно сгенерированных тестовых задач размерности до 300.

2) Теоретически обоснованы взаимосвязи задачи поиска гарантированного решения квадратично-линейной двухуровневой задачи и квадратично-квадратичной двухуровневой задачи специального вида в оптимистической постановке. Обоснована редукция поиска гарантированного решения квадратично-линейной двухуровневой задачи к решению семейства таких вспомогательных задач в оптимистической постановке.

3) Для задачи поиска гарантированных решений в квадратично-линейных двухуровневых задачах предложены и обоснованы методы локального и глобального поисков. Разработан новый метод генерации квадратично-линейных двухуровневых задач различной сложности и размерности с известными гарантированными решениями. Численное тестирование разработанных методов локального и глобального поисков на сериях сгенерированных задач размерности до 105 продемонстрировало их эффективность.

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

Заключение

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

1. Антипин A.C. Экстрапроксимальный метод решения равновесных и игровых задач // Журн. вычисл. матем. и матем. физики. 2005. Т. 45, №11, 12. С. 1969-1990, 2102-2111.

2. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. М.: Мир, 1982.

3. Береснев B.JL, Мельников A.A. Приближённые алгоритмы для задачи конкурентного размещения предприятий // Дискретный анализ и исследование операций. 2010. Т. 17, №6. С. 3-19.

4. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.

5. Васильев И.Л., Климентова К.Б., Орлов A.B. Параллельный глобальный поиск равновесных ситуаций в биматричных играх // Вычислительные методы и программирование. Издательство Московского университета. 2007. Т. 8, №2. С. 84-94.

6. Васильев Ф.П. Методы оптимизации. М.: Факториал-пресс, 2002.

7. Васин A.A., Морозов В.В. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005.

8. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976.

9. Гимади Э.Х., Гончаров E.H. Двухуровневая задача выбора системы машин и узлов с нелинейной производственной функцией // Сибирский журнал индустриальной математики. 2006. Т. 9, №2. С. 44-54.

10. Горбачевская JI.E., Дементьев В.Т., Шамардин Ю.В. Двухуровневая задача стандартизации с условием единственности оптимального потребительского выбора // Дискретный анализ и исследование операций, серия 2. 1999. Т. 6, №2. С. 3-11.

11. Горелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М.: Радио и связь, 1982.

12. Груздева Т.В. Решение задачи о клике сведением к задаче с d.c. ограничением // Дискретн. анализ и исслед. опер. 2008. Т. 15, №6. С. 20-33.

13. Груздева Т.В., Петрова Е.Г. Численное решение линейной двухуровневой задачи // Журн. вычисл. матем. и матем. физ. 2010. Т. 50, № 10. С. 1715-1726.

14. Даугавет В.А. Численные методы квадратичного программирования: учеб. пособие. СПб.: Изд-во С.-Петерб. ун-та, 2004.

15. Дементьев В.Т., Шамардин Ю.В. Двухуровневая задача о назначениях при обобщенном условии Монжа // Дискретный анализ и исследование операций, серия 2. 2003. Т. 10, №2. С. 19-28.

16. Демьянов В.Ф., Васильев JI.B. Недифференцируемая оптимизация. М.: Наука, 1981.

17. Иваненко Д.С., Плясунов A.B. О сводимости задач двухуровневого программирования к задачам векторной оптимизации // Дискретный анализ и исследование операций, серия 2. 2007. Т. 14, №1. С. 72-99.

18. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: учеб. пособие. М.: Лаборатория Базовых Знаний, 2002,

19. Измаилов А.Ф., Погосян А.Л. Условия оптимальности и ньютоновские методы для задач оптимизации с исчезающими ограничениями // Журнал вычислительной математики и математической физики. 2009. Т. 49, №7. С. 1184-1196.

20. Малышев A.B. Алгоритм поиска гарантированного решения квадратично-линейной двухуровневой задачи // Материалы Российской конференции "Дискретная оптимизация и исследование операций" (Алтай, 27 июня 3 июля 2010 года). Новосибирск, 2010. С. 116.

21. Малышев A.B. Алгоритм поиска гарантированного решения одной иерархической задачи оптимизации // Тезисы докладов II Международной школы-семинара "Нелинейный анализ и экстремальные задачи" (28 июня 4 июля 2010 г., Иркутск). Иркутск, 2010. С. 50.

22. Малышев A.B. Поиск гарантированного решения одного класса задач двухуровневого программирования // Труды VI Московской международной конференции по исследованию операций (ORM2010: Москва, 19-23 октября 2010). М.: МАКС Пресс, 2010. С. 239-240.

23. Малышев A.B. Численный поиск гарантированного решения в одной задаче двухуровневой оптимизации // Информационный бюллетень Ассоциации математического программирования. №12. "Тезисы докладов XIV Всероссийской конференции

24. Математическое программирование и приложения (Екатеринбург, 28 февраля 4 марта 2011)". Екатеринбург: УрО РАН, 2011. С. 47-48.

25. Малышев A.B., Стрекаловский A.C. О взаимосвязи некоторых задач двухуровневой и нелинейной оптимизации // Известия вузов. Математика. 2011. №4. С. 99-103.

26. Малышев A.B., Стрекаловский A.C. Глобальный поиск гарантированных решений в квадратично-линейных задачах двухуровневой оптимизации // Известия Иркутского государственного университета. Математика. 2011. Т. 4, №1. С. 73-82.

27. Моисеев H.H. Элементы теории оптимальных систем. М.: Наука, 1975.

28. Молодцов Д.А. О решении одного класса неантагонистических игр // Журн. вы-числ. матем. и матем. физики. 1976. Т. 16, №6. С. 1451-1456.

29. Молодцов Д.А., Федоров В.В. Аппроксимация игр двух лиц с передачей информации // Журн. вычисл. матем. и матем. физики. 1973. Т. 13, №6. С. 1469-1484.

30. Орлов A.B. Численное решение задач билинейного программирования // Журн. вычисл. матем. и матем. физики. 2008. Т. 48, №2. С. 45-62.

31. Орлов A.B., Стрекаловский A.C. О численном поиске ситуаций равновесия в би-матричных играх // Журн. вычисл. матем. и матем. физики. 2005. Т. 45, №6. С. 983-997.

32. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

33. Стрекаловский A.C. Минимизирующие последовательности в задачах с d.c. ограничениями // Журн. вычисл. математики и мат. физики. 2005. Т. 45, №3. С. 435-447.

34. Стрекаловский A.C. Об экстремальных задачах с d.c. ограничениями // Журн. вычисл. математики и мат. физики. 2001. Т. 41, №12. С. 1833-1843.

35. Стрекаловский A.C. О минимизации разности двух выпуклых функций на допустимом множестве // Журн. вычисл. матем. и матем. физики. 2003. Т. 43, №3. С. 399-409.

36. Стрекаловский A.C. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003.

37. Стрекаловский А.С., Орлов А.В. Биматричные игры и билинейное программирование. М.: Физматлит, 2007.

38. Стрекаловский А.С., Орлов А.В., Малышев А.В. Локальный поиск в квадратично-линейной задаче двухуровневого программирования // Сибирский журнал вычислительной математики. 2010. Т. 13, №1. С. 75-88.

39. Стрекаловский А.С., Орлов А.В., Малышев А.В. Численное решение одного класса задач двухуровневого программирования // Сибирский журнал вычислительной математики. 2010. Т. 13, №2. С. 201-212.

40. Фаддеев Д.К. Лекции по алгебре: учеб. пособие. СПб.: Изд-во «Лань», 2005.

41. Шамардин Ю.В. О двухуровневой задаче размещения при ограничениях на объем производства // Дискретный анализ и исследование операций, серия 2. 2000. Т. 7, №2. С. 114-118.

42. Aboussoror A, Mansouri A. Weak linear bilevel programming problems: existence of solutions via a penalty method // Journal of Mathematical Analysis and Applications. 2005. Vol. 304, №1. P. 399-408.

43. Al-Khayyal F.A., Horst R., Pardalos P.M. Global optimization of concave functions subject to quadratic constraints: an application in nonlinear bilevel programming // Annals of Operations Research. 1992. Vol. 34, №1-4. P. 125-147.

44. Alexandrov N,, Dennis J.E. Algorithms for Bilevel Optimization // AIA A/N AS A/US AF/ISSMO Symposium on Multidisciplinary Analyis and Optimization. 1994. P. 810-816.

45. Amouzegar M.A. A global optimization method for nonlinear bilevel programming problems // IEEE Transactions on Systems, Man, and Cybernetics, Part B. 1999. Vol. 29, №6. P. 771-777.

46. Anandalingam G., White D. A solution for the linear static Stackelberg problem using, • penalty function // IEEE Transactions Automatic Control. 1990. №35. P. 1170-1173.

47. Audet C., Hansen P., Jaumard B., Savard G. Links Between Linear Bilevel and Mixed 0-1 Programming Problems // Journal of Optimization Theory and Applications. 1997. Vol. 93, №2. P. 273-300.

48. Audet C., Savard G., Zghal W. New Branch-and-Cut Algorithm for Bilevel Linear Programming // Journal of Optimization Theory and Applications. 2007. Vol. 134, №2. P. 353-370.

49. Bard J.F. Convex two-level optimization // Mathematical programming. 1988. Vol. 40, №1. P. 15-27.

50. Bard J.F. Practical Bilevel Optimization. Dordrecht, The Netherlands: Kluwer Academic Publishers, 1998.

51. Bard J.F. Some properties of the bilevel programming problem // Journal of Optimization Theory and Applications. 1991. Vol. 68, №2. P. 371-378.

52. Ben-Ayed O., Blair C.E., Boyce D.E., LeBlanc L.J. Construction of a real-world bilevel linear programming model of the highway network design problem // Annals of Operations Research. 1992. Vol. 34, №1-4. P. 219-254.

53. Calamai P., Vicente L. Generating Linear and Linear-Quadratic Bilevel Programming Problems // SIAM Journal on Scientific Computing. 1993. Vol. 14, №4. P. 770-782.

54. Calamai P., Vicente L. Generating Quadratic Bilevel Programming Test Problems // ACM Transactions on Mathematical Software. 1994. Vol. 20. P. 103-119.

55. Calvete H. I., Gale C. On the quasiconcave bilevel programming problem // Journal of Optimization Theory and Applications. 1998. Vol. 98, №3. P. 613-622.

56. Colson B. BIPA (Bilevel programming with approximation methods): Software guide and test problems. Technical Report CRT-2002-38. Technical Report, Centre de Recherche sur les Transports, Universite de Montreal, Montreal, QC, Canada, 2002.

57. Colson B., Marcotte P., Savard G. An overview of bilevel optimization // Annals of operations research. 2007. Vol. 153, №1. P. 235-256.

58. Colson B., Marcotte P., Savard G. A trust-region method for nonlinear bilevel programming: algorithm and computational expirience // Computational optimization and applications. 2005. Vol. 30, №3. P. 211-227.

59. Candler W., Townsley R. A linear two-level programming problem // Computers and Operations Reseatch. 1982. №9. P. 59-76.

60. DeMiguel V., Murray W. A local convergence analysis of bilevel decomposition algorithms // Optimization and Engineering. 2006. Vol. 7, №2. P.99-133.

61. Dempe S. A Bundle Algorithm Applied to Bilevel Programming Problems with Non-Unique Lower Level Solutions // Comput. Optim. Appl. 2000. Vol. 15, №2. P.145-166.

62. Dempe S. Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints // Optimization. 2003. Vol. 52, №3. P. 333-359.

63. Dempe S. First-order necessary optimality conditions for general bilevel programming problems // Journal of Optimization Theory and Applications. 1997. Vol. 95, №3. P.735-739.

64. Dempe S. Foundations of Bilevel Programming. Dordrecht, The Netherlands: Kluwer Academic Publishers, 2002.

65. Dempe S., Bard J.F. Bundle Trust-Region Algorithm for Bilinear Bilevel Programming // Journal of Optimization Theory and Applications. 2001. Vol. 110, №2. P. 265-288.

66. Dempe S., Dutta J. Bilevel programming with convex lower level problems // Optimization with Multivalued Mappings, Springer Optimization and Its Applications. 2006. Vol. 2. P. 51-71.

67. Dempe S., Dutta J., Mordukhovich B.S. New necessary optimality conditions in optimistic bilevel programming // Optimization: A Journal of Mathematical Programming and Operations Research. 2007. Vol. 56, №5. P. 577-604.

68. Dempe S., Gadhi N. Necessary optimality conditions for bilevel set optimization problems // Journal of Global Optimization. 2007. Vol. 39, №4. P. 529-542.

69. Dempe S., Kalashnikov V.V., Kalashnykova N. Optimality conditions for bilevel programming problems / / Optimization with Multivalued Mappings, Springer Optimization and Its Applications. 2006. Vol. 2. P. 3-28.

70. Dempe S., Richter K. Bilevel programming with knapsack constraints // Central European Journal of Operations Research. 2000. Vol. 8, №2. P. 93-107.

71. Edmunds T.A., Bard J.F. Algorithms for nonlinear bilevel mathematical programs // IEEE Transactions on Systems, Man, and Cybernetics. 1991. Vol. 21, №1. P. 83-89.

72. Etoa Etoa J.B. Solving convex quadratic bilevel' programming problems using an enumeration sequential quadratic programming algorithm // Journal of Global Optimization. 2010. (In Print)

73. Faisca N.P., Dua V., Rustem В., Saraiva P.M., Pistikopoulos E. Parametric global optimisation for bilevel programming // Journal of Global Optimization. 2007. Vol. 38, №4. P. 609-623.

74. Falk J.E., Liu J. On bilevel programming, part I: general nonlinear cases // Mathematical Programming. 1995. Vol. 70, №1. P. 47-72.

75. FICO™ Xpress Optimization Suite. URL: http://www.flco.com/en/Products/DMTools/ Pages/FICO-Xpress-Optimization-Suite.aspx (дата обращения: 17.08.2010).

76. Fliege J., Vicente L.N. Multicriteria approach to bilevel optimization // Jornal of Optimization Theory and Applications. 2006. Vol. 131, №2. P. 209-225.

77. GLPK (GNU Linear Programming Kit). URL: http://www.gnu.org/software/glpk (дата обращения: 17.08.2010).

78. Gumus Z.H., Floudas C.A. Global Optimization of Nonlinear Bilevel Programming Problems // Journal of Global Optimization. 2001. Vol. 20, №1. P. 1-31.

79. Hansen P., Jaumard B., Savard G. New branch-and-bound rules for linear bilevel programming // SIAM Journal on Science and Statistical Computing. 1992. Vol. 13, №5. P. 1194-1217.

80. Herskovits J, Leontiev A An interior point technique for solving bilevel programming problems. Technical report, Institute of Mathematics, Federal University of Rio de Janeiro, 2002.

81. Hoai An L.T. DC Programming for solving a class of global optimization problems via reformulation by exact penalty // Proceedings of COCOS'2002. P. 87-101.

82. Hoai An L.T., Tao P.D., Canh N.N., Thoai N. DC programming techniques for solving a class of nonlinear bilevel programs // Journal of Global Optimization. 2009. Vol. 44, №3. P. 313-337.

83. Horst R., Tuy H. Global Optimization. Deterministic Approaches. Berlin: SpringerVerlag, 1993.

84. Jaumard B., Savard G., Xiong X. An exact algorithm for convex bilevel programming. Technical Report G-95-33. Technical Report, Groupe d'etudes et de recherche en analyse des decisions, Universite de Montreal, Montreal PQ, CANADA, 1995.

85. Jia F., Yang F., Wang S.-Y. Sensitivity analysis in bilevel linear programming // Systems Science and Mathematical Sciences. 1998. Vol. 11. P. 359-366.

86. Kolstad C.D., Lasdon L.S. Derivative evaluation and computational experience with large bilevel mathematical programs // Journal of Optimization Theory and Applications. 1990. Vol. 65, №3. P. 485-499.

87. Konnov I.V. Equilibrium Models and Variational Inequalities. Mathematics in Science and Engineering, Vol. 210. Amsterdam: Elsevier B.V., 2007.

88. Lignola M.B., Morgan J. Stability of regularized bilevel programming problems // Journal of Optimization Theory and Applications. 1997. Vol. 93, №3. P. 575-596.

89. Lin L.-J. Mathematical programming with system of equilibrium constraints // Journal of Global Optimization. 2007. Vol. 37, №2. P.275-286.

90. Liu G.S., Han J.Y., Zhang J.Z. Exact penalty functions for convex bilevel programming problems // Journal of optimization theory and applications. 2001. Vol. 110, №3. P. 621643.

91. Loridan P., Morgan J. Weak via strong Stackelberg problem: New results // Journal of Global Optimization. 1996. Vol. 8, №3. P. 263-287.

92. Luo Z.-Q., Pang J.-S., Ralph D. Mathematical programs with equilibrium constraints. Cambridge: Cambridge University Press, 1996.

93. Malyshev A.V., Strekalovsky A.S. Global search for pessimistic solution in bilevel problems // Proceedings of the Toulouse global optimization workshop 2010. Toulouse^ France, 2010. P. 77-80.

94. Marcotte P., Savard G. Bilevel programming: a combinatorial perspective // Graph Theory and Combinatorial Optimization. Springer US. 2005. P. 191-217.

95. Meyer R.R. Continuity properties of linear programs. Technical Report 373. Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1979.

96. Mitsos A., Lemonidis P., Barton P.I. Global solution of bilevel programs with a nonconvex inner program // Journal of Global Optimization. 2008. Vol. 42, №4. P. 475513.

97. Muu L.D., Quy N.V. A global optimization method for solving convex quadratic bilevel programming problems // Journal of global optimization. 2003. Vol. 26, №2. P. 199-219.

98. Norton R.D., Schiefer G.W. Agricultural sector programming models: a review of alternative approaches. Collaborative Paper, CP-80-30. International Institute for Applied Systems Analysis, Laxenburg, Austria, 1980.

99. Outrata J.V., Kocvara M., Zowe J. Nonsmooth approach to optimization problems with equilibrium constraints: Theory, applications and numerical results. Boston: Kluwer Acad. Publ., 1998.

100. Pang J.-S. Three modeling paradigms in mathematical programming // Mathematical Programming. 2010. Vol. 124, №2. P. 297-323.

101. Rajesh J., Gupta K., Kusumakar H.S., Jayaraman V.K., Kulkarni B.D. A Tabu Search Based Approach for Solving a Class of Bilevel Programming Problems in Chemical Engineering // Journal of Heuristics. 2003. Vol. 9, №4. P. 307-319.

102. Saboia C.H., Campelo M., Scheimberg S. A computational study of global algorithms for linear bilevel programming // Numerical Algorithms. 2004. Vol. 35, №2-4. P. 155-173.

103. Schelling T.C. The Strategy Of Conflict. Harvard Univercity Press, 1980.

104. Stackelberg H.F. Marktform und Gleichgewicht. Berlin, Germany: Springer-Verlag, 1934. Перевод на англ.: The Theory of the Market Economy. Oxford University Press, 1952.

105. Strekalovsky A.S., Orlov A.V. A new approach to nonconvex optimization // Вычислительные методы и программирование. Издательство Московского университета. 2007. Т. 8, №2. Р. 11-27.

106. Strekalovsky A.S., Orlov A.V., Malyshev A.V. On computational search for optimistic solutions in bilevel problems // Journal of Global Optimization. 2010. Vol. 48, JV21. P. 159-172.

107. Tsoukalas A., Wiesemann W., Rustem B. Global Optimization of Pessimistic Bi-Level Problems // Lectures on global optimization / Ed. by P.M. Pardalos, T.F. Coleman. Toronto, Canada, 2009. Vol. 55. P. 215-243.

108. Tuy H., Migdalas A., Hoai-Phuong N.T. A novel approach to Bilevel nonlinear programming // Journal of Global Optimization. 2007. Vol. 38, №4. P. 527-554.

109. Unlu G. A linear bilevel programming algorithm based on bicriteria programming // Computers and Operations Research. 1987. Vol. 14, №2. P. 173-179.

110. Vicente L., Savard G., Judice J. Descent approaches for quadratic bilevel programming // Journal of Optimization Theory and Applications. 1994. Vol. 81, №2. P. 379-399.

111. Vicente L., Savard G., Judice J. Discrete Linear Bilevel Programming Problem // Journal of Optimization Theory and Applications. 1996. Vol. 89, №3. P. 597-614.

112. Wang Y., Jiao Y.-C., Li H. An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme // IEEE Transactions on Systems, Man, and Cybernetics, Part A. 2005. Vol. 35, №2. P. 221-232.

113. Wang G.-M., Wan Z.-P., Wang X.-J. Genetic Algorithm for Solving Convex Quadratic Bilevel Programming Problem // Wuhan University Journal of Natural Sciences(EI). 2007. Vol. 12, №3. P. 421-425. •

114. Wets R.J.-В. On the continuity of the value of a linear program and of related polyhedral-valued multifunctions // Mathematical Programming Essays in Honor of George B. Dantzig Part I. Mathematical Programming Studies. 1985. Vol. 24. P. 14-29.

115. White D., Anandalingam G. A penalty function approach for solving bi-level linear programs // Journal of global optimization, 1993. Vol. 3. P. 397-419.

116. Yezza A. First-order necessary optimality conditions for general bilevel programming problems // Journal of Optimization Theory and Applications. 1996. Vol. 89, №1. P. 189-219.

117. Zhigljavsky A., Zilinskas A. Stochastic global optimization. Berlin: Springer, 2008.

118. Ziena Optimization LLC. KNITRO. URL: http://www.ziena.com/knitro.htm (дата обращения: 26.02.2011).