Параметризация и обратная дополнительность в моделировании и решении оптимизационных задач тема диссертации и автореферата по ВАК РФ 05.13.18, доктор физико-математических наук Зыкина, Анна Владимировна

• Зыкина, Анна Владимировна
• доктор физико-математических наук
• 2007

Оглавление диссертации доктор физико-математических наук Зыкина, Анна Владимировна

Предисловие

Введение

1. Задача обратной дополнительности

1.1. Обратная дополнительность для задачи оптимизации

1.2. Разрешимость задачи обратной дополнительности

1.3. Обратная дополнительность в модели дифицита ресурсов

1.4. Обратная дополнительность и условия Куна-Таккера

2. Обратная дополнительность в несобственных задачах

2.1. Общая схема коррекции несобственных задач МП

2.2. Задача коррекции для системы неравенств.

2.3. Коррекция несобственных задач ЛП

2.4. Частные случаи коррекции несобственных задач ЛП

2.5. Коррекция несобственных задач КП

3. Обратная дополнительность в векторной оптимизации

3.1. Обратная дополнительность для решения задачи МП

3.2. Обратная дополнительность с ограничениями

3.3. Задача целевого программирования.

3.4. Модель последовательной оптимизации.

3.5. Модификация алгоритма последовательной оптимизации

4. Итеративные методы решения обратной задачи

4.1. Непрерывная траектория для обратной дополнительности

4.2. Метод оценочной функции

4.3. Градиентный метод для линейной дополнительности

4.4. Модифицирований градиентный метод.

4.5. Экстрапроксимальный метод.

4.6. Прогнозный метод проекции градиента.

5. Решение прикладных задач

5.1. Задача стохастического программирования.

5.2. Формирование портфеля ценных бумаг.

Введение диссертации (часть автореферата) на тему «Параметризация и обратная дополнительность в моделировании и решении оптимизационных задач»

Актуальность темы

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

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

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

Цель работы

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

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

Методы исследования

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

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

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

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

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

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

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

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

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

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

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

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

Рассматриваются вопросы, связанные с вырожденностью решения линейной задачи дополнительности, предлагается прием преодоления вырожденности, вводится понятие е—вырожденности.

Доказаны сходимости алгоритмов, получены оценки скорости сходимости.

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

В заключении приведено развернутое изложение основных научных результатов, их использование и дальнейшее развитие.

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

Научная новизна

Научную новизну работы образуют перечисленные ниже основные результаты (защищаемые положения), изложенные в соответствующих разделах диссертации (более подробно защищаемые положения рассмотрены в разделе "Заключение"):

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

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

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

Практическая значимость

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

Кроме того, построенные параметрические модели для задач принятия решений и разработанные алгоритмы для их решения используются в учебных процессах в Омском государственном техническом университете и в Омском государственном университете в дисциплинах "Теория принятия решений", "Методы оптимизации", "Несобственные задачи математического программирования", "Противоречивые модели оптимального планирования", в аспирантских диссертациях, в курсовых и дипломных проектах, а также при моделировании практических задач, выполняемых в рамках госбюджетных научно-исследовательских работ ОмГТУ (регистрационные номера НИР 1.4.01.Ф, 7.04.Ф).

Апробация

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

Международные: "Проблемы оптимизации и экономические приложения" (Омск, 1997); "Динамика систем, механизмов и машин" (Омск, 1997, 1999, 2002); ИНПРИМ-1998 (Новосибирск, 1998); конференция по исследованию операций (Новосибирск, 1998); конференция по анализу и геометрии, посвященная 70-летию академика Ю.Г. Решет-няка (Новосибирск, 1999); "Методы оптимизации и их приложения" (Иркутск-Слюдянка, 2001, Иркутск-Северобайкальск, 2005 ).

Межрегиональные и региональные: Всероссийская научная конференция "Математическое программирование и приложения" (Екатеринбург, 1999, 2003, 2007); Всероссийская научная конференция "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2001); Российская конференция "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004); "Проблемы оптимизации и экономические приложения" (Омск, 2003, 2006); 37-я Региональная молодежная конференция "Проблемы теоретической и прикладной математики" (Екатеринбург, 2006); Седьмой Всероссийский симпозиум "Стратегическое планирование и развитие предприятий" (Москва, 2006).

В целом материалы диссертации докладывались на научных семинарах кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета под председательством профессора Ф.П. Васильева (Москва, 2007), отделения информатики и прикладной математики механико-математического факультета Южно-Уральского государственного университета под председательством профессора Л. Б. Соколинского (Челябинск, 2007), отделения математического моделирования НИИ математики и механики им. Н.Г. Чеботарева Казанского государственного университета под председательством профессора А.В. Лапина (Казань, 2004, 2006), отдела прикладных проблем оптимизации Вычислительного центра им. А.А. Дородницына РАН под председательством академика Ю.Г. Евтушенко (Москва, 2006), а также неоднократно в Омском государственном техническом университете.

Публикации

По теме диссертационной работы опубликовано 47 работ, среди них:

- статьи из ведущих рецензируемых научных журналов и изданий перечня ВАК, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора наук - 9;

- статьи в периодических изданиях СО РАН, СО РАН и РАН ВШ - 9;

- статьи в сборниках СО РАН, в вузовских сборниках и в трудах конференций - 8;

- тезисы докладов в материалах конференций - 21.

Личный вклад автора. Все основные результаты получены автором лично. В совместной работе [93] аспиранткой ОмГТУ Каневой О.Н. разработан алгоритм решения задачи МП с нечеткими исходными данными, в работе [95] аспиранткой ОмГТУ Шамрай Н.Б. разработан проективный метод решения систем неравенств. Указанные результаты соавторов в диссертационную работу не включены.

Введение

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

Особенно эффективно использование параметризации для решения несобственных задач математического программирования (НЗ МП), активное исследование которых ведется в Уральском отделении РАН под руководством академика И.И. Еремина [13-18]. Несобственные задачи в общем случае — это задачи, не обладающие решением в силу тех или иных причин. Для задач МП понятие несобственных задач можно сформулировать более точно: это задачи, не обладающие свойством одновременной разрешимости прямой и двойственной задач и совпадения их оптимальных значений [13, 17]. Простейшим (и одновременно наиболее важным и часто возникающим в прикладных задачах) случаем несобственности задачи МП является несовместность системы ограничений прямой задачи при совместности системы ограничений двойственной задачи. Причем, как только при некотором приращении в правой части система ограничений становится совместной, задача становится разрешимой. Это так называемые несобственные задачи 1-го рода [13, 15, 16].

Параметризация и соответствующая коррекция несобственных задач может осуществляться на основе разных подходов. Один из них состоит в параметризации исходной задачи и поиске параметра у, обеспечивающего разрешимость задачи при найденном значении параметра у. При этом дополнительно можно оптимизировать (по некоторому критерию качества ф(у) ) получаемую в результате коррекцию задачи. В общем случае И.И. Еремин предлагает следующую схему коррекции НЗ МП [13]. Рассматривается НЗ МП в виде

С : inf{/o(z) | Ш < 0,., fm(x) < 0, ж G Rn}. (0.1)

Здесь функции /о, /ь ., fm : Rn —> R в общем случае — выпуклые. Вводится класс параметрических задач

С[у] : inf{/oM(aO I fi[y]{x) < 0,., fm[y](x) < 0, х £ Rn}. (0.2) по параметру у Е U, где U — некоторое конечномерное пространство, причем для некоторого параметра у = уо G Y, Y С [/, выполняется равенство С [у о] = С. Это означает, что одна из задач (0.2) совпадает с исходной задачей (0.1). Пусть а — некоторое свойство задачи (0.2) (к примеру, разрешимость). Определяется множество параметров Ya СУ, для которых задача С [у] обладает свойством и. На множестве Ya определяется функция ф : Ya R1 называемая критерием или функцией качества аппроксимации (коррекции). В результате возникает задача оптимальной аппроксимации (коррекции):

К : min{ф(у) | у G Ya}. (0.3)

Формальный содержательный смысл задачи (0.3) состоит в выборе из множества параметров Ya наилучшего элемента у в смысле некоторого критерия ф{у). Для исходной задачи С (0.1) решение задачи оптимальной коррекции К (0.3) означает следующее: пусть у б АгдК, тогда задача С [у] аппроксимирует исходную задачу С по критерию ф(у).

Таким образом, общая схема использования параметризации для решения НЗ МП (0.1) может быть записана тремя этапами:

0 этап. Для исходной задачи С (0.1) вводится параметризация с параметром у G У. При этом образуется класс параметрических задач С [у] (0.2). Выделяется множество параметров Уа СУ, для которых задача С [у] обладает свойством разрешимости а.

1 этап. Решается задача оптимальной коррекции К (0.3) с критерием ф(у). В результате из класса задач (0.2) выделяется некоторая задача С [у], выступающая в роли аппроксимирующей для исходной задачи С (0.1).

2 этап. Решается аппроксимирующая задача С [у], оптимальное решение которой х* принимается в качестве решения несобственной задачи С (0.1).

В основе рассмотренной коррекции НЗ МП лежит метод штрафных функций, или более общо — метод последовательного программирования [70, 126, 127]. Недостатком такого подхода является то, что хотя несобственная задача С и сводится к разрешимой С [у], но последняя может оказаться некорректной [2, 35, 131]. В связи с этим возникает необходимость в регуляризации несобственных задач [5, 6, 56, 57, 63, 64, 128]. Метод регуляризации, предложенный впервые А.Н. Тихоновым [129], основан на стабилизации задачи при помощи вспомогательного параметрического функционала — регуляризиру-ющего оператора [5, 35]. К другим методам для решения НЗ МП относятся методы итеративной аппроксимации [125], когда коррекция осуществляется одновременно с оптимизацией целевой функции исходной задачи, и методы дискретной аппроксимации [123, 124], использующие комитетные конструкции для решения несобственных задач.

Использование методов коррекции при решении ИЗ МП — это один аспект в исследовании несобственных задач, другой состоит в использовании теории двойственности, разработанной И.И. Ереминым для НЗ МП [17, 71]. С одной стороны, двойственность важна как основа теории МП. С другой стороны, двойственность является источником построения конструктивных численных методов решения задач МП (в частности, решение пары двойственных разрешимых задач можно заменить решением эквивалентной системы неравенств).

Общая схема двойственности для задач математического программирования состоит в сопоставлении исходной задаче другой задачи, формируемой по определенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими [5, 7, 17]: получить оценки эффективности всех параметров, формирующих задачу; свести решение оптимизационной задачи к решению некоторой системы неравенств; сформулировать в изящной и в удобной для использования форме условия оптимальности; найти скорость сходимости итерационных методов решения задачи.

Если задача МП — результат моделирования конкретной экономической (производственной) ситуации, то двойственность и порождаемая двойственностью информация позволяют провести глубокий анализ моделируемой ситуации, выявить узкие места, тенденции изменения модели, выразив эти факторы в количественной форме [14, 16].

Для противоречивых (и, как следствие, неразрешимых) задач роль двойственности возрастает, так как численный анализ таких задач усложняется. Но для неразрешимых задач классическая схема формирования двойственных задач в прежнем виде становится бессодержательной, поскольку оптимальное значение каждой из пары двойственных задач либо отсутствует, либо равно бесконечности. Возникла необходимость расширения понятия двойственности на несобственные задачи. И.И. Еремин предложил следующую схему формирования двойственности для несобственных задач [17, 71].

Несобственной задаче С (0.1) и построенной для нее по классической схеме двойственности несобственной задаче С* по некоторой единой схеме параметризации ставятся в соответствие собственные (разрешимые) задачи D и D& . При этом задачи D и D& выступают в роли аппроксимирующих (в некотором смысле) для задач С и С*. Задачи D и D* построены так, что они связаны между собой следующими свойствами: (D#)# = D, opt D = opt D*. Указанными свойствами обладают и пары двойственных задач в классической схеме двойственности для разрешимых задач.

Таким образом, работа с противоречивыми моделями и несобственными задачами приводит к различным конструкциям, которые связаны с теми или иными видами параметризации и соответствующей коррекцией, приводящими к непротиворечивым собственным моделям. Следует, однако, заметить, что если бы все дело сводилось к корректированию с помощью некоторой параметризации противоречивой модели, к преобразованию ее в непротиворечивую и дальнейшей работе уже с непротиворечивой моделью, то, по существу, не имелось бы никакого принципиально нового момента. Более того, чаще всего содержательный смысл и значение имеет именно исходное противоречивое описание объекта или ситуации, а не получаемые в результате коррекции непротиворечивые модели [12, 14]. С учетом этого в диссертации построена новая конструкция параметризации - обратная дополнительность -основанная на аппарате задач дополнительности. Предлагаемые в диссертации приемы параметризации построены так, что соответствующая коррекция осуществляется одновременно с оптимизацией исходной противоречивой (или несобственной) задачи. При этом вводимая параметризация пригодна и для решения непротиворечивых задач.

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

Одной из первых работ, посвященных теории линейных неравенств, является сборник статей [22]. В работах С.Н.Черникова теория линейных неравенств получила глубокое и всестороннее развитие [37]. В основу теории был заложен принцип граничных решений, который используется при решении вопросов о совместности конечных систем линейных неравенств и о существовании у них решений с теми или иными свойствами. Из принципа граничных решений выводятся все основные теоремы, относящиеся к конечным системам линейных неравенств, и наиболее важные теоремы теории линейного программирования.

Одним из первых методов решения систем линейных неравенств является релаксационный метод Моцкина-Агмона [134, 150], который позволяет находить хотя бы одно решение совместной системы линейных неравенств. В основе метода лежит практически легко реализуемая операция проектирования на полупространства, отвечающие неравенствам системы. Подход к решению систем линейных неравенств, состоящий в последовательном исключении переменных, детально разработан С.Н.

Черниковым [133]. И.И. Еремин распространил метод Моцкина-Агмона на случай системы выпуклых замкнутых множеств [66, 67, 68] и создал релаксационные методы нахождения решений систем линейных и нелинейных неравенств, в основе которых лежат исследования автора по М-фейеровским отображениям и итерационным процессам фейеровского типа [8, 69].

Естественным обобщением развитого А.Н. Тихоновым [130, 132] способа регуляризации для решения систем линейных алгебраических уравнений являются предложенные В.А. Булавским [4, 60, 61, 62] методы стационарной релаксации для решения систем неравенств (в общем случае несовместных). В методах В.А. Булавского параметрическая развязка для несовместности используется путем введения в правую часть подправки, зависящей от параметров. Введение параметрической подправки позволяет, с одной стороны, ввести понятие решения для случая несовместной системы, с другой стороны, разработать достаточно широкий класс методов типа метода последовательных приближений, пригодных для решения как несовместных, так и совместных систем неравенств. Методы стационарной релаксации основаны на использовании аппарата линейных задач дополнительности [137, 139].

Задачи дополнительности интересны прежде всего их приложениями. Это транспортные и экономические задачи, многочисленные задачи из физики. К примеру, равновесие транспортных потоков и модели экономического равновесия, баланса спроса и предложения, задача выбора портфеля ценных бумаг и задачи, возникающие при расчете механических нагрузок на упруго-пластичные конструкции, структурная механика, при исследовании задач которых возникли различные постановки как непараметрических, так и параметрических задач дополнительности [И, 23, 58].

Классическая задача дополнительности состоит в нахождении пары связанных некоторой определенной функциональной зависимостью точек со и у в пространстве Rm, у которых все координаты неотрицательны и в каждой паре соответствующих координат не более, чем одна величина отлична от нуля. Рассмотрим принятые постановки [1, 32, 59, 142, 154] линейных и нелинейных, параметрических и непараметрических, в том числе обобщенных задач дополнительности.

Произвольная нелинейная задача дополнительности NCP(P) состоит в следующем: = Р{у) , и > 0 , у > 0 , (0.4) утсо = 0 , (0.5) где Р : Rm —> Rm — заданное нелинейное отображение, а пара векторов со, у £ Rm определяет решение нелинейной задачи дополнительности (0.4), (0.5). При этом обычно для краткости решением называют вектор у, а нелинейную задачу дополнительности (0.4), (0.5) записывают в более компактной форме

Р(у)> 0, у> 0, (0.6) утР(у) = 0 . (0.7)

Геометрически нелинейная задача дополнительности (0.4), (0.5) (или задача (0.6), (0.7)) состоит в поиске неотрицательного вектора у € К171 такого, что образ Р{у) также неотрицателен и ортогонален вектору у. Содержательно условия (0.5) (или (0.7)) аналогичны условиям дополняющей нежесткости в теории двойственности. Действительно, если неравенства в (0.4) (или в (0.6)) принимать покординатно как сопряженные, то условия (0.5) (или (0.7)) означают, что в каждой паре сопряженных неравенств есть хотя бы одно равенство.

Обобщенная задача дополнительности возникает, когда неравенства в (0.4) рассматриваются в смысле частичной упорядоченности пространства Rm, задаваемой при помощи конуса К С Rm, то есть условие у > 0 заменяется на условие у £ К. Этот конус предполагается замкнутым и выпуклым, имеющим непустую внутренность. Тогда обобщенная задача дополнительности состоит в нахождении таких векторов у, со £ Rm, для которых выполняется ш = Р(у), уек, соеК\ утси = о, (0.8) где К* — сопряженный конус, К* — {си \ утсо >0, V у G К]. Результаты, справедливые для задачи (0.8), являются не слишком сложным обобщением соответствующих результатов для нелинейной задачи дополнительности (0.4), (0.5).

Более существенное обобщение нелинейной задачи дополнительности (0.4), (0.5) состоит в том, что Р : Rm —»■ Rm — многозначное отображение, сопоставляющее каждой точке у G Rm подмножества Р{у) С Rm. Тогда задача дополнительности состоит в нахождении векторов у, со £ Rm, таких что выполняется

W € Р{у) , У> о , w > 0 , утш = 0 . (0.9)

Параметрическое семейство задач по параметру х G Rn для нелинейной задачи дополнительности (0.9) задает параметрическую нелинейную задачу дополнительности вида: со G Р{у, х) , у > 0 , со > 0 , утсо = 0 . (0.10)

Здесь Р : Rm+n —» Rm — многозначное отображение, зависящее от внутренних параметров у G Rm и от внешних параметров х G Rn.

Для нелинейной задачи дополнительности (0.4), (0.5) соответствующая параметрическая нелинейная задача дополнительности будет иметь вид: со = Р{у, х) , ш > 0 , у > 0 , утсо = 0 . (0.11)

Еще одним важным обобщением нелинейной задачи дополнительности (0.4), (0.5) являются вариационные неравенства [21, 32, 42], которые служат удобной общей формой записи многих задач математической физики, а также ценового, транспортного и игрового равновесия и многих других задач [3, 142]. Кроме того, с задачей решения вариационного неравенства тесно связана задача о равновесии, которая является одной из основных задач в теории игр и ее приложениях [10, 24, 27, 112, 113]. Пусть У — непустое подмножество пространства Rm и отображение Р : У —> Rm — в общем случае многозначное. Задача решения вариационного неравенства VI(P, У) состоит в нахождении точек у* е У, таких что выполняется w* G Р(у*) , («Л у-у*)> 0 V у е у • (0.12)

Если отображение Р : У —» Rm — однозначное, то задача нахождения вариационного неравенства VI(P,Y) (0.12) запишется так:

Р{у*), У-У*)> о VyeY. (0.13)

Эквивалентность вариационных неравенств VI (Р: У) и задач дополнительности NCP(P) достигается в следующих случаях [32]:

1. Если У — выпуклый конус, то задача решения вариационного неравенства (0.13) эквивалентна обобщенной задаче дополнительности (0.8).

2. Если выпуклый конус У совпадает с неотрицательным ортантом пространства Rm, то задача решения вариационного неравенства (0.12) эквивалентна обобщенной задаче дополнительности (0.9).

3. Если выпуклый конус У совпадает с неотрицательным ортантом пространства Rm, то задача решения вариационного неравенства (0.13) эквивалентна нелинейной задаче дополнительности (0.4), (0.5).

Линейная задача дополнительности LCP(P, q) состоит в отыскании векторов j/, ш G Rm таких, что выполняются следующие условия: ш = Py-q, ш > 0, у > 0, (0.14) у1 и = 0, (0.15) где Р — матрица размерности т xm, q Е Rm. Вектор q в аффинном отображении ш = и>(у) = Ру — q будем называть вектором правых частей задачи дополнительности (0.14), (0.15), это название связано с несколько другой эквивалентной постановкой LCP(P,q), состоящей в нахождении такого вектора у Е Rm, что выполняются следующие условия:

Ру>4, У> 0, (0.16) уТРу = yTq. (0.17)

В диссертации будем рассматривать линейную задачу дополнительности LCP(P,q) (0.14), (0.15) (или эквивалентную (0.16), (0.17)) и нелинейную задачу дополнительности NCP(P) (или NCP(P,q)), где Р(у) = Р{у) - q, в виде: cu = P(y)-q, у> 0, ути> = 0. (0.18)

Здесь Р : Rm —>• Rm — заданное отображение, вектор q G Rm — заданная правая часть нелинейной задачи дополнительности (0.18) (по аналогии с вектором q в линейной задаче дополнительности LCP(P, q) (0.14), (0.15). В частном случае, когда Р(у) = Ру, где Р — квадратная матрица соответствующего размера, получаем из нелинейной задачи NCP(P,q) (0.18) линейную задачу дополнительности LCP(P,q) (0.14), (0.15).

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

Первую теорему о существовании решений для нелинейной задачи дополнительности NCP(P) (0.4), (0.5) и первый вычислительный метод предложил Коттл [136]. При этом от отображения Р требуется дифференцируемость, и его якобиан VP (у) обладает следующим свойством положительной ограниченности: существует такое 5, 0 < 5 < 1, что для всех у £ Y, УС каждый главный минор матрицы VP (у) лежит между 5 и 1 — 5.

Для применимости метода Коттла делается предположение о невырожденности нелинейной задачи дополнительности NCP(P) (0.4), (0.5). Это означает, что в любом решении со, у Е К171 системы уравнений ш = Р(у) самое большее т из 2т компонентов могут обращаться в нуль. В соотношении со = Р{у) переменные со называются базисными, а переменные у — небазисными. Основной операцией в методе Коттла является обмен местами базисной и небазисной переменных сог, уг, который осуществляется следующим образом. Уравнение сог = Рг(у) (аналог ведущей строки в симплексном методе) разрешается относительно уг. Это всегда можно сделать, так как в силу положительной ограниченности якобиана VP (у) всегда выполняется дРг/дуг > 0 . Полученное выражение подставляется в уравнения coi = Pi(y), г ^ г. Новые базисные переменные для простоты снова обозначаются со, а небазисные у. Получается нелинейная задача дополнительности, в которой вместо Р{у) будет другая функция, скажем Р(у)- Если на очередной итерации получена функция Р(у) > 0, то получено решение задачи дополнительности. Доказано, если задача дополнительности (0.4), (0.5) невырожденная и отображение Р(у) имеет положительный ограниченный якобиан, то метод Коттла находит решение нелинейной задачи дополнительности NCP(P) (0.4), (0.5) за конечное число итераций [136].

Последующие работы в области нелинейных задач дополнительности посвящены выводу более общих теорем существования решения. Первый такой результат получил Карамардиан [144]: если непрерывное отображение Р сильно монотонно, то есть для любых двух точек у1 и у2 выполняются неравенства у2 - у1)т{р{у2) ~ р(у')) > р Из/2 - уЧ2, 0 > о, то существует единственное решение у* нелинейной задачи дополнительности NCP(P) (0.4), (0.5) (или задачи (0.6), (0.7)).

В доказательстве этого результата используется теорема Какутани о неподвижной точке [25].

В дальнейшем при установлении тесной связи решений нелинейной задачи дополнительности с существованием неподвижных точек и с вариационными неравенствами условие сильной монотонности было заменено на другие условия. Это оказалось возможным в силу того, что существование решений для вариационных неравенств (а значит, и для нелинейных задач дополнительности) опирается на факт существования неподвижной точки некоторого отображения, заданного в ограниченной области. Смысл условий состоит в том, чтобы найти такую ограниченную область и чтобы не дать неподвижной точке уйти в бесконечность при неограниченном расширении области (условия коэрцитив-ности) [149]. Несколько более общие условия существования решений нелинейной задачи дополнительности NCP(P) (0.4), (0.5) получил Кодзима [146], но эти условия недостаточно конструктивны. Тем же недостатком обладают полученные в работе [148] условия на функцию Р{у), при которых нелинейная задача дополнительности NCP(P) (0.4), (0.5) с отображением Р(у) = Р{у) — q имеет единственное решение у* = y(q) для любого q.

В диссертационной работе найдены условия для разрешимости нелинейной задачи дополнительности NCP(P), P(y) = P(y) — q, получены и исследованы свойства зависимости y(q), в частности, если q имеет, в свою очередь, некоторую функциональную зависимость q = F(x) [94, 97].

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

Функцию Р называют Р-функцией, если она обладает следующими двумя свойствами:

1) для любых у1, у2, у1 ^ у2 существует номер i = i(y1,y2), такой что выполняется неравенство uf-y}f(Pi(y2)-Pi(y1))>0]

2) для любого подмножества номеров J С {1,., п} и любого заданного вектора ш система уравнений i = Pi(y), Wi = yi, г E {1,. ,n} \ J, (0.19) разрешима относительно параметров у.

Следует заметить, что линейная "Р-функция — это Р-матрица, то есть матрица с положительными главными минорами. В [141] рассмотрен алгоритм, который обобщает алгоритм Мурти [153] для решения линейной задачи дополнительности на случай нелинейных "Р-функций.

Алгоритм состоит в следующем. Произвольным образом выбирается подмножество J0 С {1,. . •, п} . Пусть уже найдено подмножество Jk и ук — решение системы нелинейных уравнений (0.19) при и = 0 и J = Jk. Тогда определяется точка zk из условий: гк = Рг(ук), i Е {I,. ,n}\Jk, zk = yl г G Jk .

Если zk > 0, то решение найдено. В противном случае определяется наименьший индекс г, для которого zk < 0. Если при этом г е Jk, то полагают Jk+1 = Jk \ {г}, а при г ^ Jk полагают Jk+l = Jk U {г}. При практическом применении описанного метода на каждой итерации решается система нелинейных уравнений (0.19). Однако алгоритм использует лишь знаковую структуру решения, поэтому все решения, кроме последнего, могут находиться приближенно. Если Р(у) является ^-функцией, то нелинейная задача дополнительности NCP(P) (0.4), (0.5) имеет единственное решение (при этом непрерывность Р(у) не требуется), и алгоритм Мурти находит решение задачи дополнительности за конечное число итераций [141].

Рассмотрим еще один класс отображений — Л-функции [59].

Функция Р(у) называется Z-функцией, если для у2 > у1, и у2 = у] выполняется неравенство Рг(у2) < Р^у1)) .

Следует заметить, что линейная Л-функция — это Л-матрица, то есть квадратная матрица с неположительными внедиагональными элементами. При этом в случае непрерывности функции Р(у) и непустого множества У = {у\ у > 0, Р(у) > 0} методы решения линейной задачи дополнительности с Л-матрицей переносятся на нелинейный случай.

Исследования, связанные с множеством решений нелинейной задачи дополнительности, показывают, что почти у всех нелинейных задач дополнительности это множество дискретно, а если выполнено некоторое дополнительное условие, то число решений нечетно [155].

Основная теорема в теории линейных задач дополнительности утверждает [41, 143], что задача LCP{P,q) (0.14), (0.15) (или (0.16), (0.17)) имеет единственное решение у £ Rm для любого вектора правых частей q Е Rm тогда и только тогда, когда матрица Р является "Р-матрицей (имеет положительные главные миноры). Утверждение теоремы справедливо для матриц Р с положительно определенной симметризацией |(Р + РТ) [4,62].

Линейная задача дополнительности возникла изначально как задача выпуклого квадратичного программирования (КП) специального вида min{уТ{Ру -q) | Py>q, У > 0 } с нулевым оптимальным значением. Именно этот факт положил начало выделению задач дополнительности в самостоятельный класс [138].

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

Первым методом, предложенным для решения линейной задачи дополнительности, является алгоритм дополнительного ведущего преобразования Лемке [137], являющийся аналогом прямого симплекс-метода для системы уравнений со = Ру + dyo — q, взятой из расширенной задачи дополнительности вида со = Ру + dy0 - q , и> > 0 , 2/0 > о, у> 0, ум = 0, г = 1,. ., ш, где d — произвольный вектор соответствующей размерности (например, d = (1,., 1) ), уо — вспомогательная скалярная переменная, yi, coi — взаимно дополнительные переменные. На первой итерации алгоритма Уг = 0, i — 1,., т, а скалярная переменная > 0 выбирается из следующих условий: coi > 0, для г = 1,. ,т, и для одного номера г £ {1,. , га} выполняется равенство сог — 0. В результате получается начальное базисное решение, в котором базисными переменными являются уо и coi, г = 1,. ,т, кроме сог. На каждой следующей итерации алгоритма одна из небазисных переменных увеличивается (на первой итерации это переменная уг) или неограниченно (в этом случае алгоритм останавливается, не получив решения задачи), или до тех пор, пока одна (в предположении о невырожденности) из базисных переменных не обратится в нуль. В последнем случае на следующей итерации должна увеличиваться переменная, дополнительная к той, которая на предыдущей итерации вышла из базиса. Когда из базиса выводится переменная уо, получается решение задачи дополнительности. Что касается числа итераций в методе Лемке, то известно, что решение задачи линейного программирования с неотрицательной матрицей при помощи метода Лемке в 2-3 раза эффективнее обычного симплекс-метода [59].

Для ^-матриц (с неположительными внедиагональными элементами) метод Лемке работает как обычный симплекс-метод для следующей задачи линейного программирования [152] у0 -> min, Py + dy0-q> 0, у0 > 0, у > 0.

Для Z-матриц с множеством У = {у \ у > 0, Ру — q > 0} ф 0 разработаны достаточно эффективные итерационные методы [23, 58, 135]. Так метод, предложенный в работе [135], находит решение задачи дополнительности не более чем за т шагов. Алгоритм метода состоит в следующем. На первой итерации J1 — пустое подмножество номеров {1 ,.,т}. На к-й итерации находится решение системы уравнений Шг = 0, i е Jk, yi = 0, i ^ Jk, где сOi = (Ру — q)i, после чего образуется новое множество номеров Jh+l = Jk U {г\и>к < 0} и вычисления повторяются.

Для линейной задачи дополнительности LCP(P, q) с "Р-матрицей следует отметить два метода — метод Коттла-Данцига [137] и метод Мурти [153], которые в дальнейшем были обобщены на нелинейную задачу дополнительности. В методе Коттла-Данцига на каждой итерации находятся вектора у и и>, такие что ио = Ру — q, у > 0, и для всех г е {1,., т} выполняются равенства y^i = 0. На первой итерации алгоритма у% = 0, i = 1,. ,т. Вычисления проводятся таким образом, чтобы число отрицательных компонент вектора ио убывало, для этого отрицательная переменная заменяется в базисе ее дополнительной. В методе Мурти на каждой итерации проверяются только условия yiUJi = 0, г = 1,., т.

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

Рассмотрим особенности сведения задач ЛП и задач КП к LCP(P, q) и вытекающие из этих особенностей свойства решений и методов для соответствующих задач LCP(P, q) [32].

Первый класс задач - задача Л П. Пусть прямая задача ЛП состоит в нахождении вектора z и минимума L таких, что

Az>b, z > О, l = cTz. (0.20)

Тогда в двойственной задаче ЛП находится вектор £ и максимум L такие, что

Ат( < с, С > 0, L = ЪТС (0.21)

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

Az - v = b, v > 0, г > 0,

0.22)

АтС + и = с, и> 0, С > 0.

Если прямая и двойственная задачи непротиворечивы, то из теории двойственности ЛП имеем, что min L = maxL, и для оптимальных решений г и С прямой и двойственной задач выполняется bT( = cTz. (0.23)

Далее покажем, что равенство (0.23) эквивалентно условию zTu + (Tv = 0. (0.24)

Действительно, рассмотрим преобразования, используя условия (0.22): сTAz = (T(b+v) = CTb + CTv, CTAz = (с- u)Tz = cTz - uTz.

Тогда

QTb + CTv = cTz - uTz (0.25) и, учитывая (0.23), получаем равенство (0.24). Обратно, пусть справедливо равенство (0.24). Тогда, учитывая справедливость равенства (0.25), получаем условие (0.23). В результате задача ЛП эквивалентна задаче отыскания векторов и, v, z, £ таких, что и > 0, v > 0, > о, С > о, сь: р = ( ~ " I. у = (: I (°-26) устанавливают соответствие между LCP(P1 q) (0.14), (0.15) и задачей ЛП (0.20), (0.21).

Второй класс задач - задача КП. Рассмотрим задачу КП в следующей постановке. Найти вектор -г и минимум С такие, что

Az > b, z> 0, С = cTz + \zTDz . (0.27)

В выпуклой задаче КП (матрица D неотрицательно определена) достаточными условиями для минимума задачи (0.27) являются условия Куна-Таккера г > 0, и > 0, С > 0, v > 0, zTu = 0, C,Tv = 0, или эквивалентно z > 0, и > 0, ( > 0, v > 0, zTu + (Tv — 0, где v — вектор дополнительных переменных для ограничений Az > 6, С и и — вектора множителей Лагранжа для ограничений Az > b и z > 0 соответственно, следовательно, вектора z, и, ( и v связаны равенствами и = Dz — Ат(^ + с, v = Az — b. Таким образом, задача КП сводится к поиску решения системы v = Az-b, z > 0, v > 0, u = Dz-AT£ + c, и> 0, С > 0, (0.28) zTu + (Tv = 0.

Вводя обозначения, аналогичные обозначениям для задачи ЛП, получаем эквивалентность задач (0.28) и LCP (0.14), (0.15).

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

Рассмотрим задачу дополнительности для задачи ЛП. Матрица является сильно коположительной. Действительно, в силу структуры (бисимметричная матрица с нулевыми диагональными блоками) матрица Р является неотрицательно определенной, и следовательно, сильно коположительной. В предположении невырожденности алгоритм дополнительного ведущего преобразования Лемке останавливается за конечное число шагов. Если система уравнений и неравенств (0.22), составленная из ограничений прямой и двойственной задач ЛП (0.20), (0.21), является совместной, то алгоритм Лемке приводит к полному базисному допустимому решению LCP(P,q), и мы получаем в результате решение пары двойственных задач ЛП (0.20), (0.21). Если же система (0.22) несовместна, то получаем пустую допустимую область в прямой и двойственной задачах ЛП (0.20), (0.21), либо в одной из пары двойственных задач, и алгоритм Лемке в этом случае останавливается при нахождении луча.

Рассмотрим разрешимость задачи дополнительности для задачи КП. Матрица является сильно коположительной в силу бисимметричной структуры матрицы Р и неотрицательной определенности матрицы D (для выпуклой задачи КП). А значит, и в этом случае в предположении невырожденности алгоритм дополнительного ведущего преобразования Лемке останавливается за конечное число шагов. Если система неравенств v = Az-b, z > 0, v > О,

0.29) и = Dz- АтС + с, и > 0, С > 0, для задачи КП совместна, то по алгоритму Лемке получаем полное базисное допустимое решение для LCP(P, q) и одновременно решение задачи КП (0.27) и двойственной к ней задачи. В случае остановки алгоритма Лемке при нахождении луча в силу сильной коположительности матрицы Р система неравенств (0.29) для задачи КП несовместна. Если при этом допустимая область задачи КП непустая, то остановка при нахождении луча означает, что оптимальное решение задачи КП неограничено, иначе - допустимая область задачи КП пустая.

Еще один класс задач, исследуемых в диссертации — это обратные задачи. Важность этого класса задач обусловлена тем обстоятельством, что сложные содержательные задачи могут быть записаны как обратные задачи для известных, хорошо изученных классов задач. К примеру, модель экономического равновесия Эрроу-Дебре является обратной (векторной) задачей оптимизации [24, 33].

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

Из определения следует, что имеется некоторый произвол в том, какую из двух задач называть прямой, а какую — обратной. Обычно более простая или лучше изученная задача называется прямой [65]. Исследование и решение обратных задач можно встретить у многих авторов (А.С. Антипин, Я.М.Берщанский, В.П. Булатов, В.В. Васин, Е.Г. Голь-штейн, Л.А. Истомин, И.В. Коннов, Е.С. Левитин и др.).

В работе А.С. Антипина [45] обратная задача формулируется как система различных по природе задач. Так обратная задача выпуклого программирования определяется следующим образом: для заданных скалярной функции f(x,y) и векторной функции Go(x,y), выпуклых относительно переменных х G X, где X — выпуклое множество, и векторных функций G\(x,y) и G2(x,y) требуется определить пару векторов х*,у*, которая удовлетворяет системе, содержащей экстремальное включение, уравнения и (или) неравенства: х* G Argmin{f(x,y*)\G0(x,y*) < 0, я G X], у* G У, (0.30)

Gx(x\y*) = 0, G2{x\y*)< 0. (0.31)

Другими словами, в параметрическом относительно вектора у семействе задач выпуклого программирования (0.30) требуется выбрать параметр у — у* и отвечающий ему оптимум х = х* такие, чтобы выполнялась система уравнений и (или) неравенств (0.31).

У В.П. Булатова [28] в качестве обратной задачи (0.31) выступает параметрическая относительно параметра х оптимизационная задача, внутренним параметром которой является вектор у.

В работе JI.A. Истомина [107] приводится следующая формулировка обратной задачи. Для параметрической относительно вектора у задачи выпуклого математического программирования вида

С[у] : max{f{x,y)\G0(x,y) < 0}, у G У, (0.32) найти такие параметры у G У, для которых двойственные оценки и задачи С [у] (0.32) по некоторому выбранному критерию лучше всего отвечали бы условию у1 = и, где у1 - часть вектора параметров у.

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Зыкина, Анна Владимировна

Заключение

Основные научные результаты

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

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

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

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

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

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

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

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

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

В качестве приложений рассмотрены следующие разработки:

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

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

Использование и дальнейшее развитие результатов исследований

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

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

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

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

- Исследование методов решения задач дополнительности.

- Задача МП для обобщенного решения при ограничениях.

- Алгоритм построения множества обобщенных решений.

- Метод штрафных функций в несобственных задачах МП.

- Задача векторной оптимизации с ограничениями.

Список литературы диссертационного исследования доктор физико-математических наук Зыкина, Анна Владимировна, 2007 год

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

2. Бакушинский А.Б., Гончарский А.В. Итеративные методы решения некорректных задач. М.: Наука, 1989. - 128 с.

3. Байокки К., Капело А. Вариационные и квазивариационные неравенства. Приложение к задачам со свободной границей. М.: Наука, 1988. - 448 с.

4. Булавский В.А. Методы релаксации для систем неравенств. Новосибирск: НГУ, 1981. - 82 с.

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

6. Васильев Ф.П. Численные методы решения экстремальных задач. -М.: Наука, 1988. 552 с.

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

8. Васин В.В., Еремин И.И. Операторы и итерационные процессы фей-еровского типа. Теория и приложения. Екатеринбург: УрО РАН, 2005. - 211 с.

9. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. - 320 с.

10. Голынтейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы оптимизации. М.: Наука, 1989 - 400 с.

11. Дюво Г., Лионе Ж.Л. Неравенства в механике и физике. М.: Наука, 1980. - 383 с.

12. Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. - 288 с.

13. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. - 336 с.

14. Еремин И.И. Противоречивые модели оптимального планирования.- М.: Наука, 1988. 160 с.

15. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. - 248 с.

16. Еремин И.И., Мазуров Вл.Д, Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: УрО РАН, 2000. -280 с.

17. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001. - 180 с.

18. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. -Новосибирск: ИМ СО РАН, 1999. 268 с.

19. Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: АН СССР, 1959. - 344 с.

20. Карманов В.Г. Математическое программирование: учеб. пособие.- 4-е изд., перераб. и доп. М.: ФИЗМАТЛИТ, 2000. - 264 с.

21. Коннов И.В. Методы решения конечномерных вариационных неравенств: курс лекций. Казань: ДАС, 1998. - 101 с.

22. Линейные неравенства и смежные вопросы: сб. под ред. Куна и Таккера. М.: ИЛ, 1959. - 470 с.

23. Мееров М.В., Литвак Б.Л. Оптимизация систем многосвязного управления. М.: Наука, 1972. - 344 с.

24. Методы оптимизации в экономико-математическом моделировании: сб. под ред. Е.Г. Голыптейна. М.: Наука, 1991. - 448 с.

25. Никайдо X. Выпуклые структуры и математическая экономика. -М.: Мир, 1972. 517 с.

26. Нурминский Е.А. Математические основы теории финансовых рынков Владивосток: ДГУ, 2000. - 110 с.

27. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988. - 264 с.

28. Обратные задачи математического программирования. М.: ВЦ РАН, 1992. 155 с.

29. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: МГУ, 1984. - 296 с.

30. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М.: Сов. радио, 1975. - 192 с.

31. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 256 с.

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

33. Приоритетные результаты в области математического программирования. Информац. бюллетень АМП № 9. - Екатеринбург: УрО РАН, 2001. - 143 с.

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

35. Тихонов А.В., Арсенин В.Я. Методы решения некорректных задач.- 2-ое изд., перераб. и доп. М.: Наука, 1979. - 285 с.

36. Урясьев С.П. Адаптивные алгоритмы стохастической оптимизации и теории игр. М.: Наука, 1990. - 184 с.

37. Черников С.Н. Линейные неравенства. М.: Наука, 1968. - 488 с.

38. Ширяев А.Н. Основы стохастической финансовой математики. В 2-х томах. - М.: ФАЗИС, 1998. - Т. 1 - 512 е., т. 2 - 1056 с.

39. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. М.: Радио и связь, 1995. - 504 с.

40. Юдин Д. Б. Математические методы управления в условиях неполной информации. М.: Сов. радио, 1974. - 399 с.

41. Cottle R.W., Pang J.S., Stone R.T. The linear complementarity problem. Boston: Academic press, Inc., 1992.

42. Konnov I.V. Combined relaxation methods for variational inequalities.- Berlin etc.: Springer, 2001. 181 c.1. Статьи

43. Антипин А.С. Экстраполяционные методы вычисления седловой точки функции Лагранжа и их применение к задачам с блочно-сепарабельной структурой // Журнал вычислительной математики и математической физики. 1986. - T.l, № 1.-С. 150-151.

44. Антипин А.С. Методы решения систем задач выпуклого программирования // Журнал вычислительной математики и математической физики. 1987. - Т.27, № 3. - С. 368-376.

45. Антипин А.С. Обратная задача оптимизации: постановка задачи и подходы к ее решению // Обратные задачи математического программирования. М.:ВЦ РАН, 1992.

46. Антипин А.С. Управляемые проксимальные дифференциальные системы для решения седловых задач // Дифференциальные уравнения. 1992. - Т.28, № И. - С. 1846-1861.

47. Антипин А.С. О сходимости и оценках скорости сходимости проксимальных методов к неподвижным точкам экстремальных отображений // Журнал вычислительной математики и математической физики. 1995. - Т.35, № 5. - С. 688-704.

48. Антипин А.С. Вычисление неподвижных точек экстремальных отображений с помощью методов градиентного типа // Журнал вычислительной математики и математической физики. 1997. - Т.37, № 1. - С. 42-53.

49. Антипин А.С. Равновесное программирование: проксимальные методы // Журнал вычислительной математики и математической физики. 1997. - Т.37, № 11. - С. 1327-1339.

50. Антипин А.С. Равновесное программирование: методы градиентного типа // Автоматика и телемеханика. 1997. - № 8. - С. 125-137.

51. Антипин А.С. Решение вариационных неравенств со связанными ограничениями с помощью дифференциальных уравнений // Дифференциальные уравнения. 2000. - Т.36, № 11. - С. 1443-1451.

52. Антипин А.С. Методы решения вариационных неравенств со связанными ограничениями // Журнал вычислительной математики и математической физики. 2000. - Т.40, № 9. - С. 1291-1307.

53. Антипин А.С. О равновесной модели дефицита ресурсов // Нелинейная динамика и управление. 2005. - Вып. 5. - С. 1-9.

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

55. Антипин А.С. Экстрапроксимальный подход к вычислению равновесий в моделях чистого обмена // Журнал вычислительной математики и математической физики. 2006. - Т.46, J№ 10. - С. 17711787.

56. Астафьев Н.Н. Двойственная регуляризация задач линейного программирования, заданных последовательностью реализаций // Журнал вычислительной математики и математической физики. -1978. Т.18, № 5. - С. 1129-1138.

57. Астафьев Н.Н. Двойственная регуляризация задач линейного программирования (общий случай) // Методы оптимизации и распознавания образов в задачах планирования. Свердловск, 1980. - С. 3-12.

58. Беленький В.З. Некоторые модели оптимального планирования, основанные на схеме межотраслевого баланса // Экономика и математические методы. 1967. - Т.З, № 4 - С. 539-549.

59. Берщанский Я.М., Мееров М.В. Теория и методы решения задач дополнительности // Автоматика и телемеханика. 1983. - N2 6. -С. 5-31.

60. Булавский В. А. Релаксация в задачах с неравенствами // Оптимизация. 1979. - Вып. 23(40). - С. 32-40.

61. Булавский В.А. Квазилинейное программирование и векторная оптимизация // Доклады АН СССР. 1981. - Т. 257, № 4. - С. 788-791.

62. Булавский В.А. Обобщенные решения и регуляризация систем неравенств // Вычислительные методы линейной алгебры: труды Интитута математики. 1985. - Т.6. - С. 161-174.

63. Васильев Ф.П. О регуляризации некорректных экстремальных задач // ДАН СССР. 1978. - Т.241, № 5. - С. 1001-1004.

64. Васильев Ф.П. О регуляризации некорректных задач минимизации на множествах, заданных приближенно // ЖВМ и МФ 1980. -Т.20, № 1. - С. 38-50.

65. Голиков А.И. Об одной постановке обратной задачи нелинейного программирования // Обратные задачи математического программирования. М.: ВЦ РАН, 1992.

66. Еремин И.И. Итеративный метод для чебышевских приближений несовместных систем линейных неравенств // ДАН СССР. 1962. -Т. 143, № 6. - С. 1253-1256.

67. Еремин И.И. Релаксационный метод решения систем неравенств с выпуклыми функциями в левых частях // ДАН СССР. 1965. -Т.160, № 5. - С. 994-996.

68. Еремин И.И. Обобщение релаксационного метода Моцкина-Агмона // УМН. 1965. - Т.20, вып.2. - С. 183-187.

69. Еремин И.И. Методы фейеровских приближений в выпуклом программировании // Матем. заметки. 1968. - Т.З, № 2. - С. 217-234.

70. Еремин И.И. О задачах последовательного программирования // Сиб. мат. ж. 1973. - Т. 14, № 1. - С. 53-63.

71. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования // ДАН СССР. 1981. - Т.256, № 2. - С. 272-276.

72. Зыкина А.В Построение обобщенного решения линейной системы неравенств // Оптимизация: сб. науч. трудов. Новосибирск: ИМ СО АН СССР, 1988. - Вып.43(60). - С. 11-25.

73. Зыкина А.В. Параметризация в несобственных задачах линейного программирования // Дискретная оптимизация и анализ сложныхсистем: сб. науч. трудов. Новосибирск: ВЦ СО АН СССР, 1989. -С. 56-61.

74. Зыкина А.В. Анализ решения в противоречивых моделях оптимального планирования // Динамика систем, механизмов и машин: материалы II Междунар. науч.-техн. конф. Омск: ОмГТУ, 1997. -Кн.З. - С. 33.

75. Зыкина А.В. Обобщенное решение в линейной векторной оптимизации // Междунар. Сибирская конф. по исследованию операций. -Новосибирск: ИМ СО РАН, 1998. С. 82.

76. Зыкина А.В. Обобщенный подход для решения линейных многокритериальных задач // Математическое программирование и приложения: информац. бюллетень АМП JV2 8. Екатеринбург: УрО РАН,1999. - С. 124-125.

77. Зыкина А.В., Пригнец О.Н. Несобственная задача стохастического программирования // Математическое программирование и приложения: информац. бюллетень АМП № 8. Екатеринбург: УрО РАН,1999. - С. 126.

78. Зыкина А.В. Об обобщенном решении в векторной оптимизации // Динамика систем, механизмов и машин: материалы III Междунар. науч.-техн. конф. Омск: ОмГТУ, 1999. - Кн. 2. - С. 344-345.

79. Зыкина А.В. О вариационном подходе к решению задачи математического программирования // Алгебра, геометрия, анализ и математическая физика: труды XII Сибирской школы. Новосибирск: ИМ СО РАН, 1999. - С. 68-73.

80. Зыкина А.В. Обобщенный подход для решения линейных векторных задач // Доклады СО АН ВШ. 2000. - № 2. - С. 16-22.

81. Зыкина А.В. О реализации метода взвешенных сумм // Моделирование неравновесных систем 2000: материалы III Всерос. семинара.- Красноярск: ИПЦ КГТУ, 2000. С. 98.

82. Зыкина А.В. Параметрическое обобщенное решение в линейной векторной оптимизации // Кибернетика и системный анализ. 2001.1. С. 177-181.

83. Зыкина А.В. Анализ решений в противоречивых моделях оптимального планирования // Доклады СО АН ВШ. 2001. - № 1(3). -С. 11-16.

84. Зыкина А.В. Обобщенное решение при ограничениях // Математическое программирование: труды XII Байкальской междунар. конф. "Методы оптимизации и их приложения". Иркутск: ИСЭМ СО РАН, 2001. - Том 1. - С. 324-329.

85. Зыкина А.В. Проблемы численной реализации алгоритма нахождения обобщенного решения // Дискретный анализ и исследование операций: материалы Росс. конф. Новосибирск: ИМ СО РАН, 2002.- С. 166.

86. Зыкина А.В. Обобщенное решение в методе последовательных уступок // Динамика систем, механизмов и машин: материалы IV Междунар. науч.-техн. конф., посвященной 60-летию ОмГТУ. -Омск: ОмГТУ, 2002. Кн. 2. - С. 165-166.

87. Зыкина А.В. О реализации метода последовательных уступок // Математическое программирование и приложения: информац. бюллетень АМП № 10. Екатеринбург: УрО РАН, 2003. - С. 119.

88. Зыкина А.В. Эффективность обобщенных решений в многокритериальной оптимизации // Проблемы оптимизации и экономические