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

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

(Различия между версиями)

Версия 21:41, 8 июня 2009

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

Календарь

	пт	пт	пт	пт	пт
Февраль		08	15	22	29
Март	06	13	20	27
Апрель	04	11	18	25
Май	02		16	23

Материалы
Упражнения || Задачи | Определения | Утверждения | Теоремы || Теормин | Обозначения

Содержание

1 Введение в теорию сложности
2 Основы линейного программирования
3 Элементы математического программирования
4 Способы решения переборных задач
5 Неотсортировано

Введение в теорию сложности

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

Методичка, стр. 4-8

Массовая задача $Π$ :

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

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

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

Алгоритм $A$ решает массовую задачу $Π$ , если для любой индивидуальной задачи $I \in \Pi$ :

$A$ применим к $I$ , то есть останавливается за конечное число шагов
$A$ дает решение $I$

Кодировка задачи P -- такое отобраение $e: P \rightarrow \Sigma^*$ , обладающее следующими свойствами:

Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
$e, e - 1$ -- полиномиально вычислимы
Кодировка не избыточна, то есть для любой другой кодировки $e 1$ , удовлетворяющей 1 и 2 условиям справедливо:

$\exists p(.): \forall I \in P |e(I)| < p(e_{1}(I))$

Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): $L(\Pi, e) = e(Y(\Pi)) = \{s \in \Sigma^*| s = e(I), I \in Y(\Pi)\}$

Язык алгоритма -- множество слов, принимаемых $A$ , то есть таких, на которых алгоритм останавливается в состоянии $q Y$ , что соответсвует "да": $L(A) = \{\sigma \in \Sigma^* | A(\sigma) = q_Y\}$

Алгоритм $A$ решает массовую задачу $Π$ , с кодировкой $e$ , если $L (e,Π) = L (A)$

$t A (s)$ -- число шагов алгоритма $A$ для входа $s \in \Sigma^*$ .

Временная сложность $T_{A}(n) = max \{t_{A}(s)\}, s \in \Sigma^*, |s| < n$ .

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

Методичка, стр. 8-11

Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.

$D (Π)$ -- множество всех возможных значений параметров массовой задачи.
$Y (Π)$ -- множество всех индивидуальных задач, ответом на которые является "да".

Класс полиномиально разрешимых задач (P) -- это такие задачи, временная сложность алгоритма решения которых ограниченна полиномом:

$\exists A$ такой, что $A$ решает массовую задачу $Π$ с кодировкой $e$
$\exists p(\cdot)$ -- полином такой, что $T_A(n) < p(n)~~,~\forall n \in Z_{+}$

Примеры неполиномиальных задач:

алгоритмически неразрешимые задачи: такая, что A не применим к I, например,
- 10-я проблема Гильберта: по данному многочлену $g$ с целыми коэффициентами выяснить, имеет ли уравнение $g = 0$ целочисленное решение
задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
- найти все маршруты в задаче коммивояжёра

Класс недетерменированно полиномиальных задач (NP) -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:

$\exists \hat{A}$ для НДМТ такой, что $\hat{A}$ решает массовую задачу $Π$ с кодировкой $e$
$\exists p(\cdot)$ -- полином такой, что $\hat{T}_{\hat{A}}(n) < p(n)~~,~\forall n \in Z_{+}$

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

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

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

Дополнительная задача $\overline\Pi$ к массовой задаче $Π$ -- задача, получаемая из $Π$ путем введения альтернативного вопроса. То есть если в $Π$ спрашиваем "верно ли $x$ ", то в $\overline\Pi$ спрашиваем "верно ли, что $\neg x$ "

$D(\overline{\Pi}) = D(\Pi)$
$Y(\overline{\Pi}) = D(\Pi) \setminus Y(\Pi)$

Класс $co-P$ -- $\{\overline{\Pi} | \Pi \in P\}$

$co-P = P$ .

Класс $co-NP$ -- $\{\overline{\Pi} | \Pi \in NP\}$ .

$co-NP = N P$ пока не удалось ни доказать, ни опровергнуть.
$P \in NP \cap \text{co-NP}$

Массовая задача $Π$ допускает хорошую характеризацию, если $\Pi \in \text{NP} \cap \text{co-NP}$

пример такой задачи -- это задача определения простоты числа.
$P \subseteq \text{NP} \cap \text{co-NP}$

Массовая задача $Π'$ с кодировкой $e'$ полиномиально сводится к задаче $Π$ с кодировкой $e$ , если любая индивидуальная задача $I' \in \Pi'$ может быть сведена за полиномиальное от её длины время к некоторой задаче $I \in \Pi$ с сохранением ответа.

Массовая задача $Π$ называется NP-полной (универсальной), если

принадлежит классу NP: $\Pi \in \text{NP}$
любая задача из NP полиномиально сводится к $Π$ : $\forall \Pi' \in \text{NP} ~~~ \Pi' \propto \Pi$

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

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

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

Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE

Гипотеза. $\Pi \subseteq \text{NP} \cap \text{co-NP}$

Гипотеза. Если для некоторой NP-полной задачи $Π$ дополнительная к ней задача $\overline{\Pi} \in \text{NP}$ , то $NP = co-NP$

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

Гипотеза. $\text{P} \subset \text{PSPACE}$ . При этом NP-полные, NP-трудные, NP-эквивалентные задачи $\subset \text{PSPACE} \setminus \text{P}$

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

Псевдополиномиальный алгоритм - полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров.

Пусть $M (I)$ -- некоторая функция, задающая значение числового параметра индивидуальной задачи $I$ . Если таких параметров несколько, в качестве $M (I)$ можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то $M (I) = 0$ . Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости $T m a x (I) = O (p ( | I | , M (I)))$ , где $p(\cdot, \cdot)$ -- некоторый полином от двух переменных.

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

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

Массовая задача $Π$ называется сильно NP-полной, если её полиномиальное сужение является NP-полным.

задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями
задача булевых линейных неравенств
задача о целочисленном решении системы линейных уравнений
задача комивояжа

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

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

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

Определение озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП

ЛП (линейное программирование) -- теория, приложения и методы решения системы линейных неравенств с конечным числом неизвестных : $Ax \leqslant b~,~~ x = \{x_{i}\}, i = 1 \dots n$ , существует ли $x \in \mathbb{R}^{n}$ , удовлетворяющий данной системе линейных неравентсв

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

Утверждение (принцип граничных решений). Если озЛП имеет решение, то найдется такая подматрица $A I$ матрицы $A$ , что любое решение системы уравнений $A I x = b I$ реализует максимум $c (x)$ .

Алгебраическая сложность -- количество арифметических операций.

Битовая сложность -- количество операций с битами. Битовая сложность задач ЛП, ЛН полиномиальна.

Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остается открытым.

Теорема о границах решений задач ЛП с целыми коэффициентами

Методичка, стр. 28-29

$Δ(D) = max | det(D 1) |$ , где $D 1$ -- квадратная подматрица $D$

Теорема (о границах решений). Если задача озЛП $d^{*} = \max\langle c, x\rangle, x \in \mathbb{R}^{n}, Ax \leqslant b$ размерности (n, m) с целыми коэффициентами разрешима, то у нее существует рацональное рашение $x *$ в шаре: $\| x^{*}\| \leqslant \sqrt{n} \Delta([A|b])$ и $d^{*} = \frac{t}{s}~,~~ t,s \in Z,~~|s| \leqslant \Delta(A)$

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

Методичка, стр. 29

$x^{\varepsilon}$ -- $\varepsilon$ -приближенное решение системы ЛН, если

в строчной записи: $\langle a_i , x^{\varepsilon} \rangle \leqslant b_i + \varepsilon~,~~ \forall i \in [1,m]$
в матричной записи: $Ax^\varepsilon \leqslant b + \varepsilon e$ , где $e$ -- вектор-столбец из единиц

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

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

Методичка, стр. (30-32) 32-33
вики:Метод эллипсоидов

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

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

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

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

Введем функцию невязки в точке x -- $t (x) = max i ((A x) i - b i)$ . Точка $x^{0}=\overline{0}$ -- это центр шара $E 0$ . Если $t(x^{0}) \leqslant 0$ , то $x 0$ -- решение. Если это не так, то возмемем s: $t(x) = \langle a_{s},x^{0}\rangle - b_s$ , значит $x 0$ не удовлетворяет s-ому неравенству системы. Всякий вектор $x$ , удовлетворяющий неравенству s, должен лежать в полупространстве $\leqslant \langle a_s, x^{0}\rangle$ . Пересечение этого полупространства с нашей сферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново.

Теория двойственности ЛП

Методичка, стр. 35-36
http://www.mathelp.spb.ru/book1/lprog5.htm

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

Двойственной задачей к задаче линейного программирования $Ax \leqslant b$ на максимум $\langle c, x\rangle$ (в каноническом виде можно записать: $\max_{x \in \mathbb{R}^n:~Ax \leqslant b} \langle c, x \rangle$ ) называется задача линейного программирования на минимум: $\min_{\lambda \in \mathbb{R}^n:~\lambda A = c,~\lambda \geqslant \overline{0}} \langle \lambda, b \rangle$

Утверждение Двойственная задача к двойственной задаче совпадает с прямой задачей линейного программирования.

Теорема (двойственности ЛП). Задача ЛП разрешима тогда и только тогда, когда разрешима двойственная к ней. При этом в случае разрешимости оптимальные значения целевых функций совпадают: $\max_{x \in \mathbb{R}^n:~Ax \leqslant b} \langle c, x \rangle ~ = ~\min_{\lambda \in \mathbb{R}^n:~\lambda A = c,~\lambda \geqslant \overline{0}} \langle \lambda, b \rangle$

Сведение озЛП к однородной системе уравнений с огрничением x>0

Методичка, стр 36-37

Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейных неравенств.

Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейных уравнений в неотрицательных переменных.

Утверждение. Задача ЛП эквивалентна поиску неотрицательного ненулевого решения однородной системы линейных уравнений.

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

Методичка, стр 37-38
http://logic.pdmi.ras.ru/~yura/modern/02seminar.pdf

Метод Кармаркара.

На основании предыдущего утверждения (см. вопрос о сведении озЛП к однородной системе), есть возможность свести задачу ЛП $\max_{x \in \mathbb{R}^n:~Ax \leqslant b} \langle c, x \rangle$ к поиску решения однородной СЛАУ $\hat{P}y = \hat{q},~ y \geqslant \overline{0}$
Введем функцию Кармаркара: , где
- $N$ -- число столбцов в $P$
- $K$ -- число строк в $P$
- $p_i, ~ i \in [1,K]$ -- строки матрицы $P$ (не $\hat P$ ! описание этой матрицы - в доказательстве утверждения 5 в методичке, стр. 37)
применяя теорему о мере несовместимости и алгоритм округления можно показать, что для решения достаточно найти такой $\hat{x}$ , для которого $k(\hat{x}) \leqslant \frac{1}{3 \left(\Delta(\hat{P})\right)^N}$
при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается.

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

Методичка, стр. 34-35
http://imcs.dvgu.ru/lib/nurmi/finmath/node41.html

Система линейных неравенств $Ax \leqslant b$ называется разрешимой, если $\exists x : ~~ Ax \leqslant b$

Линейное неравенство $\langle c, x\rangle \leqslant d$ является следствием разрешимой системы ЛН $Ax \leqslant b$ , если для всех $x$ , для которых выполняется сама система, выполняется и следствие: $\forall x : Ax \leqslant b ~~ \Rightarrow ~~ \langle c, x\rangle \leqslant d$

Афинная лемма Фаракша. Линейное неравентсво $\langle c, x\rangle \leqslant d$ является следствием разрешимой в вещественный переменных ЛН $Ax \leqslant b$ , тогда и только тогда, когда существует $\lambda \in \mathbb{R}^{m}$ :

$c = \sum_{i \in M} \lambda_i a_i$
$d \geqslant \sum_{i \in M}\lambda_ib_i$
$\lambda_i \geqslant 0 ~~ \forall i \in M$

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

Методичка, стр. 35

Лемма. Система динейный неравенсив $Ax \leqslant b$ неразрешима тогда и только тогда, когда разрешима система:

$\sum_{i \in M}\lambda_i a_i = \overline{0}$ (нулевой вектор)
$\sum_{i \in M}\lambda_i b_i \leqslant -1$
$\lambda_i \geqslant 0 ~~ \forall i \in M$

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

Классификация задач математического программирования. Преимущества выпуклого случая

Методичка. стр 39-41

Задача математического программирования (ЗМП) -- по заданной $f (x)$ найти $\arg \min_{x \in X} f(x)$ , то есть:

найти $x^* \in X : ~~ \forall x \in X ~ \Rightarrow ~ f(x^*) \leqslant f(x)$ -- решение
$f * = f (x *)$ -- (оптимальное) значение целевой функции $f (x)$
где $X$ -- допустимое множество (множество ограничений)

Классификация проводится по типу допустимого множества $X$ :

дискретные (комбинаторные) -- множество $X$ конечно или счётно
целочисленные -- $X \equiv \mathbb{Z}^n$
булевы -- $X \equiv \mathbb{B}^n$
непрерывные -- $X \equiv \mathbb{R}^n$
бесконечномерные
функциональные

Задачи оптимизации бывают:

условные -- $X \subset \mathbb{R}^n$
безусловные -- $X \equiv \mathbb{R}^n$

Классификация по свойствам целевой функции: выпуклость, гладкость и т.п.

Классификация по результату:

локальная оптимизация
глобальная оптимизация

Выпуклое множество (вики) -- такое множество, которое содержит вместе с любыми двумя своими точками еще и отрезок, их соединяющий.

Функция $f$ называется выпуклой, если её надграфик (множество точек над графиком: $\{(x,y):~ y \geqslant f(x) ~ \forall x \in X\}$ ) является выпуклым множеством.

Утверждение. Любая точка локального минимума выпуклой функции является точкой её глобального минимума.

Преимущества выпуклых задач:

применим метод эллипсоидов, причем сложность - полиномиальна
для острых задач (целевая функция убывает в окрестности минимума не медленнее некоторой линейной функции) можно получить точное решение

Формула градиентного метода в задаче безусловной минимизации

Методичка. стр 41-42

Основная идея:

берем некоторое начальное значение
итеративно вычисляем градиент целевой функции
двигаемся в обратном направлении
и так постепенно приходим к (локальному) минимуму функции

Формула градиентного метода -- $x t + 1 = x t - α t grad f (x t)$ , где $α t$ -- шаговый множитель:

пассивный способ: ${α t}$ выбирается заранее
адаптивный способ: {α_t} выбирается в зависимости от реализующейся x_t
- метод скорейшего спуска -- $\alpha_t \in \arg \min_{\alpha > 0} f(x^t - \alpha \mathrm{grad} f(x^t))$
- метод дробления (деления пополам) -- если $f (x t + 1) > f (x t)$ , то возвращаемся к шагу $t$ с новым значением $α t = α t / 2$

Идея метода Ньютона

Методичка, стр. 43

Метод ньютона -- это фактически градиентный спуск с адаптивыным коэффициентом, который берется, как 2 производная целевой функции.

Реально можно вывести формулу Ньютона из разложения по Тейлору до 2 производной в окрестности точки минимума.

Формула метода Ньютона в задаче безусловной минимизации

Методичка. стр 43

Формула Ньютона -- $x^{t+1} = x^t - \frac{1}{f''(x^t)} \mathrm{grad}f(x^t)$ , при этом начальное приближение должно находиться достаточно близко к искомой точке минимума.

Метод ньютона имеет квадратичную скорость сходимости: $\| x^{t+1} - x^* \| \leqslant \frac{1}{Q} (Q \| x^1 - x^* \|)^2$ , где $Q$ - некоторая константа

Ограничения:

невырожденность матрицы 2 производных (гессиана)
близость начального приближения к точке минимума ( $\| x^1 - x^* \| < 1/Q$ )

Идея метода штрафов

Методичка. стр 44

Смысл метода в том, чтобы свести задачу условной оптимизации к задаче безусловной оптимизации, то есть избавится от ограничения на область, в которой ищем минимум.

Для этого вводится так называемая функция штрафа, которая равна нулю в той области, в которой мы "условно оптимизируем" целевую функцию, а в остальных точках добавляет к значению целевой функции некоторое значение (собственно, штраф).

Пример. Пусть область задаётся следующим образом: $X = \{x | g(x) \leqslant 0 \}$ , где $g (x)$ -- некоторая функция. Тогда рассмотрим задачу безусловной минимизации целевой функции $f (x)$ со штрафом: $\min_{x \in \mathbb{R}^n} \{ f(x) + C g(x)^p\}$ , где $C$ -- некоторая константа [??], а $p \geqslant 1$ -- параметр штрафа

Способы решения переборных задач

Методы глобальной минимизации

Методичка. стр. 52 (52-55)

Метод ветвей и границ для глобальной минимизации Липшицевых функций

Методичка. стр. 54

Метод ветвей и границ для ЦЛП. Различные стратегии метода

Методичка. стр. 57

Идея метода ветвей и границ. Пример для задачи БЛП

Методичка. стр. 59

Теорема оптимальности для разложимых функций

Методичка. стр 60

Опр. Функция f называется разделяемой на $f 1$ и $f 2$ , если она представима в виде:

$f (x, y) = f 1 (x, f 2 (y))$ Опр. Функция f называется разложимой на $f 1$ и $f 2$ , если:

она разделяема на $f 1$ и $f 2$
$f 1$ монотонно не убывает по последнему аргументу

Теорема оптимальности для разложимых функций

$min x, y (f (x, y)) = min x (f 1 (x,min y (f 2 (y))))$

Указанная теорема используется для уменьшения размерности оптимизационных задач и в методе ДП.

Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи

Методичка. стр. 62

Метод динамического программирования для БЛП с неотрицательными коэффициентами

Методичка. стр. 63-64

Неотсортировано

Геометрическое описание симплекс-метода
Полиномиальный алгоритм округления ?1-приближенного решения системы линейных неравенств
Понятие о временной сложности алгоритмов
Понятие о недетерминированно-полиномиальных задачах
Оценка сложности метода эллипсоидов ?2-приближенного решения озЛП

Методы оптимизации