Редактирование: Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
- | {{Курс Методы оптимизации}} | ||
- | |||
== Введение в теорию сложности == | == Введение в теорию сложности == | ||
=== Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма. === | === Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма. === | ||
- | ''Методичка, стр. 4-8'' | ||
'''Массовая задача <math>\Pi</math>''': | '''Массовая задача <math>\Pi</math>''': | ||
* список свободных параметров; | * список свободных параметров; | ||
* формулировка свойств, которым должно удовлетворять решение задачи. | * формулировка свойств, которым должно удовлетворять решение задачи. | ||
- | |||
<math>\Pi</math> есть множество индивидуальных задач <math>I \in \Pi</math>. '''Индивидуальная задача''' получается, если всем параметрам присвоить конкретные значения. | <math>\Pi</math> есть множество индивидуальных задач <math>I \in \Pi</math>. '''Индивидуальная задача''' получается, если всем параметрам присвоить конкретные значения. | ||
- | + | Пусть <math>\Sigma</math> - конечный алфавит, а <math>\Sigma^*</math> - множество слов в этом алфавите. Отображение e: <math>P \rightarrow \Sigma^*</math> называется кодировкой задачи П. | |
- | Пусть <math>\Sigma</math> | + | |
- | + | ||
'''Алгоритм <math>A</math> решает массовую задачу''' <math>\Pi</math>, если для любой индивидуальной задачи <math>I \in \Pi</math> : | '''Алгоритм <math>A</math> решает массовую задачу''' <math>\Pi</math>, если для любой индивидуальной задачи <math>I \in \Pi</math> : | ||
Строка 20: | Строка 14: | ||
* <math>A</math> дает решение <math>I</math> | * <math>A</math> дает решение <math>I</math> | ||
- | + | '''Кодировка задачи P''' -- такое отобраение <math>e: P \rightarrow \Sigma^* </math>, обладающее следующими свойствами: | |
- | '''Кодировка задачи P''' | + | |
* Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок. | * Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок. | ||
- | * <math>e, e^{-1}</math> | + | * <math>e, e^{-1}</math> -- полиномиально вычислимы |
* Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо: | * Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо: | ||
- | <math>\exists p(.): \forall I \in | + | <math>\exists p(.): \forall I \in P |e(I)| < p(e_{1}(I))</math> |
+ | '''Язык массовой задачи''' -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): <math>L(\Pi, e) = e(Y(\Pi)) = \{s \in \Sigma^*| s = e(I), I \in Y(\Pi)\}</math> | ||
- | '''Язык | + | '''Язык алгоритма''' -- множество слов, принимаемых <math>A</math>, то есть таких, на которых алгоритм останавливается в состоянии <math>q_Y</math>, что соответсвует "да": <math>L(A) = \{\sigma \in \Sigma^* | A(\sigma) = q_Y\}</math> |
- | ''' | + | Алгоритм <math>A</math> '''решает''' массовую задачу <math>\Pi</math>, с кодировкой <math>e</math>, если <math>L(e, \Pi) = L(A)</math> |
- | + | <math>t_{A}(s)</math> -- число шагов алгоритма <math>A</math> для входа <math>s \in \Sigma^*</math>. | |
- | + | '''Временная сложность''' <math>T_{A}(n) = max \{t_{A}(s)\}, s \in \Sigma^*, |s| < n </math>. | |
- | + | ||
- | + | ||
- | '''Временная сложность''' <math>T_{A}(n) = | + | |
=== Задачи распознавания свойств. Классы P и NP.=== | === Задачи распознавания свойств. Классы P и NP.=== | ||
- | ''Методичка, стр. 8-11'' | ||
'''Задача распознавания свойств''' -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения. | '''Задача распознавания свойств''' -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения. | ||
Строка 46: | Строка 36: | ||
* <math>Y(\Pi)</math> -- множество всех индивидуальных задач, ответом на которые является "да". | * <math>Y(\Pi)</math> -- множество всех индивидуальных задач, ответом на которые является "да". | ||
- | '''Класс полиномиально разрешимых задач (P)''' -- это такие задачи, | + | '''Класс полиномиально разрешимых задач (P)''' -- это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом: |
* <math>\exists A</math> такой, что <math>A</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math> | * <math>\exists A</math> такой, что <math>A</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math> | ||
* <math>\exists p(\cdot)</math> -- полином такой, что <math>T_A(n) < p(n)~~,~\forall n \in Z_{+}</math> | * <math>\exists p(\cdot)</math> -- полином такой, что <math>T_A(n) < p(n)~~,~\forall n \in Z_{+}</math> | ||
Строка 55: | Строка 45: | ||
* задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа | * задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа | ||
** найти все маршруты в задаче коммивояжёра | ** найти все маршруты в задаче коммивояжёра | ||
- | * ∀А, решающего П с кодировкой e, ∀p(·) ∃I ∈ П: <math>t_A(e(I)) > p(|e(I)|)</math> | ||
- | |||
- | '''Класс | + | '''Класс недетерменированно полиномиальных задач (NP)''' -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга: |
* <math>\exists \hat{A}</math> для НДМТ такой, что <math>\hat{A}</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math> | * <math>\exists \hat{A}</math> для НДМТ такой, что <math>\hat{A}</math> решает массовую задачу <math>\Pi</math> с кодировкой <math>e</math> | ||
* <math>\exists p(\cdot)</math> -- полином такой, что <math>\hat{T}_{\hat{A}}(n) < p(n)~~,~\forall n \in Z_{+}</math> | * <math>\exists p(\cdot)</math> -- полином такой, что <math>\hat{T}_{\hat{A}}(n) < p(n)~~,~\forall n \in Z_{+}</math> | ||
=== Теорема об экспоненциальной временной оценке для задач из класса NP. === | === Теорема об экспоненциальной временной оценке для задач из класса NP. === | ||
- | ''Методичка, стр. 11'' | ||
Для любой <math>\Pi \in NP</math> существует ДМТ <math>A</math>, решающая ее с не более чем экспоненциальной временной сложностью: <math>T_A(n) \leqslant 2^{p(n)} </math>. | Для любой <math>\Pi \in NP</math> существует ДМТ <math>A</math>, решающая ее с не более чем экспоненциальной временной сложностью: <math>T_A(n) \leqslant 2^{p(n)} </math>. | ||
=== Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP. === | === Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP. === | ||
- | ''Методичка, стр. 12-14'' | ||
'''Дополнительная задача <math>\overline\Pi</math>''' к массовой задаче <math>\Pi</math> -- задача, получаемая из <math>\Pi</math> путем введения альтернативного вопроса. То есть если в <math>\Pi</math> спрашиваем "верно ли <math>x</math>", то в <math>\overline\Pi</math> спрашиваем "верно ли, что <math>\neg x</math>" | '''Дополнительная задача <math>\overline\Pi</math>''' к массовой задаче <math>\Pi</math> -- задача, получаемая из <math>\Pi</math> путем введения альтернативного вопроса. То есть если в <math>\Pi</math> спрашиваем "верно ли <math>x</math>", то в <math>\overline\Pi</math> спрашиваем "верно ли, что <math>\neg x</math>" | ||
Строка 78: | Строка 64: | ||
Класс <math>\text{co-NP}</math> -- <math>\{\overline{\Pi} | \Pi \in NP\}</math>. | Класс <math>\text{co-NP}</math> -- <math>\{\overline{\Pi} | \Pi \in NP\}</math>. | ||
- | * <math>\text{co-NP} = NP</math> пока не удалось ни доказать, ни опровергнуть | + | * <math>\text{co-NP} = NP</math> пока не удалось ни доказать, ни опровергнуть. |
* <math>P \in NP \cap \text{co-NP}</math> | * <math>P \in NP \cap \text{co-NP}</math> | ||
- | Массовая задача <math>\Pi</math> '''допускает хорошую | + | Массовая задача <math>\Pi</math> '''допускает хорошую характеристику''', если <math>\Pi \in \text{NP} \cap \text{co-NP}</math> |
* пример такой задачи -- это задача определения простоты числа. | * пример такой задачи -- это задача определения простоты числа. | ||
* <math>P \subseteq \text{NP} \cap \text{co-NP}</math> | * <math>P \subseteq \text{NP} \cap \text{co-NP}</math> | ||
Строка 94: | Строка 80: | ||
=== Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН === | === Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН === | ||
- | ''Методичка, стр. 15'' | ||
- | |||
- | ''' Критерий NP-полноты. ''' Массовая задача <math>\Pi</math> '''NP-полна''' тогда и только тогда, когда она принадлежит классу '''NP''' и к ней полиномиально сводится какая-либо '''NP-полная''' задача. | ||
=== Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачи === | === Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачи === | ||
- | ''Методичка, стр. 17-18'' | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE === | === Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE === | ||
- | + | ''Гипотеза.'' <math>\Pi \subseteq \text{NP} \cap \text{co-NP}</math> | |
- | Если для некоторой NP-полной задачи <math>\Pi</math> дополнительная к ней задача <math>\overline{\Pi} \in \text{NP}</math>, то <math>\text{NP} = \text{co-NP}</math> | + | ''Гипотеза.'' Если для некоторой NP-полной задачи <math>\Pi</math> дополнительная к ней задача <math>\overline{\Pi} \in \text{NP}</math>, то <math>\text{NP} = \text{co-NP}</math> |
Класс '''PSPACE''' массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти. | Класс '''PSPACE''' массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти. | ||
- | ''Гипотеза.'' <math>\text{P} \subset \text{PSPACE}</math> | + | ''Гипотеза.'' <math>\text{P} \subset \text{PSPACE}</math>. При этом NP-полные, NP-трудные, NP-эквивалентные задачи <math> \subset \text{PSPACE} \setminus \text{P}</math> |
=== Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке === | === Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке === | ||
Строка 123: | Строка 100: | ||
Пусть <math>M(I)</math> -- некоторая функция, задающая значение числового параметра индивидуальной задачи <math>I</math>. Если таких параметров несколько, в качестве <math>M(I)</math> можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то <math>M(I) = 0</math>. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости <math>T_{max}(I) = O(p(|I|, M(I)))</math>, где <math>p(\cdot, \cdot)</math> -- некоторый полином от двух переменных. | Пусть <math>M(I)</math> -- некоторая функция, задающая значение числового параметра индивидуальной задачи <math>I</math>. Если таких параметров несколько, в качестве <math>M(I)</math> можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то <math>M(I) = 0</math>. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости <math>T_{max}(I) = O(p(|I|, M(I)))</math>, где <math>p(\cdot, \cdot)</math> -- некоторый полином от двух переменных. | ||
- | |||
- | [http://en.wikipedia.org/wiki/Pseudo-polynomial_time en-wiki] | ||
=== Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения === | === Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения === | ||
Строка 130: | Строка 105: | ||
'''Полиномиальное сужение''' массовой задачи <math>\Pi</math> -- множество таких индивидуальных задач <math>I</math>, числовые параметры которых не превосходят полинома от длины входа: <math>\Pi_{p(\cdot)} = \{ I \in \Pi | M(I) \leqslant p(|I|) \}</math> | '''Полиномиальное сужение''' массовой задачи <math>\Pi</math> -- множество таких индивидуальных задач <math>I</math>, числовые параметры которых не превосходят полинома от длины входа: <math>\Pi_{p(\cdot)} = \{ I \in \Pi | M(I) \leqslant p(|I|) \}</math> | ||
- | Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным. | + | Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным. |
* задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями | * задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями | ||
- | * задача булевых линейных неравенств | + | * задача булевых линейных неравенств |
- | * задача о целочисленном решении системы линейных уравнений | + | * задача о целочисленном решении системы линейных уравнений |
- | * задача | + | * задача комивояжа |
- | + | === Определение <math>\varepsilon</math>-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью === | |
- | + | ||
- | + | ||
- | + | ||
- | === Определение | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания === | === Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания === | ||
- | ''Методичка, стр. 24'' | ||
- | |||
- | '''Теорема''' Если для <math>\Pi</math> оптимизации | ||
- | * соответствующая ей задача распознавания свойств является сильно NP-полной | ||
- | * существует полином <math>\exists p'(\cdot) : \mathrm{Opt}_\Pi(I) < p'(M(I)) ~~ \forall I \in \Pi</math> | ||
- | то при условии, что <math>\mathrm{P} \neq \mathrm{NP}</math> для <math>\Pi</math> не существует ПППС | ||
== Основы линейного программирования == | == Основы линейного программирования == | ||
Строка 170: | Строка 123: | ||
- | '''Утверждение (принцип граничных решений)'''. Если озЛП имеет решение, то найдется такая подматрица <math>A_I</math> матрицы <math>A</math>, что любое решение системы уравнений <math>A_I x = b_I</math> реализует максимум <math> | + | '''Утверждение (принцип граничных решений)'''. Если озЛП имеет решение, то найдется такая подматрица <math>A_I</math> матрицы <math>A</math>, что любое решение системы уравнений <math>A_I x = b_I</math> реализует максимум <math>c(x)</math>. |
'''Алгебраическая сложность''' -- количество арифметических операций. | '''Алгебраическая сложность''' -- количество арифметических операций. | ||
Строка 177: | Строка 130: | ||
Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остается открытым. | Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остается открытым. | ||
- | |||
- | === Геометрическое описание симплекс-метода === | ||
- | (Копипаста из [[http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81-%D0%BC%D0%B5%D1%82%D0%BE%D0%B4 ru.wiki]], там-же есть хорошая иллюстрация.)<br> | ||
- | Симплекс-метод -- метод решения озЛП. | ||
- | |||
- | Каждое из линейных неравенств в <math>Ax \leqslant b</math> ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. | ||
- | Уравнение <math>W(x) = c</math>, где <math>W(x)</math> — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость <math>L(c)</math>. Зависимость от <math>c</math> порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее <math>c</math>, что гиперплоскость <math>L(c)</math> пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его ребрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено. | ||
=== Теорема о границах решений задач ЛП с целыми коэффициентами === | === Теорема о границах решений задач ЛП с целыми коэффициентами === | ||
- | ''Методичка, стр. 28-29'' | ||
- | <math>\Delta(D) = \max | \det(D_1) | </math>, где <math>D_1</math> | + | <math>\Delta(D) = \max | \det(D_1) | </math>, где <math>D_1</math> -- квадратная подматрица <math>D</math> |
- | + | Если задача озЛп <math>d^{*} = \max\langle c, x\rangle, x \in \mathbb{R}^{n}, Ax \leqslant b</math> размерности (n, m) с целыми коэффициентами разрешима, то у нее существует рацональное рашение <math>x^{*}</math> в шаре: <math>\| x^{*}\| \leqslant \sqrt{n} \Delta([A|b])</math> и <math>d^{*} = \frac{t}{s}~,~~ t,s \in Z,~~|s| \leqslant \Delta(A)</math> | |
=== Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами === | === Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами === | ||
- | ''Методичка, стр. 29'' | ||
<math>x^{\varepsilon}</math> -- '''<math>\varepsilon</math>-приближенное решение системы ЛН''', если | <math>x^{\varepsilon}</math> -- '''<math>\varepsilon</math>-приближенное решение системы ЛН''', если | ||
Строка 199: | Строка 143: | ||
* в матричной записи: <math>Ax^\varepsilon \leqslant b + \varepsilon e</math>, где <math>e</math> -- вектор-столбец из единиц | * в матричной записи: <math>Ax^\varepsilon \leqslant b + \varepsilon e</math>, где <math>e</math> -- вектор-столбец из единиц | ||
- | '''Теорема'''. Если система линейных неравенств имеет <math>\varepsilon_1</math> приближенное решение (<math>\varepsilon_1 = \frac{1}{(n+ | + | '''Теорема'''. Если система линейных неравенств имеет <math>\varepsilon_1</math> приближенное решение (<math>\varepsilon_1 = \frac{1}{(n+1)(\Delta(A))}</math>), то эта система разрешима, то есть имеет точное решение. |
=== Описание метода эллипсоидов === | === Описание метода эллипсоидов === | ||
- | * ''Методичка, стр. (30-32) 32-33'' | ||
- | * [http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%8D%D0%BB%D0%BB%D0%B8%D0%BF%D1%81%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2 вики:Метод эллипсоидов] | ||
Решает задачу линейного программирования за полиномиальное число шагов. | Решает задачу линейного программирования за полиномиальное число шагов. | ||
Строка 209: | Строка 151: | ||
Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз. | Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз. | ||
- | '''Лемма1.''' Если система <math>Ax \leqslant b</math> совместна, то в шаре <math>E_0 = \| x \| \leqslant \sqrt{n} \Delta([A|b])</math> найдется ее решение. | + | '''Лемма1.''' Если система <math>Ax \leqslant b</math> совместна,то в шаре <math>E_0 = \| x \| \leqslant \sqrt{n} \Delta([A|b])</math> найдется ее решение. |
Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений | Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений | ||
- | Введем функцию невязки в точке x -- <math>t(x) = \max_i((Ax)_i - b_i)</math>. Точка <math>x^{0}= | + | Введем функцию невязки в точке x -- <math>t(x) = \max_i((Ax)_i - b_i)</math>. Точка <math>x^{0}=0</math> -- это центр шара <math>E_0</math>. Если <math> t(x^{0}) \leqslant 0</math>, то <math>x^{0}</math> -- решение. Если это не так, то возмемем s: <math>t(x) = \langle a_{s},x^{0}\rangle - b_s</math>, значит <math>x^{0}</math> не удовлетворяет s-ому неравенству системы. Всякий вектор x, удовлетворяющий неравенству s должен лежать в полупространстве <math>\leqslant \langle a_s, x^{0}\rangle</math>. Пересечение этого полупространства с нашей сферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново. |
=== Теория двойственности ЛП === | === Теория двойственности ЛП === | ||
- | * ''Методичка, стр. 35-36'' | ||
- | * http://www.mathelp.spb.ru/book1/lprog5.htm | ||
- | |||
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. | Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. | ||
- | + | http://www.mathelp.spb.ru/book1/lprog5.htm | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Идея метода Кармаркара === | === Идея метода Кармаркара === | ||
- | * ''Методичка, стр 37-38'' | ||
- | * http://logic.pdmi.ras.ru/~yura/modern/02seminar.pdf | ||
- | + | http://logic.pdmi.ras.ru/~yura/modern/02seminar.pdf | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
=== Следствия систем линейных неравенств. Афинная лемма Фаркаша (без доказательства) === | === Следствия систем линейных неравенств. Афинная лемма Фаркаша (без доказательства) === | ||
- | * ''Методичка, стр. 34-35'' | ||
- | * http://imcs.dvgu.ru/lib/nurmi/finmath/node41.html | ||
- | + | Определение. <math>(1)\ <c, x> <= d</math> является '''следствием разрешимой системы ЛН''' <math>(2)\ Ax <= b</math>, если для всех x, для которых выполняется (2), выполняется и (1). | |
- | + | ||
- | + | ||
'''Афинная лемма Фаракша.''' | '''Афинная лемма Фаракша.''' | ||
- | Линейное неравентсво | + | Линейное неравентсво (1) является следствием разрешимой в вещественный переменных ЛН (2), тогда и только тогда, когда существует <math>\lambda \in R^{m}</math>: |
- | + | ||
- | + | <math>c = \Sigma\lambda_ia_i\ d >= \Sigma\lambda_ib_i\ \lambda_i >= 0 \forall i \in M\ </math> | |
- | + | ||
=== Лемма Фаркаша о неразрешимости === | === Лемма Фаркаша о неразрешимости === | ||
- | ''Методичка, стр. 35'' | ||
- | + | http://imcs.dvgu.ru/lib/nurmi/finmath/node41.html | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
== Элементы математического программирования == | == Элементы математического программирования == | ||
- | |||
- | === Классификация задач математического программирования. Преимущества выпуклого случая === | ||
- | ''Методичка. стр 39-41'' | ||
- | |||
- | ''' Задача математического программирования (ЗМП) ''' -- по заданной <math>f(x)</math> найти <math>\arg \min_{x \in X} f(x)</math>, то есть: | ||
- | * найти <math>x^* \in X : ~~ \forall x \in X ~ \Rightarrow ~ f(x^*) \leqslant f(x)</math> -- решение | ||
- | * <math>f^* = f(x^*)</math> -- (оптимальное) значение целевой функции <math>f(x)</math> | ||
- | * где <math>X</math> -- допустимое множество (множество ограничений) | ||
- | |||
- | Классификация проводится по ''типу допустимого множества'' <math>X</math>: | ||
- | * ''дискретные (комбинаторные)'' -- множество <math>X</math> конечно или счётно | ||
- | * ''целочисленные'' -- <math>X \equiv \mathbb{Z}^n</math> | ||
- | * ''булевы'' -- <math>X \equiv \mathbb{B}^n</math> | ||
- | * ''непрерывные'' -- <math>X \equiv \mathbb{R}^n</math> | ||
- | * ''бесконечномерные'' | ||
- | * ''функциональные'' | ||
- | |||
- | Задачи оптимизации бывают: | ||
- | * ''условные'' -- <math>X \subset \mathbb{R}^n</math> | ||
- | * ''безусловные'' -- <math>X \equiv \mathbb{R}^n</math> | ||
- | |||
- | Классификация по ''свойствам целевой функции'': выпуклость, гладкость и т.п. | ||
- | |||
- | Классификация по результату: | ||
- | * локальная оптимизация | ||
- | * глобальная оптимизация | ||
- | |||
- | '''Выпуклое множество''' ([http://ru.wikipedia.org/wiki/%D0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE вики]) -- такое множество, которое содержит вместе с любыми двумя своими точками еще и отрезок, их соединяющий. | ||
- | |||
- | Функция <math>f</math> называется '''выпуклой''', если её надграфик (множество точек над графиком: <math>\{(x,y):~ y \geqslant f(x) ~ \forall x \in X\}</math>) является выпуклым множеством. | ||
- | |||
- | ''Утверждение.'' Любая точка локального минимума выпуклой функции является точкой её глобального минимума. | ||
- | |||
- | <u>Преимущества выпуклых задач:</u> | ||
- | * применим метод эллипсоидов, причем сложность - полиномиальна | ||
- | * для острых задач (целевая функция убывает в окрестности минимума не медленнее некоторой линейной функции) можно получить точное решение | ||
- | |||
- | === Формула градиентного метода в задаче безусловной минимизации === | ||
- | ''Методичка. стр 41-42'' | ||
- | |||
- | Основная идея: | ||
- | * берем некоторое начальное значение | ||
- | * итеративно вычисляем [http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82 градиент] целевой функции | ||
- | * двигаемся в обратном направлении | ||
- | * и так постепенно приходим к (локальному) минимуму функции | ||
- | |||
- | '''Формула градиентного метода''' -- <math>x^{t+1} = x^t - \alpha_t \mathrm{grad} f(x^t)</math>, где <math>\alpha_t</math> -- шаговый множитель: | ||
- | * пассивный способ: <math>\{\alpha_t\}</math> выбирается заранее | ||
- | * адаптивный способ: <math>\{\alpha_t\}</math> выбирается в зависимости от реализующейся <math>x_t</math> | ||
- | ** метод скорейшего спуска -- <math>\alpha_t \in \arg \min_{\alpha > 0} f(x^t - \alpha \mathrm{grad} f(x^t))</math> | ||
- | ** метод дробления (деления пополам) -- если <math>f(x^{t+1}) > f(x^t)</math>, то возвращаемся к шагу <math>t</math> с новым значением <math>\alpha_t = \alpha_t / 2</math> | ||
- | |||
- | === Идея метода Ньютона === | ||
- | ''Методичка, стр. 43'' | ||
- | |||
- | '''Метод ньютона''' -- это фактически градиентный спуск с адаптивыным коэффициентом, который берется, как 2 производная целевой функции. | ||
- | |||
- | Реально можно вывести формулу Ньютона из [http://ru.wikipedia.org/wiki/%D0%A0%D1%8F%D0%B4_%D0%A2%D0%B5%D0%B9%D0%BB%D0%BE%D1%80%D0%B0 разложения по Тейлору] до 2 производной в окрестности точки минимума. | ||
- | |||
- | === Формула метода Ньютона в задаче безусловной минимизации === | ||
- | ''Методичка. стр 43'' | ||
- | |||
- | ''' Формула Ньютона ''' -- <math>x^{t+1} = x^t - \frac{1}{f''(x^t)} \mathrm{grad}f(x^t)</math>, при этом начальное приближение должно находиться достаточно близко к искомой точке минимума. | ||
- | |||
- | Метод ньютона имеет <u>квадратичную скорость сходимости</u>: <math>\| x^{t+1} - x^* \| \leqslant \frac{1}{Q} (Q \| x^1 - x^* \|)^2</math>, где <math>Q</math> - некоторая константа | ||
- | |||
- | <u>Ограничения:</u> | ||
- | * невырожденность матрицы 2 производных ([http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D1%81%D1%81%D0%B8%D0%B0%D0%BD_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8 гессиана]) | ||
- | * близость начального приближения к точке минимума (<math>\| x^1 - x^* \| < 1/Q</math>) | ||
- | |||
- | === Идея метода штрафов === | ||
- | ''Методичка. стр 44'' | ||
- | |||
- | Смысл метода в том, чтобы свести задачу условной оптимизации к задаче безусловной оптимизации, то есть избавится от ограничения на область, в которой ищем минимум. | ||
- | |||
- | Для этого вводится так называемая функция штрафа, которая равна нулю в той области, в которой мы "условно оптимизируем" целевую функцию, а в остальных точках добавляет к значению целевой функции некоторое значение (собственно, штраф). | ||
- | |||
- | ''Пример.'' Пусть область задаётся следующим образом: <math>X = \{x | g(x) \leqslant 0 \}</math>, где <math>g(x)</math> -- некоторая функция. Тогда рассмотрим задачу безусловной минимизации целевой функции <math>f(x)</math> со штрафом: <math>\min_{x \in \mathbb{R}^n} \{ f(x) + C g(x)^p\}</math>, где <math>C</math> -- некоторая константа [??], а <math>p \geqslant 1</math> -- параметр штрафа | ||
== Способы решения переборных задач == | == Способы решения переборных задач == | ||
- | === Методы глобальной минимизации === | ||
- | ''Методичка. стр. 52 (52-55)'' | ||
- | |||
- | |||
- | |||
- | === Метод ветвей и границ для глобальной минимизации Липшицевых функций === | ||
- | ''Методичка. стр. 54'' | ||
- | |||
- | === Метод ветвей и границ для ЦЛП. Различные стратегии метода === | ||
- | ''Методичка. стр. 57'' | ||
- | |||
- | === Идея метода ветвей и границ. Пример для задачи БЛП === | ||
- | ''Методичка. стр. 59'' | ||
- | |||
- | === Теорема оптимальности для разложимых функций === | ||
- | ''Методичка. стр 60'' | ||
- | |||
- | '''Опр.''' Функция f называется '''разделяемой''' на <math>f_1</math> и <math>f_2</math>, если она представима в виде <math>f(x, y) = f_1(x, f_2(y))</math>. | ||
- | |||
- | '''Опр.''' Функция f называется '''разложимой''' на <math>f_1</math> и <math>f_2</math>, если: | ||
- | * она разделяема на <math>f_1</math> и <math>f_2</math> | ||
- | * <math>f_1</math> монотонно не убывает по последнему аргументу | ||
- | |||
- | '''Теорема оптимальности для разложимых функций''': <math> \min_{x,y}(f(x,y)) = \min_x(f_1(x, \min_y(f_2(y)))) </math>. | ||
- | |||
- | Указанная теорема используется для уменьшения размерности оптимизационных задач и в методе ДП. | ||
- | |||
- | === Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи === | ||
- | '' Методичка. стр. 62 '' | ||
- | |||
- | === Метод динамического программирования для БЛП с неотрицательными коэффициентами === | ||
- | '' Методичка. стр. 63-64 '' | ||
== Неотсортировано == | == Неотсортировано == | ||
- | # Полиномиальный алгоритм округления | + | # Формула градиентного метода в задаче безусловной минимизации |
+ | # Сведение озЛП к однородной системе уравнений с огрничением x>0 | ||
+ | # Формула градиентного метода в задаче безусловной минимизации | ||
+ | # Формула метода Ньютона в задаче безусловной минимизации | ||
+ | # Идея метода штрафов | ||
+ | # Геометрическое описание симплекс-метода | ||
+ | # Методы глобальной минимизации | ||
+ | # Полиномиальный алгоритм округления ?1-приближенного решения системы линейных неравенств | ||
+ | # Идея метода эллипсоидов | ||
+ | # Идея метода Ньютона | ||
+ | # Теорема оптимальности для разложимых функций | ||
+ | # Идея метода ветвей и границ. Пример для задачи БЛП | ||
+ | # Метод ветвей и границ для ЦЛП. Различные стратегии метода | ||
+ | # Метод ветвей и границ для глобальной минимизации Липшицевых функций | ||
# Понятие о временной сложности алгоритмов | # Понятие о временной сложности алгоритмов | ||
# Понятие о недетерминированно-полиномиальных задачах | # Понятие о недетерминированно-полиномиальных задачах | ||
- | # Оценка сложности метода эллипсоидов | + | # Метод динамического программирования для БЛП с неотрицательными коэффициентами |
- | + | # Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи | |
- | + | # Оценка сложности метода эллипсоидов ?2-приближенного решения озЛП |