Редактирование: Методы Оптимизации, Теормин

Материал из eSyr's wiki.

Версия от 06:53, 8 июня 2009; 82.138.9.1 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

ПРЕДУПРЕЖДЕНИЕ: Вы редактируете устаревшую версию данной страницы. После сохранения страницы будут потеряны изменения, сделанные в последующих версиях.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

== Введение в теорию сложности ==
=== Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма. ===

'''Массовая задача <math>\Pi</math>''': 
* список свободных параметров; 
* формулировка свойств, которым должно удовлетворять решение задачи.

<math>\Pi</math> есть множество индивидуальных задач <math>I \in \Pi</math>. '''Индивидуальная задача''' получается, если всем параметрам присвоить конкретные значения.

Пусть <math>\Sigma</math> - конечный алфавит, а <math>\Sigma^*</math> - множество слов в этом алфавите. Отображение e: <math>P \rightarrow \Sigma^*</math> называется кодировкой задачи П.

'''Алгоритм <math>A</math> решает массовую задачу''' <math>\Pi</math>, если для любой индивидуальной задачи <math>I \in \Pi</math> : 
* <math>A</math> применим к <math>I</math>, то есть останавливается за конечное число шагов
* <math>A</math> дает решение <math>I</math>

'''Кодировка задачи P''' -- такое отобраение <math>e: P \rightarrow \Sigma^* </math>, обладающее следующими свойствами:
* Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
* <math>e, e^{-1}</math> -- полиномиально вычислимы
* Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо:
<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>.

===  Задачи распознавания свойств. Классы P и NP.===

'''Задача распознавания свойств''' -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.
* <math>D(\Pi)</math> -- множество всех возможных значений параметров массовой задачи.
* <math>Y(\Pi)</math> -- множество всех индивидуальных задач, ответом на которые является "да".

'''Класс полиномиально разрешимых задач (P)''' -- это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом:
* <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>

<u>Примеры неполиномиальных задач:</u>
* алгоритмически неразрешимые задачи: <math>\forall A ~~ \exists I \in \Pi</math> такая, что <math>A</math> не применим к <math>I</math>, например, <math>t_A(e(I)) = \infty</math>
** [http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BE%D1%84%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D0%BE_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5 10-я проблема Гильберта]: по данному многочлену <math>g</math> с целыми коэффициентами выяснить, имеет ли уравнение <math>g = 0</math> целочисленное решение
* задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
** найти все маршруты в задаче коммивояжёра

'''Класс недетерменированно полиномиальных задач (NP)''' -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:
* <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>

=== Теорема об экспоненциальной временной оценке для задач из класса NP. ===

Для любой <math>\Pi \in NP</math> существует ДМТ <math>A</math>, решающая ее с не более чем экспоненциальной временной сложностью: <math>T_A(n) \leqslant 2^{p(n)} </math>.

=== Класс co-NP. Пример задачи, допускающей хорошую характеризацию.  Доказательство утверждения о взаимоотношении классов NPC и co-NP. ===

'''Дополнительная задача <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>D(\overline{\Pi}) = D(\Pi)</math>
* <math>Y(\overline{\Pi}) = D(\Pi) \setminus Y(\Pi)</math>

Класс <math>\text{co-P}</math> -- <math>\{\overline{\Pi} | \Pi \in P\}</math>
* <math>\text{co-P} = P</math>.

Класс <math>\text{co-NP}</math> -- <math>\{\overline{\Pi} | \Pi \in NP\}</math>. 
* <math>\text{co-NP} = NP</math> пока не удалось ни доказать, ни опровергнуть.
* <math>P \in NP \cap \text{co-NP}</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>\Pi'</math> с кодировкой <math>e'</math> ''' полиномиально сводится ''' к задаче <math>\Pi</math> с кодировкой <math>e</math>, если любая индивидуальная задача <math>I' \in \Pi'</math> может быть сведена за полиномиальное от её длины время к некоторой задаче <math>I \in \Pi</math> с сохранением ответа.

Массовая задача <math>\Pi</math> называется '''NP-полной (универсальной)''', если 
* принадлежит классу NP: <math>\Pi \in \text{NP}</math>
* любая задача из NP полиномиально сводится к <math>\Pi</math>: <math>\forall \Pi' \in \text{NP} ~~~ \Pi' \propto \Pi</math>

Класс '''NPC (NP-complete)''' -- множество всех NP-полных задач.

===  Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН ===

=== Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачи ===

=== Взаимоотношение классов 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>

Класс '''PSPACE''' массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти.

''Гипотеза.'' <math>\text{P} \subset \text{PSPACE}</math>. При этом NP-полные, NP-трудные, NP-эквивалентные задачи <math> \subset \text{PSPACE} \setminus \text{P}</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> -- некоторый полином от двух переменных.

=== Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения ===

'''Полиномиальное сужение''' массовой задачи <math>\Pi</math> -- множество таких индивидуальных задач <math>I</math>, числовые параметры которых не превосходят полинома от длины входа: <math>\Pi_{p(\cdot)} = \{ I \in \Pi |  M(I) \leqslant p(|I|) \}</math>

Массовая задача <math>\Pi</math> называется '''сильно NP-полной''', если её полиномиальное сужение является NP-полным.
* задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями
* задача булевых линейных неравенств
* задача о целочисленном решении системы линейных уравнений
* задача комивояжа

=== Определение <math>\varepsilon</math>-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью ===

=== Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания ===

== Основы линейного программирования ==

=== Определение озЛП. Принцип граничных решений.  Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП ===
'''ЛП''' (линейное программирование) -- теория, приложения и методы решения системы линейных неравенств с конечным числом неизвестных : <math>Ax \leqslant b~,~~ x = \{x_{i}\}, i = 1 \dots n </math>, существует ли <math>x \in \mathbb{R}^{n}</math>, удовлетворяющий данной системе линейных неравентсв

'''озЛП''' (основная задача линейного программирования) : найти такой вектор <math>x \in \mathbb{R}^{n}</math> -- решение задачи линейного программирования <math>d^{*} = \max_{x \in \mathbb{R}^n;~Ax \leqslant b} \langle c, x \rangle</math>, максимизирующее линейную функцию <math>\langle c, x \rangle = c_1 x_1 + c_2 x_2 + \dots + c_n x_n</math>

'''Утверждение (принцип граничных решений)'''. Если озЛП имеет решение, то найдется такая подматрица <math>A_I</math> матрицы <math>A</math>, что любое решение системы уравнений <math>A_I x = b_I</math> реализует максимум <math>c(x)</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>

=== Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами ===

<math>x^{\varepsilon}</math> -- '''<math>\varepsilon</math>-приближенное решение системы ЛН''', если 
* в строчной записи: <math>\langle a_i , x^{\varepsilon} \rangle \leqslant b_i + \varepsilon~,~~ \forall i \in [1,m]</math>
* в матричной записи: <math>Ax^\varepsilon \leqslant b + \varepsilon e</math>, где <math>e</math> -- вектор-столбец из единиц

'''Теорема'''. Если система линейных неравенств имеет <math>\varepsilon_1</math> приближенное решение (<math>\varepsilon_1 = \frac{1}{(n+2)(\Delta(A))}</math>), то эта система разрешима, то есть имеет точное решение.

=== Описание метода эллипсоидов ===

Решает задачу линейного программирования за полиномиальное число шагов.

Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.

'''Лемма1.''' Если система <math>Ax \leqslant b</math> совместна,то в шаре <math>E_0 = \| x \| \leqslant \sqrt{n} \Delta([A|b])</math> найдется ее решение.

Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений

Введем функцию невязки в точке 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>. Пересечение этого полупространства с нашей сферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново.

=== Теория двойственности ЛП ===
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче.

http://www.mathelp.spb.ru/book1/lprog5.htm

=== Идея метода Кармаркара ===

http://logic.pdmi.ras.ru/~yura/modern/02seminar.pdf

=== Следствия систем линейных неравенств. Афинная лемма Фаркаша (без доказательства) ===

Определение. <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>

http://imcs.dvgu.ru/lib/nurmi/finmath/node41.html

=== Лемма Фаркаша о неразрешимости ===

'''Лемма'''.
Система динейный неравенсив <math>Ax <= b</math> неразрешима тогда и только тогда, когда разрешима система:

<math>\Sigma\lambda_ia_i = 0 \ \Sigma\lambda_ib_i <= -1 \ \lambda_i >= 0 \forall i \in M\ </math>

== Элементы математического программирования ==

== Способы решения переборных задач ==
=== Методы глобальной минимизации ===

== Неотсортировано ==
# Формула градиентного метода в задаче безусловной минимизации
# Сведение озЛП к однородной системе уравнений с огрничением x>0
# Формула градиентного метода в задаче безусловной минимизации
# Формула метода Ньютона в задаче безусловной минимизации
# Идея метода штрафов
# Геометрическое описание симплекс-метода
# Методы глобальной минимизации
# Полиномиальный алгоритм округления ?1-приближенного решения системы линейных неравенств
# Идея метода эллипсоидов
# Идея метода Ньютона
# Теорема оптимальности для разложимых функций
# Идея метода ветвей и границ. Пример для задачи БЛП
# Метод ветвей и границ для ЦЛП. Различные стратегии метода
# Метод ветвей и границ для глобальной минимизации Липшицевых функций
# Понятие о временной сложности алгоритмов
# Понятие о недетерминированно-полиномиальных задачах
# Метод динамического программирования для БЛП с неотрицательными коэффициентами
# Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи
# Оценка сложности метода эллипсоидов ?2-приближенного решения озЛП

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице: