Введение к работе
Актуальность темы диссертационного исследования обусловлена сложностью задач системного анализа и управления, возникающих при исследовании структур разной природы (организационных, технических, экономичиских, социально-экономических и др ) Для таких задач характерно принятие человеком оценочных и управленческих решений на основе компьютерного расчета равновесных или оптимальных с точки зрения того или иного критерия ситуаций в экономико-математических моделях
Особенную важность задачи системного анализа приобретают при разработке инновационных программ На современном этапе развития общества способность к эффективной инновационной деятелбности является определяющей для жизнеспособности экономики Реализация инновационного проекта проходит в условиях высокого риска и неопределенности, поэтому для лица, принимающего решение, важны максимально точные оценки Эти оченки могут быть получены за счет использования нелинейных критериальных функций и рассмотрения моделей высокой размерности
С математической точки зрения подобный подход приводит к двум основным задачам поиску приближений равновесных точек, который сводится к поиску приближенного решения систем уравнений, и поиску приближений оптимальных точек Таким образом, успешное применение методов системного анализа требует разработки эффективных методов решения нелинейных систем уравнений и задач нелинейной оптимизации на множестве С, которое обычно считается заданным линейными ограничениями, при минимуме требований на критериальные функции В общем случае, эти задачи известны как задачи отыскания решения вариационного неравенства Само решение вариационного неравенства называется стационарной точкой
Ряд методов решения указанных задач при различных условиях описан, например, в работах Б Т Поляка, Ф П Васильева и А С Антипина Однако эти методы предполагают, как правило, выпуклость функций и множеств В настоящей работе решение данной проблемы исследуется без предположения о выпуклости функций Для этого используется идея перебора симплексов, во многом похожая на идею симплициального поиска минимума функции, развитую в работах А П Дамбраускаса п А С Рыкова
Конструктивная недостаточность известных методов состоит в том, что они или являются слишком требовательными к целевым функциям или не являются глобально сходяндимимся Помимо этого, с вычислительной точки зрения, сходимость таких методов при больших размерностях задачи является достаточно
медленной Устранение этих недостатков является крайне актуальным для решения задач системного анализа Это определило выбор темы исследования В качестве альтернативы известным методам выбрана версия методов неподвижных точек известная как симлициальные целочислеппые рестарт-алгоритмы переменной размерности
Целями исследования являются
построение универсальных целочисленных алгоритмов поиска стационарных точек,
построение симплициальных рестрат-алгоритмов переменной размерности, которые использовали бы в своей работе симплексы малой размерности, реализующие траектории приближенные к кусочно-линейным,
построение симплипиальных рестарт-алгоритмов поиска стационарной точки на произвольном множестве, заданном ограничениями Ах ^ Ь
тестирование построенных алгоритмов
Для достижения указанных целей были поставлены и решены следующие основные задачи
анализ существующих целочисленных рестарт-алгоритмов с целью выявления взаимодействия их основных компонент ,
анализ основных принципов построения триангуляции, которые используются в алгоритмах поиска неподвижных точек,
исследование конструктивных различий целочисленных и векторных алгоритмов ,
разработка общей схемы целочисленного алгоритма на произвольном ограниченном многограннике,
применение общей схемы для построения высокоэффективных целочисленных алгоритмов поиска стационарных точек на Hd ,
исследование области применимости общей схемы,
применение общей схемы для построения высокоэффективных целочисленных алгоритмов поиска стационарных точек на множестве, заданном ограничениями вида Ах ^ Ь,
экспериментальное сравнение существующих и вновь построенных алгоритмов
Объектом исследования являются алгоритмы поиска стационарных точек Предмет исследования- симплшгиальные целочисленные рестарт-алгоритмы переменной размерности
Информационная база исследования включает базы данных, анализ литературных источников, данные численного тестирования ряда алгоритмов поиска
неподвижных точек, опубликованные в журнале 'Математическое программирование'
Методологической и теоретической основой исследования являлся системный подход в сочетании с дедуктивным и индуктивным методами научного познания При решении конкретных задач широко использовались методы теории многогранников, комбинаторики, линейной алгебры
Наиболее существенные результаты и научная новизна диссертационной работы состоят в разработке новых методов вычисления стационарных точек нелинейных функций на множествах, заданных линейными ограничениями На основе диссертационных исследований построены три таких метода
1 Построен 2d целочисленный алгоритм для нахождения стационарных то
чек на R , являющийся аналогом классического векторного алгоритма Райта
- одного из самых высокоэффективных векторных алгоритмов
2 Построен 3d — 1 целочисленный ачгоритм для нахождения стационарных
точек на Rd, являющийся аналогом векторного алгоритма Коджимы и Ямамото
- самого многолучевого из всех существующих алгоритмов
3 Построен целочисленный алгоритм для поиска стационарных точек на
произвольном множестве, заданном ограничениями вида Ах ^ 6, являющийся
аналогом векторного алгоритма Тальмана и Ямамото
Для каждого из этих методов разработаны программные пакеты на языке C++ Для алгоритма 3 такой пакет написан впервые, а пакеты для алгоритмов 1 и 2 оказывается гораздо быстрее своих предшественников и впервые демонстрируют возиожность эффективно работать на задачах, размерность которых исчисляется тысячами переменных
Теоретическая значимость исследования состоит в том, что его ходе получены следующие результаты
предложен новый способ триангуляции пространства и многогранника,
применено новое индуктивное описание использующейся в исследовании триангуляции Куна,
обобщено понятие аппроксимации, использующееся в существующих целочисленных алгоритмах,
введено понятие сильной и слабой аппроксимации, необходимое для построения новых алгоритмов,
описан общий способ построения алгоритма по произвольному наперед заданному многограннику
построен критерий существования многогранника, порождающего заданное разбиение пространства на многогранные конусы,
построена 'регулярная триангуляция' куба,
построена 'регулярная триангуляция' октаэдра,
9 обоснована интерпретация целочисленного алгоритма для поиска стационарных точек на многограннике как обобщения симплекс-метода, 10 доказана сходимость квазиградиентного метода к равповесию по Нэшу в модели рыночного ценообразования
Практическая значимость исследования состоит в том, что предложенные в нем методы поиска стационарных точек являются по результатам численного тестирования высокоэффективными и, следовательно, пригодными для решения практических задач, в том числе задач, возникающих в области экономического моделирования и характеризующихся большой размерностью
Апробация результатов исследования Работа обсуждалась на научных семинарах специализации 'Теоретические и прикладные проблемы инноваций' кафедры общей экономики МФТИ, кафедры высшей математики МФТИ, отдела теории автоматического управления ИПУ РАН, отдела прикладных проблем оптимизации ВЦ РАН, лаборатории теории и численных методов оптимизации ЦЭМИ РАН, направления математических основ информатики, управления и системного анализа ИСА РАН, кафедры оптимального управления факультета ВМК МГУ Основные результаты диссертации опубликованы в 4-х печатных работах
Похожие диссертации на Решение вариационного неравенства алгоритмами неподвижных точек
