Методы Оптимизации, Теормин
Материал из eSyr's wiki.
м (→Элементы математического программирования) |
м (→= Классификация задач математического программирования. Преимущества выпуклого случая) |
||
Строка 220: | Строка 220: | ||
== Элементы математического программирования == | == Элементы математического программирования == | ||
- | === Классификация задач математического программирования. Преимущества выпуклого случая == | + | === Классификация задач математического программирования. Преимущества выпуклого случая === |
''Методичка. стр 39-41'' | ''Методичка. стр 39-41'' | ||
Версия 12:26, 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 |
Материалы
Упражнения
||
Задачи | Определения | Утверждения | Теоремы
||
Теормин | Обозначения
Введение в теорию сложности
Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма.
Массовая задача Π:
- список свободных параметров;
- формулировка свойств, которым должно удовлетворять решение задачи.
Π есть множество индивидуальных задач . Индивидуальная задача получается, если всем параметрам присвоить конкретные значения.
Пусть Σ - конечный алфавит, а Σ * - множество слов в этом алфавите. Отображение e: называется кодировкой задачи П.
Алгоритм A решает массовую задачу Π, если для любой индивидуальной задачи :
- A применим к I, то есть останавливается за конечное число шагов
- A дает решение I
Кодировка задачи P -- такое отобраение , обладающее следующими свойствами:
- Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
- e,e − 1 -- полиномиально вычислимы
- Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 1 и 2 условиям справедливо:
Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания):
Язык алгоритма -- множество слов, принимаемых A, то есть таких, на которых алгоритм останавливается в состоянии qY, что соответсвует "да":
Алгоритм A решает массовую задачу Π, с кодировкой e, если L(e,Π) = L(A)
tA(s) -- число шагов алгоритма A для входа .
Временная сложность .
Задачи распознавания свойств. Классы P и NP.
Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или "нет", в качестве своего решения.
- D(Π) -- множество всех возможных значений параметров массовой задачи.
- Y(Π) -- множество всех индивидуальных задач, ответом на которые является "да".
Класс полиномиально разрешимых задач (P) -- это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом:
- такой, что A решает массовую задачу Π с кодировкой e
- -- полином такой, что
Примеры неполиномиальных задач:
- алгоритмически неразрешимые задачи: такая, что A не применим к I, например,
- 10-я проблема Гильберта: по данному многочлену g с целыми коэффициентами выяснить, имеет ли уравнение g = 0 целочисленное решение
- задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа
- найти все маршруты в задаче коммивояжёра
Класс недетерменированно полиномиальных задач (NP) -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга:
- для НДМТ такой, что решает массовую задачу Π с кодировкой e
- -- полином такой, что
Теорема об экспоненциальной временной оценке для задач из класса NP.
Для любой существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: .
Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.
Дополнительная задача к массовой задаче Π -- задача, получаемая из Π путем введения альтернативного вопроса. То есть если в Π спрашиваем "верно ли x", то в спрашиваем "верно ли, что "
Класс co-P --
- co-P = P.
Класс co-NP -- .
- co-NP = NP пока не удалось ни доказать, ни опровергнуть.
Массовая задача Π допускает хорошую характеризацию, если
- пример такой задачи -- это задача определения простоты числа.
Массовая задача Π' с кодировкой e' полиномиально сводится к задаче Π с кодировкой e, если любая индивидуальная задача может быть сведена за полиномиальное от её длины время к некоторой задаче с сохранением ответа.
Массовая задача Π называется NP-полной (универсальной), если
- принадлежит классу NP:
- любая задача из NP полиномиально сводится к Π:
Класс NPC (NP-complete) -- множество всех NP-полных задач.
Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН
Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачи
Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE
Гипотеза.
Гипотеза. Если для некоторой NP-полной задачи Π дополнительная к ней задача , то NP = co-NP
Класс PSPACE массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти.
Гипотеза. . При этом NP-полные, NP-трудные, NP-эквивалентные задачи
Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке
Псевдополиномиальный алгоритм - полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров.
Пусть M(I) -- некоторая функция, задающая значение числового параметра индивидуальной задачи I. Если таких параметров несколько, в качестве M(I) можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), то M(I) = 0. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкости Tmax(I) = O(p( | I | ,M(I))), где -- некоторый полином от двух переменных.
Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения
Полиномиальное сужение массовой задачи Π -- множество таких индивидуальных задач I, числовые параметры которых не превосходят полинома от длины входа:
Массовая задача Π называется сильно NP-полной, если её полиномиальное сужение является NP-полным.
- задача выполнимости, задача 3-выполнимости -- совпадают со своими полиномиальными сужениями
- задача булевых линейных неравенств
- задача о целочисленном решении системы линейных уравнений
- задача комивояжа
Определение -приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью
Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания
Основы линейного программирования
Определение озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП
ЛП (линейное программирование) -- теория, приложения и методы решения системы линейных неравенств с конечным числом неизвестных : , существует ли , удовлетворяющий данной системе линейных неравентсв
озЛП (основная задача линейного программирования) : найти такой вектор -- решение задачи линейного программирования , максимизирующее линейную функцию
Утверждение (принцип граничных решений). Если озЛП имеет решение, то найдется такая подматрица AI матрицы A, что любое решение системы уравнений AIx = bI реализует максимум c(x).
Алгебраическая сложность -- количество арифметических операций.
Битовая сложность -- количество операций с битами. Битовая сложность задач ЛП, ЛН полиномиальна.
Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остается открытым.
Теорема о границах решений задач ЛП с целыми коэффициентами
Методичка, стр. 28-29
Δ(D) = max | det(D1) | , где D1 -- квадратная подматрица D
Теорема (о границах решений). Если задача озЛП размерности (n, m) с целыми коэффициентами разрешима, то у нее существует рацональное рашение x * в шаре: и
Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами
Методичка, стр. 29
-- -приближенное решение системы ЛН, если
- в строчной записи:
- в матричной записи: , где e -- вектор-столбец из единиц
Теорема. Если система линейных неравенств имеет приближенное решение (), то эта система разрешима, то есть имеет точное решение.
Описание метода эллипсоидов
- Методичка, стр. (30-32) 32-33
- вики:Метод эллипсоидов
Решает задачу линейного программирования за полиномиальное число шагов.
Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.
Лемма1. Если система совместна, то в шаре найдется ее решение.
Таким образом получаем, что если система совместна, то эта лемма позволяет локализовать хотбы бы 1 из ее решений
Введем функцию невязки в точке x -- t(x) = maxi((Ax)i − bi). Точка -- это центр шара E0. Если , то x0 -- решение. Если это не так, то возмемем s: , значит x0 не удовлетворяет s-ому неравенству системы. Всякий вектор x, удовлетворяющий неравенству s, должен лежать в полупространстве . Пересечение этого полупространства с нашей сферой дают полуэлипсоид. Вокруг получившегося полуэлипсоида описываем новую сферу и повторяем алгоритм заново.
Теория двойственности ЛП
- Методичка, стр. 35-36
- http://www.mathelp.spb.ru/book1/lprog5.htm
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче.
Двойственной задачей к задаче линейного программирования на максимум (в каноническом виде можно записать: ) называется задача линейного программирования на минимум:
Утверждение Двойственная задача к двойственной задаче совпадает с прямой задачей линейного программирования.
Теорема (двойственности ЛП). Задача ЛП разрешима тогда и только тогда, когда разрешима двойственная к ней. При этом в случае разрешимости оптимальные значения целевых функций совпадают:
Идея метода Кармаркара
- Методичка, стр (36) 37-38
- http://logic.pdmi.ras.ru/~yura/modern/02seminar.pdf
Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейных неравенств.
Утверждение. Задача ЛП оптимизации эквивалентна решению системы линейных уравнений в неотрицательных переменных.
Утверждение. Задача ЛП эквивалентна поиску неотрицательного ненулевого решения однородной системы линейных уравнений.
Метод Кармаркара.
- На основании предыдущего утверждения, есть возможность свести задачу ЛП к поиску решения однородной СЛАУ
- Введем функцию Кармаркара: , где
- N -- число столбцов в P
- K -- число строк в P
- -- строки матрицы P (не ! описание этой матрицы - в доказательстве утверждения 5 в методичке, стр. 37)
- применяя теорему о мере несовместимости и алгоритм округления можно показать, что для решения достаточно найти такой , для которого
- при этом можно так же показать полиномиальный алгоритм поиска данного приближения, который в курсе не рассматривается.
Следствия систем линейных неравенств. Афинная лемма Фаркаша (без доказательства)
- Методичка, стр. 34-35
- http://imcs.dvgu.ru/lib/nurmi/finmath/node41.html
Система линейных неравенств называется разрешимой, если
Линейное неравенство является следствием разрешимой системы ЛН , если для всех x, для которых выполняется сама система, выполняется и следствие:
Афинная лемма Фаракша. Линейное неравентсво является следствием разрешимой в вещественный переменных ЛН , тогда и только тогда, когда существует :
Лемма Фаркаша о неразрешимости
Методичка, стр. 35
Лемма. Система динейный неравенсив неразрешима тогда и только тогда, когда разрешима система:
- (нулевой вектор)
Элементы математического программирования
Классификация задач математического программирования. Преимущества выпуклого случая
Методичка. стр 39-41
Способы решения переборных задач
Методы глобальной минимизации
Динамическое программирование
Теорема оптимальности для разложимых функций
Опр. Функция f называется разделяемой на f1 и f2, если она представима в виде:
f(x,y) = f1(x,f2(y)) Опр. Функция f называется разложимой на f1 и f2, если:
- она разделяема на f1 и f2
- f1 монотонно не убывает по последнему аргументу
Теорема оптимальности для разложимых функций
minx,y(f(x,y)) = minx(f1(x,miny(f2(y))))
Указанная теорема используется для уменьшения размерности оптимизационных задач и в методе ДП.
Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи
Неотсортировано
- Формула градиентного метода в задаче безусловной минимизации
- Сведение озЛП к однородной системе уравнений с огрничением x>0
- Формула градиентного метода в задаче безусловной минимизации
- Формула метода Ньютона в задаче безусловной минимизации
- Идея метода штрафов
- Геометрическое описание симплекс-метода
- Методы глобальной минимизации
- Полиномиальный алгоритм округления ?1-приближенного решения системы линейных неравенств
- Идея метода эллипсоидов
- Идея метода Ньютона
- Теорема оптимальности для разложимых функций
- Идея метода ветвей и границ. Пример для задачи БЛП
- Метод ветвей и границ для ЦЛП. Различные стратегии метода
- Метод ветвей и границ для глобальной минимизации Липшицевых функций
- Понятие о временной сложности алгоритмов
- Понятие о недетерминированно-полиномиальных задачах
- Метод динамического программирования для БЛП с неотрицательными коэффициентами
- Оценка сложности метода эллипсоидов ?2-приближенного решения озЛП