Параметризация и обратная дополнительность в моделировании и решении оптимизационных задач

• Автор: Зыкина, Анна Владимировна
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2007
• Место защиты: Омск
• Количество страниц: 296 с. : ил.

Содержание
Предисловие
Введение

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СР(Р, <у) (0. МСР(Р) (или Л^Р(Р, с/)), где Р{у) = Р(у) - 0, у > 0, уг^ = 0. РСР(Р, су) (0. В частном случае, когда Р(у) = Р? Р - квадратная матрица соответствующего размера, получаем из нелинейной задачи 1ТСР(Р,) (0. ЬСР(Р>д) (0. Теоремы о существовании решений для нелинейной задачи дополнительности получают, как правило, из теорем о существовании решений для вариационных неравенств и эти теоремы используют ту или иную форму монотонности отображения Р. Первую теорему о существовании решений для нелинейной задачи дополнительности NCP{P) (0. Коттл [6]. У, У Я Я™, каждый главный минор матрицы 7Р(у) лежит между 6 и 1-6. Для применимости метода Коттла делается предположение о невырожденности нелинейной задачи дополнительности ЛГСР(Р) (0. Это означает, что в любом решении ад у € Я! Р(у) самое большее т из 2т компонентов могут обращаться в нуль. В соотношении и) = Р(у) переменные о> называются базисными, а переменные у - небазисными. Основной операцией в методе Коттла является обмен местами базисной и небазисной переменных о>г, уТ, который осуществляется следующим образом. Уравнение о>г — Рт(у) (аналог ведущей строки в симплексном методе) разрешается относительно уг. Это всегда можно сделать, так как в силу положительной ограниченности якобиана VР(у) всегда выполняется дРг/дуг > 0 . Полученное выражение подставляется в уравнения ад = Р,;(;у), г ф т. Новые базисные переменные для простоты снова обозначаются ад а небазисные у. Р(у) будет другая функция, скажем Р(у). Если на очередной итерации получена функция Р(у) > 0, то получено решение задачи дополнительности. Доказано, если задача дополнительности (0. Р(у) имеет положительный ограниченный якобиан, то метод Коттла находит решение нелинейной задачи дополнительности УСР(Р) (0. Последующие работы в области нелинейных задач дополнительности посвящены выводу' более общих теорем существования решения. Р(у')) > ? Иг/2 - у1 f. NCP(P) (0. В доказательстве этого результата используется теорема Какутани о неподвижной точке []. В дальнейшем при установлении тесной связи решений нелинейной задачи дополнительности с существованием неподвижных точек и с вариационными неравенствами условие сильной монотонности было заменено на другие условия. Это оказалось возможным в силу того, что существование решений для вариационных неравенств (а значит, и для нелинейных задач дополиительности) опирается на факт существования неподвижной точки некоторого отображения, заданного в ограниченной области. Смысл условий состоит в том, чтобы найти такую ограниченную область и чтобы не дать неподвижной точке уйти в бесконечность при неограниченном расширении области (условия коэрцитив-ности) [9]. Несколько более общие условия существования решений нелинейной задачи дополнительности NCP(P) (0. Кодзима [6], но эти условия недостаточно конструктивны. Тем же недостатком обладают полученные в работе [8] условия на функцию Р(у)} при которых нелинейная задача дополнительности NCP(P) (0. Р(у) = Р(у) - q имеет единственное решение у* = y(q) для любого q. NCP(P), Р(у) = P(y) — q, получены и исследованы свойства зависимости y(q), в частности, если q имеет, в свою очередь, некоторую функциональную зависимость q = Р{х) [, ]. С {1,. Р<(у), ге,/, и, = уь г 6 {1,. Следует заметить, что линейная Р-функция - это Р-матрица, то есть матрица с положительными главными минорами. В [1] рассмотрен алгоритм, который обобщает алгоритм Мурти [3] для решения линейной задачи дополнительности на случай нелинейных Р-функций. Алгоритм состоит в следующем. Произвольным образом выбирается подмножество . С {1, -, п} . Пусть уже найдено подмножество ^ и ук — решение системы нелинейных уравнений (0. Рг(ук), ie{l,. Jk, г? Если гк > 0, то решение найдено. В противном случае определяется наименьший индекс г, для которого гк < 0. Если при этом г 6 «/*, то полагают ,]м =