13 513
правок
Изменения
Нет описания правки
По большей части берётся из лекций по МетОптам: {{Скачать|Лекции по методам оптимизации 2003.pdf}}. Другие источники описаны отдельно.
==== Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е<sup>N</sup>'', в метрических пространствах, в гильбертовых пространствах) ====
Они же Теоремы Вейерштрасса.
* Слабый вариант. Гильбертово пространство, компакт слабый, п/н слабо. Слабые п.т. мин. последовательности в Argmin.
==== Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства ====
* '''Опр.''' множество выпуклое; функция выпуклая, строго выпуклая, сильно выпуклая с k > 0.
* '''Т.''' (критерий сильной вып. для диф-мых функций).
==== Критерии оптимальности в гладких выпуклых задачах минимизации ====
* '''Т.''' <m>J(u) \in C^1(U)</m>, U выпукло ⇒ <m>(J'(u_*), u-u_*) >= 0</m> (1), <m>J'(u_* \in int U) = 0</m>. Если (1) и J(u) выпукла — значит u argmin (то есть ⇐).
* Ещё там есть пара примеров.
==== Правило множителей Лагранжа ====
* [[rupedia:Метод множителей Лагранжа]] относится к методам снятия ограничений.
* А мы будем минимизировать L(u,λ) = λ<sub>0</sub>J(u) + сумма λ<sub>i</sub>g<sub>i</sub>, λ<sub>i</sub> — множители Лагранжа.
==== Теорема Куна-Таккера, двойственная задача, ее свойства ====
* '''Т.''' (Куна-Таккера) (обоснование метода Лагранжа) — всё существует, λ<sub>i</sub> неотрицательно, λ<sub>i</sub>g<sub>i</sub>=0 (усл.доп.нежёсткости). Для достаточности ещё λ<sub>i</sub> ≠ 0.
* '''Т.''' (свойства дв.задачи). <m>\psi \le \psi^* \le \phi_* = J_* \le \phi(u)</m>. '''=''' только если L имеет седловую точку.
==== Метод проекции градиента (в ''Е<sup>N</sup>'', в гильбертовом пространстве) ====
* Условный минимум — минимизируем J(u) на множестве U. В лоб — метод град. спуска проецируем на U = pr<sub>U</sub>(u<sub>k</sub>-a<sub>k</sub>J'(u<sub>k</sub>)).
* '''Т.''' (скорость сходимости) <m>\le |u_0 — u_*|_H q^k(\alpha), q(\alpha) = \sqrt{1-2k\alpha+\alpha² L²}</m>
==== Метод Ньютона ====
* Идея — градиентный (или скорейший) спуск по квадратичной аппроксимации функции J(u) в окрестности u<sub>k</sub>.
* '''Т.''' (скорость сходимости) <m>\le \frac{2k}{L}q^{2^k}(1-q^{2^k})^{-1}</m>
==== Метод покоординатного спуска ====
* Сдвигаемся на a<sub>k</sub> в одну из сторон по одной координате по очереди, пока удаётся. Потом переходим к следующей. Потом дробим a.
* '''Т.''' (обоснование сходимости)
==== Метод штрафных функций ====
* Можно также почитать [[mlwiki:Метод штрафных функций]].
* '''Т.''' (обоснование) индив. штрафы должны давать огран. множество ⇒ всё сходится.
==== Метод барьерных функций ====
* Можно почитать [[mlwiki:Метод штрафных функций#Метод барьерных функций]].
* По сути то же, что и метод штрафных функций, только штраф другого вида.
==== Метод динамического программирования ====
* Нет в МетОптах.
* Вообще-то ещё есть непрерывный аналог, идея та же, реализация на дифф.исчислении и ощутимо мохнатее.
==== Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову) ====
* '''Опр.''' корректно пост.задача: 1) существует, 2) единственно, 3) из сходимости значений следует сходимость аргументов.
* '''Т.''' (обоснование метода).
==== Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования ====
* '''Опр.''' ЗЛП, каноническая ЗЛП (u ≥ 0), угловая точка, невырожденная угловая точка, невырожденная задача.
# {{Скачать|Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu}} (только 5-я глава).
==== Антагонистические игры. Матричные игры, теорема о минимаксе ====
* '''Опр.''' седловая точка F(x, y); антаг. игра <tt><X,Y,F(x,y)></tt>; игра имеет решение; значение игры; матричная игра; нижнее и верхнее значения игры (sup inf и inf sup); максиминная, минимаксная стратегии.
* '''Т.''' (о минимаксе) 1) есть с.т. ⇔ max inf = min sup. 2) с.т. = стратегии максиминная и минимаксная.
==== Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки ====
* '''Опр.''' игра с вогнутой, выпуклой функцией выигрыша.
* '''Т.''' (существование решения) <m>x^0 \in X, \psi^0 = \sum_1^{m+1} q_j^0 I_y_j</m>
==== Бескоалиционные игры ''n'' лиц. Равновесие по Нэшу ====
* '''Опр.''' игра n лиц.
* '''Т.''' (существования равновесия)
==== Принцип гарантированного результата. Минимаксные задачи ====
* Из книжки 2.
* '''Т.''' F1 ≤ F2 ≤ F3 ≤ F4. Противник знает x → не знает → мы знаем y.
==== Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход ====
* Из книжки 2.
* Лексикографический подход — упорядочиваем их по важности и ORDER BY.
==== Кооперативные игры (''с''-ядро, вектор Шепли) ====
* Игроки делят выручку.
* '''Вектор Шепли''' — состоит из компонент, равных мат.ожиданиям вкладов конкретных игроков.
==== Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера) ====
* Из книжки 2.
* '''Т.''' (критерий Гросса) аналог уравнивания для производных.
==== Иерархические игры ====
* '''Опр.''' иерархической игры (есть обмен информацией о стратегиях).
* '''Т.''' (Гермейера). В Г<sub>2</sub> гарантированный результат игрока X = максимум из 1) гарантированного результата X при наилучшем ответе Y на стратегию наказания, применяемую к нему X и 2) лучшего результата X в случае, если он позволит Y получить больше, чем в первом случае.
==== Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача) ====
* В книжках нет.
# {{Скачать|Оре - Теория графов.djvu}}
==== Основные комбинаторные числа ====
==== Оценки и асимптотики для комбинаторных чисел ====
==== Графы и сети. Оценки числа графов и сетей различных типов ====
==== Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности) ====
* Можно почитать [[rupedia:Планарный граф]].
* '''Т.''' (ф-ла Эйлера) ''Вершин − Ребёр + Граней = 2'' у всякого связного плоского графа.
==== Экстремальная теория графов. Теорема Турана ====
==== Теорема Рамсея ====
== Теория кодирования ==
==== Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана ====
==== Оптимальное кодирование. Построение кодов с минимальной избыточностью ====
==== Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку ====
==== Конечные поля и их основные свойства ====
==== Коды Боуза—Чоудхури—Хоквингема ====
* Можно почитать [[rupedia:Код Боуза — Чоудхури — Хоквингема]], как пример - [[rupedia:Код Рида — Соломона]].
Почти вся берётся из лекций [[rupedia:Шананин,_Александр_Алексеевич|Шананина]]: {{Скачать|Шананин А.А. - Лекции по математическим моделям в экономике 1999.pdf}}.
==== Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц ====
* x-Ax=w, w≥0, x≥0 — модель Леонтьева.
* '''T.''' (об уст.матрицах)
==== Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона ====
* '''Опр.''' динам.модель Леонтьева (cx → max, Ax(t+1) ≤ x(t)); магистраль (отклоняется не больше чем на заданный угол).
* '''Т.''' (Моришимы) вектор Ф-П матрицы A — магистраль для семейства решений д.м. Л.
==== Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования ====
* Прямая задача — максимизируем прибыль при ограничениях на трудозатраты (не больше).
* Обратная задача — минимизируем зарплату при ограничениях на внутренние цены (не меньше).
==== Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона ====
* Типа, сколько надо просить за опцион, чтобы потом было на что реализовать право покупателя.
* <m>\sum{2^n+1}{2^{n+1}}p(j)b(j) = \beta(1)b(1) + \gamma(1)s(1)</m>
==== Модель олигополистической конкуренции Курно. Теорема Нэша ====
* '''Опр.''' (бояны) игра N игроков, равновесие по Нэшу.
* '''Т.''' (существования решения) c(x) и P(x) {{in}} C², издержки возрастают и выпуклы, P(x) неотрицательна и убывает в 0 (есть насыщение) ⇒ {{exists}}! равновесие по Нэшу.
==== Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре ====
* '''Опр.''' совершенная конкуренция.
* '''Т.''' (Э-Д) (существования конкурентного равновесия с кучей условий)
==== Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы ====
* Отсебятина: на неподвижных точках, между прочим, [[rupedia:Алгоритм фрактального сжатия|фрактальное сжатие]] работает. Правда, не на Брауэре, а на Банахе, но это не важно.
* '''Л.''' (Г-Н-Д) замкнутое непустое выпуклое ({{forall}}x f(x) выпукло) м/о из пространства весовых векторов (сумма неотриц. компонент=1) в 2<sup>Rn</sup> и такое, что {{forall}}p, u{{in}}f(p) pu≥0 переводит хотя бы один x хотя бы в один неотрицательный вектор.
==== Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия ====
* Можно почитать [[rupedia:Первая теорема благосостояния]], [[rupedia:Вторая теорема благосостояния]].
* Сравнительная статика: по идее это сравнение «снимков» состояния без прямого учёта фактора времени, но где почитать именно про равновесие — неизвестно.
==== Проблемы коллективного выбора. Парадокс Эрроу ====
* Можно почитать [[rupedia:Теорема Эрроу]], [[rupedia:Парадокс Кондорсе]].
* Также не может быть: универсальность + полнота + монотонность + отсутствие диктатора + независимость от посторонних альтернатив.
==== Индексы неравенства и кривая Лоренца. Теорема мажоризации ====
* Можно почитать стр.11-21 книжки {{Скачать|Маршалл, Олкин - Неравенства - теория мажоризации и ее приложения.djvu}}.
