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

ПЕТРОВА ЕЛЕНА ГЕННАДЬЕВНА

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДОПОЛНИТЕЛЬНОСТИ И ДВУХУРОВНЕВОГО ПРОГРАММИРОВАНИЯ

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

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

7 ДПР 2011

Иркутск - 2011

4841946

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

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

профессор

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

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

профессор

Коннов Игорь Васильевич;

кандидат физико-математических наук Хамисов Олег Валерьевич.

Ведущая организация: Московский государственный

университет им. М.В. Ломоносова, факультет вычислительной математики и кибернетики.

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

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

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

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

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

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

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

Для большинства существующих методов решения задач с равенствами (методы приведенных градиентов, линеаризации, БС^Р-методы, различные двойственные методы) известны результаты о сходимости лишь к локальному экстремуму. Исключением является метод штрафов и различные его модификации, где сходимость носит глобальный характер (см. работы А. Фи-акко и Г. Мак-Кормика, Р. Куранта, У. Мюррея, Р. Флетчера и др.). Здесь все трудности перенесены на этап решения вспомогательных задач безусловной минимизации, которые обычно являются невыпуклыми, что затрудняет поиск их решений. Недостаток метода связан с необходимостью бесконечного увеличения параметра штрафа, в результате чего штрафная функция приобретает "овражный" характер, а влияние исходной целевой функции практически исчезает.

Другое направление в методах штрафов, получившее свое развитие в работах И.И. Еремина, В.Ф. Демьянова, О.Л. Малгасарьяна, У.И. Зангвилла и др., связано с построением точных штрафных функций, когда однократная безусловная оптимизация сразу же дает решение исходной задачи. Однако точные штрафные функции, как правило, оказываются недифференцируе-мыми, что создает дополнительные сложности при их минимизации.

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

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

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

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

Как известно, линейная задача дополнительности (ЛЗД) содержит в себе так называемое комплементарное нелинейное ограничение-равенство. Теория линейной дополнительности, впервые представленная в работах Р. Котт-ла, Дж. Данцига, К. Лемке, интенсивно развивается последние десятилетия, однако наибольшее количество работ традиционно посвящено методам решения ЛЗД с неотрицательно определенными матрицами и с матрицами, имеющими положительные главные миноры. В диссертации разработан алгоритм решения значительно более сложной ЛЗД: со знаконеопределенной матрицей.

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

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

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

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

A.C. Стрскаловского.

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

В результате исследований для линейной задачи дополнительности получены следующие результаты: предложены и обоснованы новые алгоритмы локального и глобального поисков с изменяющимися, но согласованными параметрами точностей решения вспомогательных задач на основе условий глобальной оптимальности в задачах d.c. минимизации; создана и протестирована программа, которая позволяет решать ЛЗД до размерности 400 со знаконеопределенными матрицами.

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

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

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

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

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

кающих в приложениях: задачи экономического равновесия, планирования производства, контактных задач в технике и т.д.

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

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

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

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

Публикации и личный вклад автора. По материалам диссертации опубликовано 12 работ, список которых приведен в конце автореферата. В число указанных работ входят статьи [1-3], опубликованные в журналах, рекомендованных ВАК РФ. Все результаты диссертации, выносимые на защиту, получены Е.Г. Петровой самостоятельно и не затрагивают интересы иных лиц. Из совместных публикаций с A.C. Стрекаловским, Е.С. Мазур-кевич, Т.В. Груздевой на защиту выносятся только результаты, полученные автором лично.

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

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

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

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

Мх + q = w,

<*,«;)= О, (1)

х>0, ги >0,

где х, w € Ж", а вектор q € Мп и вещественная знаконеопределенная матрица M размера (п х п) заданы.

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

В § 1.2 задача (1) сводится к невыпуклой задаче оптимизации:

F(x) = (х, Мх + q) I min,

х (2)

х > 0, Мх + q > 0.

Показано, что целевая функция F(-) является d.c. функцией, т.е. F(x) = G(x) - Н(х), где G(x) = {Мхх,х) + (q,x) и Н(х) = (М2х,х) -сильно выпуклые функции, Mi = Mf >0, г = 1,2.

В § 1.3 описан специальный метод локального поиска (СМЛП) для задачи (2) с учетом d.c. структуры целевой функции, заключающийся в решении

последовательности линеаризованных задач:

Js{x) = (Mi®, х) + (q- 2M2xs, х) i min, x e S, (3)

X

где S = {x € Bn : x > 0, q + Mx> 0}.

Следующий § 1.4 посвящен построению тестовых невыпуклых задач линейной дополнительности и тестированию СМЛП.

В § 1.5 описана схема алгоритма глобального поиска (АГП) в терминах задачи d.c. минимизации (2). Согласно стратегии глобального поиска1 (СГП) решение задачи разбивается на несколько более простых этапов, включающих локальный поиск и процедуры выхода из текущих критических точек, полученных на этапе локального поиска. Однако при применении общей СГП к конкретной задаче необходимо обосновать и детализировать отдельные ее этапы. В § 1.6 определяются параметры АГП, строится аппроксимация поверхности уровня выпуклой функции Я(-), производится выбор точностей решения вспомогательных задач и осуществляется тестирование АГП.

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

я(г/) = /?-Сь

где параметр ß выбирается из интервала ] inf(G, 5),sup(G, (к = F{zk) ~ значение целевой функции в текущей критической точке. Наиболее эффективно показала себя аппроксимация, состоящая из точек

у1 = Hid?, i = l,...,n + l,

где в качестве dl для i = 1,..., п использовались решения следующих задач линейного программирования:

(е',х) | min, х > 0, Mx + q> 0, i = l,...,n, (4)

a cf+1 находилось как решение аналогичной задачи

(е,г, х) i min, х > 0, Mx + q> 0, (5)

где е„ = (1,1,..., 1,1).

После выбора способа согласования точностей локального и глобального поисков, осуществленного в разделе 1.6.2, АГП был протестирован на задачах размерности до 400. На том же поле тестовых невыпуклых ЛЗД было

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

проведено сравнение результатов работы АГП, решателя PATH2, предназначенного для решения линейных задач дополнительности и процедуры quadprog (Matlab 6.5), реализующей метод активных множеств для задач квадратичного программирования, применительно к задаче (2). Результаты эксперимента показали, что, начиная с размерности 30, АГП значительно выигрывает по числу решенных задач у обеих программ, причем с повышением размерности этот разрыв увеличивается. Таким образом, результаты сравнительного эксперимента свидетельствуют об успешности применения АГП для решения ЛЗД со знаконсопределенными матрицами.

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

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

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

f{x,y) = (c,x) + (d,y) | min,

аМ/

x€X={xelRm\Ax< b}, (6)

у € Y.(x) = Arg min {(d\y) \ у € У(а:)} ,

где множество Y(x) определено системой неравенств

Y(x) = {уемп\ А1Х + Вху < ь1}, (7)

с € Мт, d, dl € Шп, Ъ € ШР, Ь1 € Ш:' — заданные векторы, А, Аи В]_ — матрицы размера (р х т), (q х т), (q х п) соответственно. Пусть, кроме того, выполнены следующие общепринятые предположения относительно задачи (6):

1) функция f(x, у) ограничена снизу на непустом множестве

Z € Мт, у € Мп | Ах < Ь, Ац + Вгу < Ь1};

2) функция {d},y) ограничена снизу на множестве Y(x) для всех х € X, так что inf inf{(d1, у) I у € Y(х), х G X} > —оо.

X у

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

2http: //pages-сз. wise. edu/~f erris/path. htal

В § 2.2 с помощью известного приема, использующего теорию двойственности в линейном программировании, задача (6) сводится к оптимизационной задаче

(с, х) + (d, у) J. min,

СР) (x,y,v)eS = {Ax<b, AlX + В1У < Ь\ vBi = -dl, и>0}, (8)

(d\y) = (A1x-b\v). Далее показано, что билинейная функция, задающая невыпуклое ограничение-равенство F(x,y,v) = (d1, у) — (А\х — bl,v) может быть представлена в виде разности двух выпуклых функций:

F(x,y,v) = g(x,y,v)-h(x,v), (9)

где д(х, у, и) = ^\\AlX - u||2 + (d\y) + (b\v), h(x, v) = ±\\Aix + vf.

Таким образом, исходная задача сведена к задаче минимизации с d.c. ограничением-равенством. В связи с этим далее изучаются свойства общей задачи с d.c. ограничением-равенством вида

/ ч /(я) J. min, х £ S, , ч

^ 10)

F(x) = g{x)-h{x) = 0

и разрабатывается метод ее решения с целью отыскания решения в (8).

Так в § 2.3 получены условия глобальной оптимальности (УГО) для задачи с d.c. равенством вида (10). Далее исследуется связь задачи (10) с задачей с d.c. ограничением-неравенством:

f(x) I min, xeS, F(x)=g{x)-h(x)< 0. 1 '

Показано, что из УГО для задачи (11) вытекают достаточные условия глобальной оптимальности в задаче (10).

Теорема 1. Пусть выполнены условия регулярности

3 veS : F(v) > 0, (12)

Vy € 5 : F(y) = 0 (д(у) = %)) Bp = р{у) е S : д{р) - д(у) < (Vh(y),p - у). Если z € S, F(z) = 0 и, кроме того, справедливо условие

V(y,/0): h(y)=ß,. y е S,

g(y)<ß<sMg,S), g(x)-ß>(Vh{y),x-y) Ух е S : f(x) < f(z),

(13)

mo z является решением задачи (10).

Доказаны теорема о необходимых условиях глобальной оптимальности и теорема о связи задач (10) и (11).

Теорема 2. Пусть выполнено предположение

3veS: F(v)> 0, /(«)•< V(7>o) = inf{f(x) I xeS, F(x) = 0}. (15)

X

Тогда если z — решение задачи (10), то

4(y,ß): h(y) = ß, yeS, g(x) -ß> (V h(y),x -y) \/xeS: f(x) < f(z).

Теорема 3. Пусть выполнено предположение (15). Тогда задача (10) эквивалентна задаче (11).

Следующий § 2.4 посвящен обобщению УГО на минимизирующие последовательности в задаче (10).

В §2.5 для решения задачи с d.c. ограничением-равенством предложена стратегия глобального поиска, аналогичная известной СГП для задачи (11) 3. Основными этапами СГП являются локальный поиск, построение аппроксимации поверхности уровня выпуклой функции h{-) и решение линеаризованных задач.

В §2.6 выполняется проверка условий регулярности из теорем 1, 2 для поставленной ранее задачи (8), к которой была сведена исходная двухуровневая задача. В силу свойств задачи (8) условие (13) оказывается невыполненным. С другой стороны, условия (15), принимающие в данном случае вид

Э(х, y,v) е S : F(x, у, v) > 0, f(x, у) < V(V), (16)

выполнены. В результате предлагается рассмотреть вместо (8) возмущенную задачу

f(x,y) = (с, х) + (d, у) | min,

(x,y,v)eS, (17)

F(x,y,v)-p = 0,

где 0 < р < F(x,y,v).

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

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

решение двухуровневой задачи, где задача нижнего уровня решается приближенно с точностью р:

f(x, у) = (с, х) + (d, у) 1 min, х € X = {х € Rm | Ах < 6}, (18)

у € Yt(x,P) £ {у € У(®) | <rf\l/> < infKd1,«)!« € У(®)] + р}.

Связь между задачами (17) и (18) устанавливает следующая теорема.

Теорема 4. Пусть тройка (х*, у*, v*) — решение задачи (17). Тогда пара (х*,у*) является решением двухуровневой задачи (18).

Таким образом, для отыскания решения двухуровневой задачи (6) предлагается вместо задачи (8) решать возмущенную задачу (17), в которой выполнены условия регулярности. При этом параметр р должен выбираться достаточно малым, чтобы точность решения задачи нижнего уровня была приемлемой для рассматриваемой задачи (6). Для решения задачи (17) предлагается применять СГП, одним из основных моментов которой является локальный поиск (поиск критических точек).

В §2.7 предлагается и обосновывается следующая конечная процедура поиска критической точки в задаче (17).

Процедура поиска критической точки

0. Найти вспомогательную точку

5 € Prx(Z) ={х£Х\3 уе Y(x) : (х,у) € Z}.

1. При фиксированном х := х € Prx(Z) найти решение (y,v*) задачи

(19)

(d, у) | min,

у,«

Агх + Biy < Ь1, vBi = -d\ v>Q, {di,у) = {Агх - buv) + p. t

2. При фиксированном v :— v* решить задачу

(20)

(с, x) + {d, у) I min,

У

Ax < b, Aix + Biy < 61, {di,y) = {Aix-bhv*)+p. ^

Пусть (x*,y*) — решение задачи (20), тогда, очевидно, (x*,y*,v*) — допустимая в задаче {Vp)-{17) точка, кроме того

f{x*,y*)<f{x,y) Ч(х,у) € Z ■. F{x,y,v*) = 0, (21)

так что точка (x*,y*,v*) является частичным минимумом функции /(•) по паре (х, у) при фиксированном v*.

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

В § 2.8 на основе СГП, представленной в § 2.5, разработан алгоритм глобального поиска для задачи (17) с учетом ее особенностей.

Пусть заданы числа /3_ = inf(g, S), 0+ = sup(.g, 5), М, Na € Z+-Алгоритм глобального поиска

Шаг 0. Положить к := 0. Выбрать х° G Prx(Z).

Шаг 1. Начиная с точки х°, используя процедуру поиска критической точки, найти (xk,yk,vk). Положить Ар (/3+ — р-)/М. Шаг 2. Положить '■— д{хк,Ук,vk) — р, 7fc := {с,хк) + {d,yk), i := 1. Шаг 3. Построить г-ю точку аппроксимации поверхности уровня функции h(-): Л = {(< и?) | h(uW) = рк, i = 1,..., Anillar 4. Найти (xlk, ytk, vlk) — решение линеаризованной задачи

±\\А1Х - u||2 + (d\y) + (b\v) ~ {Vg{u\w% (х, v)) | min, |

Лх < b, A1X + Biy < b\ vBx = -d\v> 0, ^ f < ^

(c,x) + {d,y) <7jb. J

Шаг 5. Начиная с точки хгк, используя процедуру поиска критической точки, найти (x',y',vl).

Шаг 6. Если f(xl,yl) < 7/с, то положить xk+1 := х\ yk+1 := у\ vk+l := v%, к к + 1 и идти на Шаг 2.

Шаг 7. Если f(x\ у1) >jk ni < Na, то г := i + 1 и идти на Шаг 3. Шаг 8. Если f(x\yl) >%, Р < Р+ ш i — Na, то положить Рк '■— Рк + Д/3, ¿ :=1 и идти на Шаг 3.

Шаг 9. Если /(z\f) > 1к, г = NA и р > /?+, то Stop: {xk,yk,vk) -решение задачи (Vp)-(17), найденное алгоритмом. #

В § 2.9 представлены результаты тестирования АГП. Вначале экспериментально выбиралась наиболее подходящая аппроксимация поверхности уровня выпуклой функции h(ui,Wi) = Р — задающей базовую невыпуклость в задаче (17). Наибольшую эффективность АГП показал в случае, когда в

^Caiamai P., Vicente L. Generating Linear and Linear-Quadratic Bilevel Programming Problems // SIAM Journal on Scicntific Computing archive. 1993. V. 14, № 4. P. 770-782.

качестве точек аппроксимации выбирались векторы, коллинеарные векторам из набора Dir3 = {(я* + е\ vk), г — 1,..., т}, где хк, vk — компоненты текущей критической точки. Одновременно при тестировании аппроксимаций были выявлены наиболее сложные классы задач. С учетом полученной информации далее было проведено тестирование АГП на задачах высокой размерности. В §2.10 приводятся результаты работы алгоритма глобального поиска для решения практической задачи планирования производства в условиях неизвестного спроса5.

Решение вспомогательных задач линейного программирования при поиске критических точек, а также линеаризованных квадратичных задач на шаге 4 осуществлялось посредством известного коммерческого пакета Xpress6. В ходе вычислительного эксперимента с помощью АГП удалось решить с заданной точностью 79 из 80 сгенерированных задач до размерности m + п = 1000. Известная из литературы7 максимальная размерность линейно-линейных двухуровневых задач, в которых удалось найти оптимистическое решение, составляет т + п = 200.

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

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

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

В § 3.1 ставится задача поиска корня уравнения

F(z) = 0, xeRn, (22)

где F(-) является d.c. функцией: F{x) = д(х) — h(x).

Пусть существуют точки и, v 6 Ш", удовлетворяющие соотношениям

F{u) = д{и) - h(u) < 0 < F(v) = g(v) - h(v). (23)

Отметим, что поставленная задача является вспомогательной в общей задаче (10) с d.c. ограничением-равенством для поиска допустимой точки, лучшей, чем текущая критическая.

В силу (23) существует число А € ]0; 1[, удовлетворяющее условию

хх = \и+ (1 -X)v = v + X(u-v) : F(x\) = 0. (24)

6Bard J.F. Practical Bilevel Optimization. Dordrecht: Kluwer Academic Publishers, 1998.

6Fair Isaac Corporation: Xpress Optimization Suite. URL: www.fico.com

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

В диссертации показано, что чем ближе А к нулю, тем лучше верхняя оценка для значения f(x(X)) в задаче (10), а в случае линейной функции /(•) минимальному А соответствует наименьшее значение f(x(А)). Предлагается следующая процедура выпуклой комбинации (ПВК) для отыскания корня уравнения (22).

Процедура выпуклой комбинации

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

Шаг 1. Вычислить

„ ,=_ВД__(2ъ

h(u)~h{x*)-(Vg(x*),u-xsy ( '

Шаг 2. Построить выпуклую комбинацию х := Xs + ц8(и — х3).

Шаг 3. Если F(x) < г, то Stop, х — е-решение уравнения F(x) = 0.

Шаг 4. Положить s := s + 1, xs := х, перейти на Шаг 1. //-

Установлено, что в случае д(х) = 0 или h(x) = 0 в одномерном случае (п = 1) ПВК превращается в известные метод хорд или метод Ньютона соответственно.

В §3.2 в случае е = 0 (когда итеративный процесс бесконечен) доказаны следующие свойства алгоритма.

Теорема 5. Числовая последовательность строящаяся по правилу (25), сходится к нулю: lim д, = 0.

S—»00

Следствие 1. Последовательность выпуклых комбинаций {зг5}, генерируемая ПВК, сходится: lim xs = х,.

S—»00

Введем множество чисел А, доставляющих корни уравнения (24), Л* = {А е [0,1] | F(Xu + (1 - А» - 0} и множество соответствующих им векторов х(\)

X* - (а; е Ж" j ЗА £ Л* : ® = Au + (1 - A)t>}.

Теорема 6. Последовательность {ж3} сходится к точке х* такой, что F(xt) = 0. Кроме того,

||г,-т;|| =тт{||я-г;|| \ х £ X*}. (26)

X

В §3.3 проведено численное сравнение ПВК с известным методом, представляющим собой компиляцию методов хорд и вилки, и методом половинного деления на задачах высокой размерности. Сравнение осуществлялось в среде MatLab г2009а. Результаты вычислительного эксперимента показали эффективность разработанной ПВК.

Вторая половина главы 3 посвящена решению систем d.c. уравнений. Рассматривается задача поиска корня системы уравнений

fi(x) = 9i{x) - hi(x) = 0, i — I,... ,т, (27)

где х € Шп, a g¡(x), К{х) — выпуклые на Rn функции, i = 1,..., т. Данная система сводится к задаче d.c. минимизации

га

F(x) = Y, |/¡(z)| 1 min, ж € Rn. (28)

i=i

При этом показано, что функция F(x) является d.c. функцией, поскольку представима в виде разности двух выпуклых функций G(x) и Н(х), где

m т

G{x) = 2^^max{g(¡(a!;), hi(x)}, Н{х) = + Ы(х)).

í=1 i=l

В частности, для систем квадратичных уравнений

Mx) = \{CiX,x) + (bi,x) + d¡ = 0, ¿ = l,...,n, (29)

где Ci — симметричные, необязательно положительно определенные матрицы размера (п х п), которые, как известно, можно разложить на разность двух положительно определенных матриц (C¿ = Ai — B¿, A¿ > 0, B¡ > 0), получено следующее d.c. представление:

n

G{x) = ^]тах{(Д;а;,2:) + {h,x) +d¿; (Bix,x) - (Ь{,х) - di},

i=1 i " (30)

H(x) = -(Sx,x), S = Y,(Aí + Bí), ¿ i=i

где S — симметричная, положительно определенная матрица.

Для задачи (28) на основе СГП, представленной в первой главе, разработан алгоритм глобального поиска, включающий в себя алгоритм локального поиска и процедуры выхода из критической точки. При этом, ввиду негладкости функции G(-), использовался недифференцируемый вариант специального метода локального поиска, в котором вспомогательные негладкие выпуклые задачи решались известным методом недифференцируемой оптимизации, называемым r-алгоритмом Н.З. Шора.

Далее был проведен численный эксперимент по сравнению АГП для решения нелинейных систем с Matlab-солвером STRSCNE8. Сравнение осу-

8Bcllavia S., Macconi М., Morini В. STRSCNE: A Scaled TVuat Region Solver for Constrained Nonlinear Equations // COAP. 2004. V. 28, № 1. P. 31-50.

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

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

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

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

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

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

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

1. Петрова Е.Г., Стрекаловский A.C. О решении систем нелинейных алгебраических уравнений // Современные технологии. Системный анализ. Моделирование. 2009. № 24(4). С. 30-36.

'Роозе А., Кулла В., Ломи М., Мерессоо Т. Набор тестовых систем нелинейных уравнений. Таллин: Валгус, 1989.

2. Мазуркевич Е.О., Петрова Е.Г., Стрекаловский A.C. О численном решении линейной задачи дополнительности // ЖВМ и МФ. 2009. Т. 49, № 8. С. 1385-1398.

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

4. Петрова Е.Г., Стрекаловский A.C. О вариационных методах решения систем нелинейных уравнений // Тр. XIII Байкальской междунар. школы-семинара "Методы оптимизации и их приложения". Иркутск, 2005. Т. 1. С. 319-324.

5. Петрова Е.Г. Вариационный подход для решения систем нелинейных уравнений // Материалы III Всерос. конф. "Проблемы оптимизации и экономические приложения". Омск, 2006. С. 151.

6. Стрекаловский A.C., Петрова Е.Г. О вариационном подходе при решении систем нелинейных уравнений // Материалы II Всерос. конф. "Ин-фокоммуникационные и вычислительные технологии и системы" (Улан-Удэ, Байкал, 1-4 июля, 2006 г.). Иркутск, 2006. С. 139-145.

7. Стрекаловский A.C., Петрова Е.Г. Вариационный подход к линейной задаче о дополнительности // Материалы Рос. конф. "Дискретная оптимизация и исследование операций" (Владивосток, 7-14 сентября 2007 г.). Новосибирск: Изд-во Института математики, 2007. С. 112.

8. Strekalovsky A.S., Petrova E.G. On an approach to linear complementarity problem // The Second Intern. Conf. on Optimization and Optimal Control. Ulaanbaatar (Mongolia), 2007. P. 40-41.

9. Петрова Е.Г., Груздева T.B. Линейные двухуровневые задачи как задачи оптимизации с невыпуклым ограничением // Тр. XIV Байкальской междунар. школы-семинара "Методы оптимизации и их приложения". Иркутск, 2008. Т. 1. С. 596-601.

10. Петрова Е.Г. Численное решение линейных двухуровневых задач высокой размерности // Материалы IV Всерос. конф. "Проблемы оптимизации и экономические приложения". Омск, 2008. С. 189.

11. Петрова Е.Г., Стрекаловский A.C. Процедура выпуклой комбинации для решения d.c. уравнений // Тез. докл. XI Байкальской школы-семинара молодых ученых "Математическое моделирование и информационные технологии" (Иркутск, 15-21 марта 2010 г.). Иркутск, 2010. С. 63.

12. Petrova E.G., Gruzdeva T.V. The linear bilevel problems via nonconvex constraint problems // Proc. of the Toulouse global optimization workshop. 2010. P. 123-126.

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

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

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

Введение

1 Оптимизационный подход к решению линейной задачи дополнительности

1.1 Постановка задачи. Различные формулировки линейной задачи дополнительности.

1.2 Редукция к задаче минимизации.

1.3 Специальный метод локального поиска.

1.4 Построение тестовых примеров и апробация алгоритма локального поиска.

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

1.6 Вычислительный эксперимент.

1.6.1 Выбор аппроксимации поверхности уровня.

1.6.2 Согласование точностей локального и глобального поиска.

1.6.3 Решение серий задач

1.7 Основные результаты главы.

2 Поиск оптимистических решений в линейной двухуровневой задаче

2.1 Постановка линейной двухуровневой задачи.

2.2 Сведение двухуровневой задачи к задаче с <±с. ограничением

2.3 Условия глобальной оптимальности для задачи минимизации с ограничением-равевом.

2.4 Минимизирующие последовательности.

2.5 Стратегия глобального поиска.

2.6 Решение возмущенной задачи.

2.7 Локальный по в задаче<1 ограничением-равевом.

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

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

2.8 Глобальный поиск в линейной двухуровневой задаче.

2.9 Вычислительный эксперимент.

2.9.1 Первый этап. Выбор аппроксимации поверхности уровня.

2.9.2 Второй этап. Оценка сложности задач.

2.9.3 Третий этап. Решение задач высокой размерности.

2.10 Задача планирования производства в условиях неизвестного спроса

2.11 Основные результаты главы.

3 Методы решения уравненийс1 функциями

3.1 Решение одного уравнения<1 функцией

3.2 Доказательство сходимости ПВК.

3.3 Вычислительный эксперимент.

3.4 Решение систем нелинейных уравнений.

3.5 Особенности решения квадратичных систем уравнений

3.6 Численное решение систем уравнений.

3.6.1 Квадратичные уравнения.

3.6.2 Нелинейные уравнения.

3.7 Основные результаты главы.

В последние годы круг приложений методов нелинейной оптимизации неуклонно расширяется. Если прежде в задачах планирования и управления экономическими объектами использовалось, как правило, линейное программирование, то теперь все чаще в экономико-математических исследованиях возникают нелинейные экстремальные задачи [60, 63]. При этом, по мнению ряда специалистов, наиболее сложными для решения являются оптимизационные задачи с нелинейными ограничениями-равенствами, в которых зачастую затруднительно нахождение даже допустимой точки ¡84, 110, 126]. Однако необходимость решения таких задач на практике побуждает исследователей к разработке эффективных численных методов.

Методы решения экстремальных задач с равенствами многочисленны и разнообразны. Их можно классифицировать как по формальным признакам, так и по содержательным. Так, выделяются методы нулевого, первого и второго порядков в зависимости от порядка используемых производных [3, 9, 15, 57]. Методы также делятся на прямые (в которых итерации ведутся в пространстве прямых переменных) [3, 4, 9, 57, 84] и двойственные (которые существенно используют двойственные переменные) [5, 9, 57]. Во многих методах на каждом шаге решается некоторая вспомогательная задача, и, с вычислительной точки зрения, удобно вести классификацию по ее типу. Это может быть задача безусловной минимизации, задача минимизации линейной или квадратичной функции при линейных ограничениях и т.д. Кроме того, одни методы направлены на поиск глобального решения задачи, другие же позволяют найти только локальный экстремум. Наконец, сами идеи, лежащие в основе методов, весьма различаются. Выделим основные направления в развитии данных методов.

В задачах небольшой размерности для нахождения стационарных точек, которые могут быть описаны системой Лагранжа [31], можно применять, например, метод Ньютона и его различные модификации [25, 45], а также методы безусловной минимизации [9, 57, 126] после сведения системы к оптимизационной задаче. Принципиальным недостатком такого подхода является то, что при этом пропадает оптимизационная сущность самой задачи, и, в частности, локальные максимумы и минимумы при использовании данного подхода не различаются.

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

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

На подобной идее основаны популярные в настоящее время методы последовательного квадратичного программирования (БС^Р-методы) [15, 31, 126], заключающиеся в решении задач выпуклого квадратичного программирования, аппроксимирующих исходную задачу оптимизации. Правильно выбранная задача квадратичного программирования оказывается достаточно адекватной локальной аппроксимацией исходной задачи. В то же время квадратичная задача достаточно проста, и для нее существуют эффективные методы решения. На сегодняшний день ЭС^Р-методы входят в число наиболее эффективных методов условной оптимизации [31, 126].

Другим направлением в решении задач с ограничениями-равенствами являются двойственные методы [57] (например, метод Эрроу-Гурвица), в которых одновременно происходит минимизация функции Лагранжа по ж и максимизация по двойственным переменным у. Другим двойственным подходом является метод модифицированной функции Лагранжа [5], который основан на добавлении гладкого штрафного слагаемого к функции Лагранжа минимизируемой функции, в результате чего получается так называемое семейство модифицированных функций Лагранжа.

Однако все утверждения относительно сходимости перечисленных методов носят локальный характер, т.е. гарантируют нахождение лишь локального экстремума. Исключением является метод штрафов и различные его модификации [9, 36, 57, 60, 84, 126], сходимость которых носит глобальный характер. Метод штрафных функций является одним из наиболее простых и широко известных методов решения задач математического программирования. Основная его идея состоит в приближенном сведении задачи минимизации с ограничениями к задаче безусловной минимизации некоторой функции. При этом вспомогательная функция подбирается так, чтобы она совпадала с заданной минимизируемой функцией внутри допустимой области и быстро возрастала вне ее. Здесь все трудности перенесены на этап решения вспомогательных задач безусловной минимизации, которые обычно оказываются невыпуклыми. Основной же недостаток метода состоит в том, что параметр штрафа должен бесконечно увеличиваться, а с ростом параметра задача становится все хуже обусловленной: целевая функция приобретает все более "овражный" характер.

Другой подход в области штрафных функций заключается в таком построении вспомогательных функций, что для соответствующего выбора параметра однократная безусловная оптимизация дает решение исходной задачи. Это — так называемый метод точной штрафной функции [22, 26, 27, 28]. Однако точные штрафные функции, как правило, оказываются недифференцируемыми, что придает дополнительную сложность при их минимизации.

Наконец, все большую популярность для поиска глобального решения невыпуклых задач, в том числе задач с равенствами, приобретают методы ветвей и границ, отсечений, аппроксимаций и т.д., идеи которых заимствованы из дискретной оптимизации [63, 116, 124, 129, 139]. К настоящему моменту предложено огромное количество алгоритмов, использующих различные варианты отыскания оценок и построения дерева поиска в задачах с равенствами. Одним из недостатков этих подходов является так называемое "проклятие размерности", которое означает, что с увеличением размерности объем вычислений по этим методам возрастает экспоненциально [129, 139], что не позволяет найти именно глобальное решение.

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

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

1. D.C. минимизация

F(x) = д(х) — h(x) I min, х € D, гДе 9(')> М') ~~ выпуклые функции на некотором открытом выпуклом множестве П С Ш.п, £> С П, т.е. F(■) — с1.с. функция.

2. Экстремальные задачи с с!.с. ограничениями, простейшей из которых является задача следующего вида где F{x) = д(х) — h(x), х € Í2, а /г(-), д(•),/(•) являются выпуклыми функциями на выпуклом открытом множестве О С IRn, содержащем множество D, F(-) — непрерывная функция па IRn.

Отметим, что в случае, когда функция д(-) тождественно равна нулю, то в первом случае получаем задачи выпуклой максимизации [66, 69], а во втором — обратно-выпуклые задачи [69, 71].

Понятие d.c. функции (функции, представимой в виде разности двух выпуклых функций) является одним из базовых в невыиуклой оптимизации.

Пионером в изучении свойств d.c. функций является А.Д. Александров [1]. Позже этой проблемой занимались Е.М. Ландис [40] и П. Хартмаи [105]. Некоторые более поздние работы по d.c. структурам можно найти в [107, 128].

Хотя исследование задач d.c. оптимизации (исключая частный случай — выпуклую максимизацию) началось сравнительно недавно, не более 40 лет назад, к настоящему моменту достигнуты определенные успехи. Во-первых, предложены условия глобальной оптимальности [65, 108, 109, 134], использующие современный аппарат выпуклого анализа [37, 59]. Кроме того, разрабатывается теория двойственности [107, 111, 137], а также связанные с характеризацией оптимума и двойственностью задач различные условия регулярности [111, 137]. )

В частности, на основе предложенных A.C. Стрекаловским условий глобальной оптимальности для представленных выше классов задач [67, 69, 70] были разработаны алгоритмы глобального поиска для решения многих актуальных теоретических и прикладных невыпуклых задач оптимизации [19, 44, 66, 68, 72, 78]. f{x) I min, xeD, F{x) < 0,

2)

Стратегия глобального поиска состоит из двух основных этапов: а) локального поиска и б) процедуры выхода из локального экстремума (критической точки), включающей в себя построение аппроксимациии поверхности уровня выпуклой функции, задающей базовую невыпуклость в исследуемой задаче, решение линеаризованных задач и ряд других [67, 69, 70].

В данной работе, основываясь на разработанных стратегиях глобального поиска, предпринимается попытка подойти к решению более сложных задач следующего вида: ж) 1 min, xeS, F(x) = 0, (3) где F(x) — д(х) — h(x), д(-), h(-), /(•) — выпуклые функции.

В работе предложены алгоритмы глобального поиска в задачах вида (3), базирующиеся на теории глобального поиска A.C. Стрекаловского. [67, 69, 70, 72].

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

Были выбраны следующие объекты диссертационного исследования:

• линейная задача дополнительности;

• линейная двухуровневая задача;

• одно уравнение с d.c. функцией и системы уравнений с d.c. функциями.

Как известно [88, 99, 100], линейная задача дополнительности (ЛЗД) содержит в себе комплементарное ограничение-равенство. Следующий же объект — линейная двухуровневая задача — может быть проинтерпретирован как некоторое усложнение предыдущей ЛЗД, поскольку после сведения двухуровневой задачи к оптимизационной, мы получаем задачу с линейной целевой функцией и схожими нелинейными комплементарными ограничениями. Для получения же допустимой точки в задачах оптимизации с равенствами требуется нахождение решения уравнения или системы уравнений.

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

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

Далее представим более подробно постановки задач и их особенности. В первой главе диссертации исследуется линейная задача дополнительности (ЛЗД) [88, 99, 100, 101, 104, 113, 123, 125, 127, 131, 135, 117], состоящая в нахождении пары векторов (ж, го), удовлетворяющих следующим условиям: где х, ги Е Ш1п, а вектор д Е Мп и вещественная, подчеркнем, знаконеопределенная (пхп)-матрица М заданы. Нетрудно видеть, что задачу (4) можно также записать в следующем виде:

Теория линейной дополнительности, впервые представленная в работах Коттла [99], Данцига [101], Лемке [122], интенсивно развивается три последних десятилетия, главной причиной чего служит связь ЛЗД с задачами линейного и квадратичного программирования [58]. Исторически задачу ЛЗД можно рассматривать в качестве объединяющей формулировки для задач линейного, квадратичного программирования и биматричных игр [100].

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

Решение ЛЗД в общем случае является нетривиальной задачей. Как известно [97], получение ответа на вопрос, имеет ли решение ЛЗД с целочисленными коэффициентами, оказывается ОТ-полной задачей [131]. Поэтому наиболее эффективными являются методы, ориентированные на использование свойств матрицы М, т.е. на отдельные классы ЛЗД. Таковыми могут быть, в частности, задачи с матрицами, имеющими неотрицательные главные миноры (или Р0-матрицами) [99,100]. Другим подобным классом могут быть задачи с матрицами, имеющими неположительные внедиагональные элементы (или Z-матрицами). Тогда можно построить эффективные методы решения как для ЛЗД, так и для ее нелинейных обобщений (напр., [104, 135]). Именно поэтому наибольшее количество

Мх + <7 = 1«, х, т) = 0, х > 0, и) > 0, х, Мх + д) = 0, х > 0, Мх + д > 0.

5) работ традиционно посвящено методам решения ЛЗД с неотрицательно определенными матрицами и с матрицами, имеющими положительные главные миноры. В качестве приоритетных можно выделить два основных направления развития.

Первое направление — это методы крайних точек ("pivoting methods"), являющиеся, по сути, разнообразными модификациями метода Лемке-Хаусона [100]. Процедура поиска решения основана на переборе крайних точек многогранного множества

S = {(ж, ш) е Rn+n :w = q + Мх, х > 0, w > 0}. (6)

Каждая итерация метода соответствует движению из крайней точки множества S вдоль некоторого его ребра, почти удовлетворяющего условиям дополнительности, т.е. ребра, на котором X{Wi ^ 0 только для одного значения индекса ?' е {1,., п}.

Этот метод является конечным вследствие конечного (но, возможно, очень большого) числа крайних точек многогранного множества. Однако нахождение решения ЛЗД (в случае его существования) гарантировано только при определенных условиях, налагаемых на матрицу М [58], например, при положительности всех ее главных миноров. Кроме того, данные методы эффективны в основном на задачах малой и средней размерности. С ростом размерности задачи резко увеличивается количество перебираемых вершин (как известно, количество вершин многогранного множества возрастает экспоненциально).

Второй подход к решению ЛЗД (который применяется в диссертационной работе) — это вариационный метод, заключающийся в минимизации некоторой целевой функции, например, скалярного произведения {х, w) на допустимом множестве S. Для решения такой задачи применяются, например, методы внутренних точек [23, 24, 30, 120] и специализированные методы квадратичного программирования [3, 16, 81, 126]. При решении вариационной задачи, как и в первом случае, успешность применяемых методов зависит от свойств матрицы М. Так, в случае знаконеопределенности матрицы М (что порождает невыпуклость в задаче), возникают проблемы с поиском глобального решения, поскольку стандартные методы выпуклой оптимизации в этом случае позволяют найти, в лучшем случае, локальное решение, а чаще — лишь стационарную точку, которая может быть далека от глобального оптимума.

Приведем пример прикладной задачи линейной дополнительности.

Пример 0.0.1 Равновесие рынка

Рассмотрим следующую модель рыночного равновесия [100]:

Поведение производственной стороны описывается задачей линейного программирования: с, я) | min, X

Ах > 6, Вх > г, (7) х > 0.

Здесь х — количество производимого товара, с — вектор затрат на производство, неравенство Ах > b описывает технологические ограничения, В — матрица ограничения на спрос, вектор г задает количество потребления.

Поведение потребителей характеризуется следующим образом: г = Dp + d,

8) гдер — вектор цен, функция С}(р) = Бр+(1 вектор-функция потребления, описывающая зависимость спроса от рыночных цен.

При этом должны выполняться условия равновесия:

Р = У >

9) где у* — двойственный вектор теневых (скрытых) цен, который может быть найден как решение двойственной [10] к (7) задачи, которая имеет следующий вид:

Ь,у) + {Ир + й,у) Т шах, у ьА + уВ < с, ^ (10)

V > 0, у > 0.

Тогда по теореме двойственности [10] или применив теорему Каруша-Куна-Таккера к задачам (7) и (10), получаем, что нахождение решения задач (7),(10) с учетом (8) эквивалентно решению системы х, с - Ату - Вту) = 0, х > 0, с - Ату - Вту > 0, (V, -Ь + Ах) = 0, у>0, —Ь + Ах > 0, (у, -й - Ир + Вх) = 0, у> 0, -й - Ир + Вх > 0.

П)

Отметим, что в системе (11) присутствуют нелинейные ограничения-равенства. При этом нетрудно видеть, что система (11) имеет вид ЛЗД с переменной 2 = (х,ь,у)т, где . \ (о ~ат ~вт ^ 7 с

-Ь / М =

АО О у В О -И у

В этом случае свойства матрицы М, в частности, симметричность и положительная определенность, напрямую зависят от вида матрицы —£>, которая характеризует поведение потребителей и может, вообще говоря, иметь произвольный вид. Таким образом, в общем случае получившаяся ЛЗД имеет знаконеопределенную матрицу М. #

Кроме того, к задачам линейной дополнительности часто сводятся различные технические и экономические задачи. В [100] авторы рассматривают следующие постановки: задача торможения, контактная задача, задача об опорном подшипнике, задача упруго-пластического кручения, задача об оптимальном постоянном основном капитале и т.д. В последнее время ЛЗД широко применяется для физического моделирования в компьютерных играх [121]. При этом в некоторых задачах матрица М является знаконеопреде-ленной.

С целью преодоления невыпуклости вариационной задачи в первой главе применяется теория глобального поиска [69], [ТО] для минимизации целевой функции, представимой в виде разности двух выпуклых функций (с!.с. функции).

В §1.1 представлены различные формулировки ЛЗД, показана ее связь с задачами линейного и квадратичного программирования, с биматричными играми. Далее, в §1.2 производится сведение исходной задачи к задаче с1.е. минимизации. Параграфы 1.3-1.4 посвящены методу локального поиска в задаче линейной дополнительности. В §1.5 предлагается алгоритм глобального поиска, заключающийся в последовательном решении более простых подзадач и основанный на условиях глобальной оптимальности. Наконец, в §1.6 представлены результаты численного эксперимента на серии случайно сгенерированных задач. Здесь решается вопрос выбора аппроксимации поверхности уровня выпуклой функции, позволяющей более эффективно находить глобальные решения, вопрос согласования точностей локального и глобального поиска. Далее проводится вычислительный эксперимент на задачах повышенной размерности.

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

В настоящее время задачи с иерархической структурой, возникающие на практике при исследовании сложноорганизованных систем в технике и экономике, являются весьма популярным объектом для математического исследования [11, 89, 90, 92, 96, 98, 103, 114, 132, 136, 138], популярность которого объяс.нятеся прежде всего широким полем приложений [90]. С другой стороны, иерархическая структура задач и связанная с ней скрытая невыпуклость даже в простейшем линейном случае [103] вызывают трудности исследования таких задач.

В работе исследуется непрерывная двухуровневая задача с линейными целевыми функциями на верхнем и нижнем уровнях [90, 103]. При этом предполагается, что из всех возможных решений на нижнем уровне выбирается то, которое благоприятствует достижению цели верхнего уровня. Такая постановка двухуровневой задачи носит название оптимистической (кооперативной) [103]. Будем рассматривать линейно-линейную двухуровневую задачу в следующей постановке: f{x, у) = (с, х) + (d, у) 1 min, (BV) X е х 4 {х е мт | Ас < &}, у Е У,(.т;) = Arg min {(d1, у) \ у Е У (ж)} , у

13) где множество У(х) определено системой неравенств:

У(х) й{уеяп\ Ахх + В1У < б1}, (14) 1 с Е Мт, d, d1 Е Л1п, Ь Е ШР, Ь1 е Ш4 — заданные векторы, А, В1 — матрицы размера (р х т), (<7 х тгь), (д х п) соответственно.

Несмотря на внешнюю простоту, задача (ВТ)-( 13) оказывается весьма сложной для решения. В §2.2 представлен пример, иллюстрирующий невыпуклость линейной двухуровневой задачи в самом простейшем случае.

За три десятилетия интенсивного исследования непрерывных двухуровневых задач различных классов было предложено достаточно много методов их решения (см., например, обзоры [98, 103]).

В линейно-линейном случае двухуровневая задача обладает тем свойством, что хотя бы одно ее глобальное решение достигается в крайней точке допустимого множества, поэтому широкий класс методов решения таких двухуровневых задач базируется на переборе вершин допустимого множества. Первые результаты в этом направлении были опубликованы в [96], а затем получили развитие в [102, 136] и др.

Еще одним интенсивно развивающимся направлением является разработка методов спуска, предназначенных для поиска стационарных точек и локальных минимумов в двухуровневых задачах [132].

Наиболее популярным подходом к решению двухуровневых задач является разработка методов, основанных иа замене задачи нижнего уровня ее условиями оптимальности (что возможно в случае выпуклой, в частности, линейной, целевой функции нижнего уровня по своей переменной) [103]. В результате вместо двухуровневой получаем эквивалентную ей одноуровневую задачу, но содержающую в своей структуре невыпуклое ограничение-равенство, которое и создает сложности при ее решении. В этом случае мы имеем дело с задачей, принадлежащей классу задач с комплементарными ограничениями, специальная структура которых создает трудности ее эффективного численного решения [32]. Тем не менее, учитывая комплементарность множителей Лагранжа и ограничений задачи нижнего уровня, можно предложить различные варианты метода ветвей и границ [89, 130]. Один из подходов в этом случае также составляют так называемые методы релаксации, в которых ограничение-равенство параметрически возмущается так, чтобы получаемая задача могла обладать свойствами регулярности ограничений [32].

Другой подход к решению двухуровневых задач — решение последовательности вспомогательных задач линейной дополнительности (см., например, [114]), что, по сути, представляет собой симбиоз методов крайних точек и ветвей и границ.

Кроме того, при использовании подхода, основанного на сведении двухуровневой задачи к одноуровневой, для решения последней часто применяется метод штрафов [94], хотя в силу невыпуклости оштрафованной целевой функции, такой подход обоснован только лишь для поиска локальных экстремумов [95]. В то же время уже удалось успешно использовать данный метод для численного поиска глобального решения [79, 80] в двухуровневых задачах с квадратичной целевой функцией на верхнем и линейной целевой функцией на нижнем уровнях.

Насколько можно судить по доступной литературе, размерность, которую приводят авторы публикаций при тестировании предлагаемых алгоритмов, является недостаточной для решения практических задач. Эффективно решаются только линейно-линейные задачи средней размерности. Так, в [89] приведены результаты решения таких задач с суммарным числом переменных до 130, а в [130] — до 200.

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

Пример 0.0.2 Планирование производства в условиях неизвестного спроса [90]

Предположим, что производитель желает определить, в каких объемах ему следует производить п товаров в каждый из рассматриваемых Т периодов. Вектор объемов производства обозначим через х € IRnxT. Задача производителя — максимизировать прибыль в условиях q ресурсных ограничений. Предполагается, что производитель работает только с одним потребителем (например, производство комплектующих деталей для последующей сборки автомобилей на автозаводе). Вектор спроса в £-й момент не известен точно, а лежит во множестве Yt, границы которого зависят от его затрат на рекламу, которые выражаются вектором v € МпхТ.

В модели будем использовать следующие обозначения. Параметры ciijt — количество ресурса г, необходимого для производства единицы продукции j в момент t, г = 1., q, j = 1,., n, £ = 1,., Т; bu — количество ресурса г, доступное в момент i; Pjt — цена продажи продукта j в момент ¿; Cjt — стоимость производства продукта j в момент i; hjt — цена хранения единицы продукта j в момент

Sjt — цена производства единицы продукта j по субконтракту в момент /,; dj — место, требуемое для хранения единицы продукции j\ lt — свободное место под хранение, имеющееся в момент t. Переменные

Xjt — количество продукта j, производимого в момент £;

Vjt — затраты на рекламу продукта j в момент

Zjt — нехватка продукта j в момент

Wjt — избыток продукта j в момент

Hjt — спрос на продукт j в момент t.

Множества

Vj — ограничения на рекламные расходы на продукт j] Yt(v) — множество, содержащее вектор спроса yt в момент t.

Верхний уровень управляет значениями переменных Xjt и Vjt, а нижний — переменными Zjt, wjt и уjt.

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

F(x, v, z, = ^2(cJtxjt + hjtwjt + sjtZjt + vjt) - PjiVjt I min, (15) j=l ¿=i j=l t=i n

ClijtZjt < bit i=i

Хц > О, VI е ц V? € {1,. е {1,. ,т}, у, IV, г) € 5о/((19) - (23)), в то время как задача нижнего уровня формализуется следующим образом: п т

У) = У2У2рцУц 1 пип, .7=1 ¿=1

Щг ~ Щь-1 + Уц ~ = хц 47 (Е {1,., та}, £ <Е {1,., Т}, п > О, > о, г^о = 0 V? € {1,. е {1,. ,т},

Неравенства (16) задают ресурсные ограничения. Ограничения на рекламные затраты заданы в (18) и влияют на спрос посредством (23). Уравнение (20) отражает материальный баланс. Начальные запасы полагаются нулевыми (формула (22)). Если и У( — многогранные множества, задача (15)-(23) является задачей линейного двухуровневого программирования. #

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

В §2.1 дается постановка задачи и обсуждается ее так называемая скрытая невыпуклость. В §2.2 производится сведение двухуровневой задачи к оптимизационной задаче с (1.с. ограничением-равенством. §2.3 посвящен условиям глобальной оптимальности для задач с с!.с. равенством в общем виде. Затем §2.4 обобхцает условия глобальной оптимальности па случай минимизирующих последовательностей. В §2.5—§2.6 описаны общие концепции глобального поиска для задачи с с!.с. ограничением.

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

17)

18)

19)

20) (21)

22) (23)

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

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

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

Третья глава посвящена поиску точек, удовлетворяющих ограничениям равенствам. Во второй главе при применении теории глобального поиска возникает необходимость нахождения допустимой по ограничению-равенству точки с использованием двух векторов, в которых функция принимает значения противоположных знаков. Решению этого вопроса посвящена первая часть главы, в которой предлагаются новый метод решения нелинейных уравнений со многими неизвестными: где д(х), 1г(х) — выпуклые на 1Яп функции. Необходимость решения одного уравнения со многими неизвестными возникает, например, в случае построения допустимой точки в задаче оптимизации с ограничением-равенством (см. §2.3). При этом разработанный метод позволяет находить специальную допустимую точку, наиболее подходящую, с точки зрения целевой функции. В одномерном случае это означает нахождение минимального корня уравнения, что находит широкое приложение во многих прикладных задачах: фазового детектирования, частотно-временного анализа, теории фильтров (см., например,

Далее в третьей главе рассматривается задача поиска точки, удовлетворяющей системе уравнений с с1.с, функциями: где д^{х),к{{х) — выпуклые на Мп функции, i = 1,.,ш. Отметим, что в работе не ставится задача поиска всех корней системы уравнений. Результаты по решению задачи в такой постановке можно найти, например, в [6, 7]. д{х) - к{х) = 0, х е ЛГ,

24)

62]). г(ж) = 0г(ж) - Ы{х) =0, г — 1,. ,т.,

25)

Несмотря на широкий спектр методов [4, 12, 25, 45], разработанных в этой области, проблема численного поиска решений систем нелинейных уравнений остается весьма актуальной.

Так, при применении методов типа Ньютона возникает трудность, заключающаяся в выборе подходящего начального приближения, обеспечивающего сходимость к решению [4, 9, 45, 64, 83]. Причем с ростом размерности системы сложность поиска стартовой точки многократно возрастает. Большие трудности при применении Ньютоновских методов также создает наличие в системе кратных корней [8].

В случае же использования вариационных методов, мы имеем дело с невыпуклой экстремальной задачей, а для ее решения неприемлемы стандартные методы выпуклой оптимизации, имеющие свойство отыскивать в лучшем случае лишь локальные решения или стационарные точки, которые могут быть весьма далеки от глобального решения [9, 57, 69, 81].

Один из способов решения систем уравнений заключается в следующем. Строится функция, минимум которой достигается на решении системы. Затем, начиная с некоторого стартового приближения к точке минимума, проводятся итерации каким-либо из методов минимизации. Таким путем получается удовлетворительное приближение к решению системы. Далее, исходя из этого приближения, производится уточнения при помощи какого-либо итерационного метода, предназначенного именно для решения систем уравнений, например, метода Ньютона [25, 45]. Применение методов минимизации на первоначальном этапе вызвано тем, что обычно они имеют более широкую область сходимости, чем методы, направленные на решение систем уравнений. В то же время последние обычно обладают лучшей скоростью сходимости при наличии достаточно хорошего начального приближения [4].

В последние десятилетия разработаны и успешно применяются на практике интервальные методы для доказательного глобального решения уравнений и систем уравнений [86], однако непреодолимым ограничением в этом случае является размерность систем.

Третья глава посвящена решению нелинейных уравнений и систем нелинейных уравнений. В §3.1 предлагается процедура выпуклой комбинации (ПВК) для решения одного уравнения со многими неизвестными, задаваемого с1.с. функцией. В §3.2 доказываются теоремы сходимости предложенного алгоритма, а в §3.3 проводится численное тестирование.

В §3.4—§3.6 рассматривается решение систем нелинейных уравнений. В §3.4 приведена постановка задачи. Как и линейная задача дополнительности в главе 1, система уравнений сводится к задаче с!.с. минимизации, для которой предлагается алгоритм глобального поиска. В §3.5 уточняется выбор параметров алгоритма на случай квадратичных уравнений, а в §3.6 проводится вычислительный эксперимент.

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

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

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

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

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

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

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

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

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

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

Заключение

1. Александров А.Д. О поверхностях, представимых разностью выпуклых функций / А.Д. Александров // Изв. АН КазССР. Сер. Матем. и механика — 1949. - № 3. -С. 3-20.

2. Амосов A.A. Вычислительные методы для инженеров / A.A. Амосов, Ю.А. Дубин-ский, Н.В. Копченова — М.: Мир, 1998.

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

4. Бахвалов Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков — М.: Наука, 1987.

5. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа / Д. Бертсе-кас — М.: "Радио и связь", 1978.

6. Булатов В.П. Численные методы поиска всех вещественных корней систем нелинейных уравнений / В.П. Булатов // ЖВМ и МФ. 2000. — Т.40, №3. - С. 348-355.

7. Булатов В.П. Глобальная оптимизация и методы нахождения всех корней систем нелинейных алгебраических уравнений / В.П. Булатов, Т.И. Белых // Дискретн. анализ и исслед. опер. — 2006. — Т.13, №1. — С. 3-9.

8. Булатов М.В. О свойствах конечномерных систем нелинейных уравнений с кратными решениями / В.П. Булатов, В.Ф. Чистяков // Труды XIV Байкальской международной школы-семинара. Том 3. — Иркутск: Изд-во ИСЭМ СО РАН, 2008. — С. 43-57.

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

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

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

12. Вержбицкий В.М. Основы численных методов / В.М. Вержбицкий — М.: Высшая < школа, 2002.

13. Втхорина М.В. Барьерно-проективный метод с наискорейшим спуском для линейных задач дополнительности / М.В. Втюрина, В.Г. Жадан // ЖВМ и МФ. — 2005. Т.45, № 5. - С. 792-812.

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

15. Гилл Ф. Практическая оптимизация / Ф. Гилл, У. Мюррей, М.Райт — М.: Мир, 1985.

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

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

18. Груздева Т.В. Локальный поиск в задачах с невыпуклыми ограничениямию / Т.В. Груздева, A.C. Стрекаловский // ЖВМ и МФ. 2007. - Т. 47, № 3. - С. 397-413.

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

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

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

22. Демьянов В.Ф. Условия экстремума и вариационное исчисление / В.Ф. Демьянов — М.: Высшая школа, 2005.

23. Дикин И.И. Непрерывный процесс для задачи линейной дополнительности / И.И. Дикин — Дискретн. анализ и исслед. опер., серия 2. — 2001. — Т. 8, № 2. — С. 27-30.

24. Дикин И.И. Метод внутренних точек в линейном и нелинейном программировании / И.И. Дикин М.: КРАС АНД, 2010.

25. Дэннис Дж. Численные методы безусловной оптимизации и решения нелинейных уравнений / Дж. Дэннис, Р. Шнабель — М.: Мир, 1988.

26. Еремин И.И. Метод "штрафов" в выпуклом программировании / И.И. Еремин // ДАН. — 1967. Т.173. - №4. - С. 748-751.

27. Еремин И.И. Введение в теорию линейного и выпуклого программирования / И.И. Еремин, H.H. Астафьев. М.:Наука, 1976.

28. Еремин И.И. К методу штрафов в математическом программировании / И.И. Еремин // Доклады РАН. 1996. - Т.346, № 4. -С. 459-461.

29. Ершова М.С. Введение в двухуровневое программирование / М.С. Ершова — Иркутск: Иркутский государственный университет, 2006.

30. Жадан В.Г. Метод Ньютона с наискорейшим спуском для линейной задачи дополнительности / В.Г. Жадан, A.B. Люлько — М.: ВЦ им. A.A. Дородницына РАН, 2002.

31. Измаилов А.Ф. Численные методы оптимизации / А.Ф. Измаилов, М.В. Солодов — М.: Физматлит, 2005.

32. Измаилов А.Ф. Чувствительность в оптимизации / А.Ф. Измаилов — М.: Физматлит, 2006.

33. Ильин В.А. Линейная алгебра / В.А. Ильин, Э.Г. Поздняк — М.: Наука, 1978.

34. Иоффе А.Д. Теория экстремальных задач / А. Д, Иоффе, В. М. Тихомиров — М.: Наука, 1974.

35. Калиткин H.H. Численные методы / H.H. Калиткин — М.: Гл. ред. физ.-мат. лит., 1978.

36. Карманов В.Г. Математическое программирование / В.Г. Карманов — М.: Наука, 1986.

37. Кларк Ф. Оптимизация и негладкий анализ / Ф. Кларк — М.: Наука, 1988.

38. Колмогоров А. Н. Элементы теории функций и функционального анализа / А.Н. Колмогоров, C.B. Фомин — М.: Наука, Гл. ред. физ.-мат. лит., 1972.

39. Красносельский М.А. Приближенное решение операторных уравнений / М. А. Красносельский — М.: Наука, 1969.

40. Ландис Е.М. О функциях, представимых в виде разности двух выпуклых / Е.М. Ландис // Доклады Академии Наук СССР. 1951. - Т.80, № 1. — С. 9-11.

41. Михалевич B.C. Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы / B.C. Михалевич, В.А. Трубин, Н.З. Шор — М.: Наука, Гл. ред. физ.-мат. лит., 1986.

42. Мазуркевич Е.О. О численном решении линейной задачи дополнительности / Е.О. Мазуркевич, Е.Г. Петрова, A.C. Стрекаловский // ЖВМ и МФ. — 2009. — Т.49, № 8. С. 1385-1398.

43. Мухамедиев Б.М. О решении задачи билинейного программирования и отыскании всех ситуаций равновесия в биматричных играх / Б.М. Мухамедиев // ЖВМ и МФ. 1978. - Т. 18, № 2. - С. 351-359.

44. Орлов A.B. Численное решение задач билинейного программирования / A.B. Орлов // ЖВМ и МФ. 2008. - Т.48, № 2. - С. 237-254.

45. Ортега Дж. Итерационные методы решения нелинейных систем уравнений со многими неизвестными / Дж. Ортега, В. Рейнболдт — М.: Мир, 1975.

46. Петрова Е.Г. Решение систем Б.С. уравнений / Е.Г. Петрова // Тезисы докладов VII Байкальской школы-семинара молодых ученых "Математическое моделирование и информационные технологии". — Иркутск, 2005. — С. 29-30.

47. Петрова Е.Г. Вариационный подход для решения систем нелинейных уравнений / Е.Г. Петрова // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". — Омск, 2006. — С. 151.

48. Петрова Е.Г. К теории двойственности в невыпуклых задачах / Е.Г. Петрова // Труды III межвузовской зональной конференции "Математика и проблемы ее преподавания в вузе". — Иркутск: Изд-во Иркут. гос. пед. ун-та, 2007. — С. 114.

49. Петрова Е.Г. Линейные двухуровневые задачи как задачи оптимизации с невыпуклым ограничением / Е.Г. Петрова, Т.В. Груздева // Труды XIV Байкальской международной школы-семинара. Том 1. — Иркутск: Изд-во ИСЭМ СО РАН, 2008. — С. 596-601.

50. Петрова Е.Г. О решении систем нелинейных алгебраических уравнений / Е.Г. Петрова, А.С. Стрекаловский // Современные технологии. Системный анализ. Моделирование. 2009. - №24(4). — С. 30-36.

51. Петрова Е.Г. Численное решение линейных двухуровневых задач высокой размерности / Е.Г. Петрова // Материалы IV Всероссийской конференции "Проблемы оптимизации и экономические приложения". — Омск, 2008. — С. 189.

52. Поляк Б.Т. Введение в оптимизацию / Б.Т. Поляк — М: Наука, 1983.

53. Попов Л.Д. Введение в теорию, методы и экономические приложения задач о дополнительности / Л.Д. Попов // Учеб. пособие. Екатеринбург: Изд-во Урал, ун-та, 2001.

54. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи / Б.Н. Пшеничный — М.: Наука, Гл. ред. физ.-мат. лит., 1980.

55. Пшеничный Б.Н. Численные методы в экстремальных задачах // Б.Н. Пшеничный, Ю.М. Данилин — М.: Наука, 1975.

56. Роозе А. Набор тестовых систем нелинейных уравнений / А. Роозе, В. Кулла, М. Ломп, Т. Мерессоо — Таллин: Валгус, 1989.

57. Сергеев Я.Д. Диагональные методы глобальной оптимизации / Я.Д. Сергеев, Д.Е. Квасов — М.: Физматлит, 2008.

58. Современное состояние теории исследования операций / Под редакцией Н. Н. Моисеева. — М.: Наука, Гл. ред. физ.-мат. лит., — 1979.

59. Срочко В.А. Численные методы: курс лекций / В.А. Срочко — Иркутск: Иркут. ун-т, 2004.

60. Стрекаловский A.C. Условия глобальной оптимальности в задачах d.c. программирования / A.C. Стрекаловский // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск: Изд-во ИГУ, 1997.

61. Стрекаловский А. С. О сходимости алгоритма глобального поиска в задаче выпуклой максимизации на допустимом множестве / A.C. Стрекаловский, A.A. Кузнецова // Известия высших учебных заведений. Математика. — 1999. — №12. — С. 74-81.

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

63. Стрекаловский A.C. О численном решении задач невыпуклой оптимизации / A.C. Стрекаловский, А.А.Кузнецова, Т.В. Яковлева // Сибирский журнал вычислительной математики. — 2001. — Т. 4, № 2. — С. 185-199.

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

65. Стрекаловский A.C. О минимизации разности двух выпуклых функций на допустимом множестве / A.C. Стрекаловский // ЖВМ и МФ. —2003. — Т. 43, № 1.-С. 49-59.

66. Стрекаловский A.C. Модификация метода Розена в обратно-выпуклой задаче / A.C. Стрекаловский, Т.В. Яковлева // Известия вузов. Математика 2005. — № 12(523). С. 70-75.

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

68. Стрекаловский A.C. Элементы теории двойственности для задач d.c. минимизации / A.C. Стрекаловский, Е.Г. Петрова // Материалы конференции. Ляпуновские чтения и презентация информационных технологий — Иркутск, 2006. — С. 42.

69. Стрекаловский A.C. О задачах с ограничениями типа равенств / A.C. Стрекаловский, Е.Г. Петрова // Информационный бюллетень № 11, Тезисы докладов конференции "Математическое программирование и приложения". — Екатеринбург, 2007. С. 84-85.

70. Груздева Т.В. Локальный поиск в задачах с невыпуклыми ограничениями / Т.В. Груздева, A.C. Стрекаловский // ЖВМ и МФ. — 2007. — Т. 47. № 3. — С. 397413.

71. Стрекаловский A.C. Биматричные игры и билинейное программирование / A.C. Стрекаловский, A.B. Орлов — М.: Физматлит, 2007.

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

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

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

75. Тыртышников Е.Е. Матричный анализ и линейная алгебра / Е.Е. Тыртышников — М.: Физматлит, 2007.

76. Фаддеев Д.К. Вычислительные методы линейной алгебры / Фаддеев Д.К., Фадде-ева В.Н. С-Пб.: Лань, 2002.

77. Фиакко А. Нелинейное программирование. Методы последовательной безусловной минимизации / А. Фиакко, Г.П. Мак-Кормик — М.: Мир, 1972.

78. Хамисов О.В. Нахождение корней нелинейного уравнения методом вогнутых опорных функций / О.В. Хамисов // Труды XII Байкальской международной конференции. Том 4. Иркутск: Изд-во ИСЭМ СО РАН, 2001. - С. 194-198.

79. Шарый С.П. Интервальные методы для систем уравнений и необходимость переформулировки задачи / С.П. Шарый — Вычислительные Технологии. — в печати.

80. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения / Н.З. Шор — Киев: Наукова думка, 1976.

81. Alefeld G. Solutions of Linear Complementarity Problems for H-matrices / G. Alefeld, Z. Wang, Z. Shen // Reliable Computing. — 2004. — V.10. — P. 423-435.

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

83. Bard J.F. Practical Bilevel Optimization / J.F. Bard — Dordrecht: Kluwer Academic Publishers, 1998.

84. Bellavia S. STRSCNE: A Scaled Trust Region Solver for Constrained Nonlinear Equations / S. Bellavia, M. Macconi, B. Morini // COAP, 2004. V. 28, №. 1. — P. 31-50.

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

86. Calamai P. Generating Quadratic Bilevel Programming Test Problems / P. Calamai, L. Vicente // ACM Transactions on Mathematical Software. — 1994. — V.20. — P. 103119.

87. Campelo M. A Note on a Penalty Function Approach for Solving Bilevel Linear Programs / M. Campelo, S. Dantas, S. Scheimberg // Journal of global optimization. — 2000. V. 16. - P. 245-255.

88. Campelo M., Scheimberg S. A Study of Local Solutions in Linear Bilevel Programming / M. Campelo, S. Scheimberg // Journal of optimization theory and applications. — 2005. V.125, №1. - P. 63-84.

89. Candler W. A linear two-level programming problem / W. Candler, R. Townsley // Computers and Operations Research. — 1982. — V.9. — P. 59—76.

90. Chung S. J. NP-Completeness of the Linear Complementarity Problem / S.J. Chung // Journal of optimization theory and applications. — 1989. — V. 60 , №3. — P. 393-399.

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

92. Cottle R.W. Linear Complementarity since 1978 / R.W. Cottle // Variational Analysis and Appls. 2007. - V.79. - P. 239-257.

93. Cottle R.W. The Linear complementarity problem / R.W. Cottle, J.S. Pang, R.E. Stone — Academic Press, 1999. /

94. Dantzig G.B. Positive (semi-)definite programming / G.B. Dantzig, R.W. Cottle // Nonlinear Programming. — Amsterdam: North-Holland, 1967. — P. 55-73.

95. Dempe S. A simple algorithm for the linear bilevel programming problem / S. Dempe // Optimization. 1987. — V.18. — P. 373-385.

96. Dempe S. Foundations of Bilevel Programming / S. Dempe — Dordrecht: Kluwer Academic Publishers, 2002.

97. Facchinei F. Finite-Dimensional Variational Inequalities and Complementarity Problems / F. Facchinei, J.-S. Pang —- Berlin: Springer Verlag, 2003 (two volumes).

98. Hartman P. On Functions Representable as a Difference of Convex functions / P. Hartman // Pacific Journal of Mathematics. — 1959. — V.9 — P. 707-713.

99. Hiriart-Urruty J.-B. Conditions for Global Optimization / J.-B. Hiriart-Urruty // Handbook of Global Optimization, Kluwer Academic Publishers. — 1995. — P. 1-26.

100. Hiriart-Urruty J.-B. Conditions for Global Optimality / J.-B. Hiriart-Urruty // Handbook of Global Optimization. — Dordecht: Kluwer Academic Publishers, 1995. P. 1-26.

101. Horst R. Global Optimization. Deterministic Approaches / R. Horst, Ii. Tuy — Berlin: Springer-Verlag, 1993.

102. Horst R. D.C. Programming: Overview / R. Horst, N.V. Thoai // Journal of Optimization Theory and Applications. — 1999. — V.103, №1. — P. 1-43.

103. Horst R. Introduction to global optimization/ R. Horst, P. Pardalos, N. V. Thoai — Dordrecht-Boston-London: Kluwer Academic Publishers, 1995. — V.3. — 246 p.

104. Jia F. Sensitivity analusis in bilevel linear programming / F. Jia, F. Yang, S.-Y. Wang. // Systems Science and Mathematical Sciences. — 1998. — V. 11. — P. 359-366.

105. Judice J.J. The linear-quadratic bilevel programming problem / J.J. Judice, A. Faustino // Information Systems and Operational Research. — 1994. — V. 32. — P. 87-98.

106. L.V. Kolev A new method for global solution of systems of non-linear equations / L.V. Kolev // Reliable Computing. 1998. - V.4. - P. 125-146.

107. Land A.H. An automatic method of solving discrete programming problems / A.H. Land, A.G. Doig // Econometrica. 1960 - V. 28, №3. — P. 497-520.

108. Le Th.H. DC Programming Approaches and DCA for globally solving Linear Complementarity Problems / Th.H. Le, D.T. Pham // Research Report, National Institute for Applied Sciences, Rouen, 2004.

109. Le Th.H. The DC (difference of convex functions) Programming and DCA revisited with DC models of real world nonconvex optimization problems / Th.H. Le, D.T. Pham // Annals of Operations Research. — 2005. V. 133. — P. 23-46.

110. Lemke C.E. Equilibrium points of bimatrix games / C.E. Lemke, J.T. Howson // SIAM Journal on Applied Mathematics. — 1964. — V.12. — P. 413-423.

111. Kojima M. A unified approach to interior point algorithms for linear complementarity problems / M. Kojima, N. Megiddo, T. Noma, A. Yoshise — Berlin: Springer-Verlag, 1991.

112. Morales J.L. An algorithm for the fast solution of linear complementarity problems / J.L. Morales, J. Nocedal, M. Smelyanskiy // Numerische Mathematik. — 2008. —V.3, №2. -P. 251-266.

113. More J.J. Classes of functions and feasibility conditions in nonlinear complementarity problems / J.J. More // Math. Programming. — 1974. — V.6, №3. — P. 327-338.

114. Li L. A Block Recursive Algorithm For the Linear Complementarity Problem With an M-matrix / L. Li, Y. Kobayashi // International Journal of Innovative Computing, Information and Control ICIC International. — 2006. — V.2, №6. — P. 1327-1335.

115. Nemhauser G.N. Integer and Combinatiorial Optimization / G.N. Nemhauser , L.A. Wolsey — Wiley-Interscience Publication, 1999.

116. Nguyen V.Th. Global Optimization Method for Solving Mathematical Programs with Linear Complementarity Constraints / V.Th. Nguyen, Y. Yamamoto, A. Yoshise // Journal of Optimization Theory and Application. — 2005. — №124. — P. 467—490.

117. Nocedal J. Numerical optimization / J. Nocedal, S.J. Wright — New York, Berlin, Heidelberg: Springer-Verlag, 2000.

118. Pang J.S. Complementarity problems / J.S. Pang // Handbook of Global Optimization, Kluwer Academic Publishers. 1995. - P. 271-338.

119. Penot J.-P. Approximation and decomposition properties of some classes of locally d.c. functions / J.-P. Penot, M.L. Bougeard // Mathematical Programming. — 1988. — V.41. P. 195-227.

120. Pochet Y. Production Planning by Mixed Integer Programming / Y. Pochet , L.A. Wolsey — Springer, 2006.

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

122. Simantiraki E.M. An Infeasible-Interior-Point method for linear complementarity problems / E.M. Simantiraki, D.F. Shanno // Rutcor Research Report. — 1996.

123. Still G. Linear bilevel problems: Genericity results and an efficient method for computing local minima / G. Still // Math. Meth. Oper. Res. — 2002. — V.55. — P. 383—400.

124. Strekalovsky A.S. On an approach to linear complementarity problem / A.S. Strekalovsky, E.G. Petrova // The Second International Conference on Optimization and Optimal Control. — Mongolia, Ulaanbaatar, 2007. — P. 40-41.

125. Tamir A. Minimality and complementarity problems associated with Z-functions and M-functions // Mathematical Programming. — 1974. — V.7, №1. — P. 17-31.

126. Tuy H. A global optimization approach for the linear two-level program / H. Tuy, A. Migdalas, P. Vbrand // Journal of Global Optimization. — 1993. — V.3. — P. 123.

127. Tuy H. D.C. Optimization: Theory, Methods and Algorithms / H. Tuy // Handbook of Global Optimization, Kluwer Academic Publishers, 1995. — P. 149-216.

128. White D. A penalty function approach for solving bi-level linear programs / D. White, G. Anandalingam // Journal of Global Optimization. 1993. — V.3. - P. 397-419.

129. Wolsey L.A. Integer Programming / L.A. Wolsey — Wiley & Sons, Inc., 1998.

130. Fair Isaac Corporation: Xpress Optimization Suite. URL: www.fico.com.

131. CPLEX user's manual. ILOG, Inc. URL: www.ilog.com

132. URL: http://pages.cs.wisc.edu/~ferris/path.html.

133. URL: http: //www. mathworks . com.