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

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

Версия от 21:41, 8 июня 2009; StepLg (Обсуждение | вклад)

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

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.

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

Для любой $\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-приближенного решения озЛП

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