Кандаминимум 010109 - ответы основной специальности — различия между версиями

Версия 00:19, 24 ноября 2009

Математическое программирование

По большей части берётся из лекций по МетОптам: Лекции по методам оптимизации 2003.pdf (application/pdf, 745 КБ). Другие источники описаны отдельно.

Теоремы о достижении нижней грани функции (функционала) на множестве (в Е^N, в метрических пространствах, в гильбертовых пространствах)

Они же Теоремы Вейерштрасса.

• Полунепрерывная снизу J(u) на компакте в метрическом пространстве достигает своей нижней грани, любая минимальная последовательность сходится к argmin по метрике.
• Слабый вариант. Гильбертово пространство, компакт слабый, п/н слабо. Слабые п.т. мин. последовательности в Argmin.

Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства

• Опр. множество выпуклое; функция выпуклая, строго выпуклая, сильно выпуклая с k > 0.
• Т. лок.мин. выпуклой f на выпуклом U = глобальный на U. Argmin выпукло. Argmin={argmin} для строго выпуклой.
• Т. (сильно вып. Вейерштрасса) J(u) сильно выпукла и п.н. снизу на выпуклом и замкнутом U из Гильбертова H ⇒ достигает inf, Argmin={argmin}, .
• Т. (критерий вып. для диф-мых функций).
• Т. (критерий сильной вып. для диф-мых функций).

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

• Т. , U выпукло ⇒ (1), . Если (1) и J(u) выпукла — значит u argmin (то есть ⇐).
• Ещё там есть пара примеров.

Правило множителей Лагранжа

• rupedia:Метод множителей Лагранжа относится к методам снятия ограничений.
• Задача. J(u) → min при огр. g_i ≤ 0.
• А мы будем минимизировать L(u,λ) = λ₀J(u) + сумма λ_ig_i, λ_i — множители Лагранжа.

Теорема Куна-Таккера, двойственная задача, ее свойства

• Т. (Куна-Таккера) (обоснование метода Лагранжа) — всё существует, λ_i неотрицательно, λ_ig_i=0 (усл.доп.нежёсткости). Для достаточности ещё λ_i ≠ 0.
• Опр. Двойственная задача:
• Т. (свойства дв.задачи). . = только если L имеет седловую точку.

Метод проекции градиента (в Е^N, в гильбертовом пространстве)

• Условный минимум — минимизируем J(u) на множестве U. В лоб — метод град. спуска проецируем на U = pr_U(u_k-a_kJ'(u_k)).
• Т. (скорость сходимости)

Метод Ньютона

• Идея — градиентный (или скорейший) спуск по квадратичной аппроксимации функции J(u) в окрестности u_k.
• Т. (скорость сходимости)

Метод покоординатного спуска

• Сдвигаемся на a_k в одну из сторон по одной координате по очереди, пока удаётся. Потом переходим к следующей. Потом дробим a.
• Т. (обоснование сходимости)

Метод штрафных функций

• Можно также почитать mlwiki:Метод штрафных функций.
• Относится к методам снятия ограничений.
• Задача. J(u) → min при огр. g_i ≤ 0 либо = 0 начиная с g_m+1-ой.
• От задачи переходим к последовательности задач . P(u) — штраф, .
• Т. (обоснование) индив. штрафы должны давать огран. множество ⇒ всё сходится.

Метод барьерных функций

• Можно почитать mlwiki:Метод штрафных функций#Метод барьерных функций.
• По сути то же, что и метод штрафных функций, только штраф другого вида.

Метод динамического программирования

• Нет в МетОптах.
• Можно почитать книжку Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu (image/vnd.djvu, 5,6 МБ), страницы 461—464.
• Или просто Википедию.
• Идея — поиск пути по минному полю с конца к началу, ибо любой конец оптимальной траектории оптимален (принцип оптимальности Беллмана).
• Вообще-то ещё есть непрерывный аналог, идея та же, реализация на дифф.исчислении и ощутимо мохнатее.

Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову)

• Опр. корректно пост.задача: 1) существует, 2) единственно, 3) из сходимости значений следует сходимость аргументов.
• Суть метода — в отсутствие (3) добавить к J(u) и минимизировать полученный функционал Тихонова.
• Т. (обоснование метода).

Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования

• Опр. ЗЛП, каноническая ЗЛП (u ≥ 0), угловая точка, невырожденная угловая точка, невырожденная задача.
• Т. (критерий угловой точки) (про линейную комбинацию r столбцов матрицы A)
• Симплекс-метод — идея перебора угловых точек в направлении минимизации функции.

Исследование операций, теория игр

Источники — две книжки по тиграм (теории игр) Васина и Морозова:

1. А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu (image/vnd.djvu, 1,16 МБ)
2. Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu (image/vnd.djvu, 248 КБ) (только 5-я глава).

Антагонистические игры. Матричные игры, теорема о минимаксе

• Опр. седловая точка F(x, y); антаг. игра <X,Y,F(x,y)>; игра имеет решение; значение игры; матричная игра; нижнее и верхнее значения игры (sup inf и inf sup); максиминная, минимаксная стратегии.
• Л. значение игры не зависит от выбора решения.
• Л. нижнее значение ≤ верхнего.
• Т. (о минимаксе) 1) есть с.т. ⇔ max inf = min sup. 2) с.т. = стратегии максиминная и минимаксная.

Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки

• Опр. игра с вогнутой, выпуклой функцией выигрыша.
• Т.
• Т. (существование решения)

Бескоалиционные игры n лиц. Равновесие по Нэшу

• Опр. игра n лиц.
• Опр. (равновесие по Нэшу) от него никому невыгодно отклоняться в одиночку.
• Т. (существования равновесия)

Принцип гарантированного результата. Минимаксные задачи

• Из книжки 2.
• Можно почитать http://www.intuit.ru/department/algorithms/opres/2/.
• Опр. оптимальная стратегия (в предположении пессимизма) (так Гермейер стратегии сравнивал); ε-оптимальная стратегия, абсолютно оптимальная стратегия.
• Т. F1 ≤ F2 ≤ F3 ≤ F4. Противник знает x → не знает → мы знаем y.

Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход

• Из книжки 2.
• Многокритериальная оптимизация — как выбрать стратегию, если критериев качества несколько?
• Опт. по Парето = «не улучшишь хотя бы один критерий».
• Опт. по Слейтеру = «не улучшишь все критерии разом».
• Лексикографический подход — упорядочиваем их по важности и ORDER BY.

Кооперативные игры (с-ядро, вектор Шепли)

• Игроки делят выручку.
• Опр. коалиции, хар.функция, супераддитивная, игра, игра с постоянной суммой, вектор дележа, эквив. игры (масштаб-сдвиг), 0-1 редуц. форма игры.
• Индивидуальная разумность — выручку в коалиции не меньше, чем индивидуальная игрока.
• Групповая разумность — выручка любой подкоалиации не меньше, чем её индивидуальная.
• Ядро (c-ядро) — дележи, удовлетворяющие групповой разумности.
• Вектор Шепли — состоит из компонент, равных мат.ожиданиям вкладов конкретных игроков.

Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера)

• Из книжки 2.
• Задача 1: максимизируем минимум эффекта по всем пунктам.
• Т. (пр. ур. Гермейера) оптимальное решение существует и единственно — идея: вначале распределяем ресурсы по наиболее слабым пунктам так, чтобы эффекта им досталось поровну.
• Задача 2: максимизируем сумму эффекта по всем пунктам.
• Т. (критерий Гросса) аналог уравнивания для производных.

Иерархические игры

• Опр. иерархической игры (есть обмен информацией о стратегиях).
• Г₁: x → y(x) — Y знает стратегию X.
• Г₂: f(y) → y(f(y)) → x=f(y).
• Г₃: f₁(g(x)) → g(x) → x=f(g(x)).
• Т. (Гермейера). В Г₂ гарантированный результат игрока X = максимум из 1) гарантированного результата X при наилучшем ответе Y на стратегию наказания, применяемую к нему X и 2) лучшего результата X в случае, если он позволит Y получить больше, чем в первом случае.

Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача)

• В книжках нет.
• Можно почитать rupedia:Теорема Форда — Фалкерсона, rupedia:Транспортная задача, rupedia:Алгоритм Дейкстры.
• Опр. транспортная сеть, поток, сечение графа, величина сечения.
• Т. (Ф-Ф, очевидная — «пропускная способность определяется слабым звеном») максимальный поток между истоком и стоком равен величине минимального сечения.
• Решение транспортной задачи аналогично Ф-Ф.
• Поиск кратчайшего пути — динамическое программирование, алгоритм Дейкстры (жадный).

Оптимальное управление

1. Постановка задач оптимального управления, их классификация.
2. Принцип максимума Понтрягина. Краевая задача принципа максимума.
3. Линейная задача быстродействия, ее свойства (существование решения, число переключений).
4. Принцип максимума и вариационное исчисление.
5. Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.
6. Метод динамической регуляризации в задаче наблюдения.
7. Дифференциальные игры.

Дискретная оптимизация

1. Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений).
2. Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).
3. Временная сложность решения задач дискретной оптимизации. Основные классы сложности (P, NP, NPC).
4. NP-трудные задачи (задача о рюкзаке, задача коммивояжера).

Теория функциональных систем

1. Проблема полноты. Теорема о полноте систем функций двузначной логики P₂.
2. Алгоритм распознавания полноты систем функций k-значной логики P_k.
3. Теорема Слупецкого.
4. Особенности k-значных логик.
5. Автоматы. Регулярные события и их представление в автоматах.
6. Эксперименты с автоматами.
7. Алгоритмическая неразрешимость проблемы полноты для автоматов.
8. Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.
9. Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.

Комбинаторный анализ и теория графов

1. Основные комбинаторные числа.
2. Оценки и асимптотики для комбинаторных чисел.
3. Графы и сети. Оценки числа графов и сетей различных типов.
4. Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности).
5. Экстремальная теория графов. Теорема Турана.
6. Теорема Рамсея.

Теория кодирования

1. Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана.
2. Оптимальное кодирование. Построение кодов с минимальной избыточностью.
3. Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку.
4. Конечные поля и их основные свойства.
5. Коды Боуза—Чоудхури—Хоквингема.

Управляющие системы

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

Дизъюнктивные нормальные формы

1. Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.
2. Локальные алгоритмы построения ДНФ. Построение ДНФ ∑Т (сумма тупиковых) с помощью локального алгоритма.
3. Невозможность построения ДНФ ∑М (сумма минимальных) в классе локальных алгоритмов.

Синтез и сложность управляющих систем

1. Асимптотически оптимальный метод синтеза схем из функциональных элементов.
2. Асимптотически оптимальный метод синтеза контактных схем.
3. Инвариантные классы и их свойства.
4. Синтез схем для функций из некоторых инвариантных классов.
5. Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами.
6. Нижние оценки сложности реализации булевых функций формулами в произвольном базисе.

Эквивалентные преобразования управляющих систем

1. Эквивалентные преобразования формул двузначной логики Р₂.
2. Эквивалентные преобразования контактных схем.
3. Эквивалентные преобразования операторных алгоритмов.
4. Пример Линдона.

Надежность и контроль функционирования управляющих систем

1. Построение надежных контактных схем из ненадежных контактов.
2. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.

Математическая экономика

1. Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
2. Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
3. Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования.
4. Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона.
5. Модель олигополистической конкуренции Курно. Теорема Нэша.
6. Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре.
7. Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы.
8. Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия.
9. Проблемы коллективного выбора. Парадокс Эрроу.
10. Индексы неравенства и кривая Лоренца. Теорема мажоризации.

Основная литература

1. Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2001.
2. Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
3. Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
4. Оре О. Теория графов. М.: Наука, 1980.
5. Кибернетический сборник. 1960—1990. Вып. 1—9; вып. 1—28 (новая серия). М.: Мир.
6. Дискретная математика и математические вопросы кибернетики. Т. 1. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.
7. Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.
8. Проблемы кибернетики. 1959—1984. Вып. 1—41. М.: Наука.
9. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990.
10. Труды Математического института им. В. А. Стеклова. Т. 51. М.: Изд-во АН СССР, 1958.
11. Математические вопросы кибернетики. 1988—2001. Вып. 1—10. М.: Наука.
12. Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1969.
13. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986.
14. Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002.
15. Карманов В. Г. Математическое программирование. М.: Наука, 2000.
16. Понтрягин Л. Избранные научные труды. Т. 2. М.: Наука, 1988.
17. Тихомиров В. М., Фомин С. В., Алексеев В. М. Оптимальное управление. М.: Наука, 1979.
18. Краснощеков П. С., Петров А. А. Принципы построения моделей. М.: Фазис, 2002.
19. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.
20. Морозов В. В. Основы теории игр. М.: Изд-во МГУ, 2002.
21. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Наука, 198 .
22. Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972.
23. Ашманов С. А. Введение в математическую экономику. М.: Наука, 1984.
24. Экланд И. Элементы математической экономики. М.: Мир, 1983.
25. Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.
26. Маршалл А., Олкин И. Неравенства, теория мажоризации и ее приложения. М.: Мир, 1983.
27. Мельников А. В. Стохастический анализ и расчет производных ценных бумаг. М.: ТВП, 1997.

Дополнительная литература

1. МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
2. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
3. Сэведж Дж. Э. Сложность вычислений. М.: Факториал, 1998.
4. Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.
5. Орлов В. А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов. //Кибернетика. 1973. № 4. С. 109—113.
6. Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.
7. Соловьев Н. А. Тесты (теория, построение, применения). Новосибирск: Наука, 1978.
8. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1984.