Проблема оптимизации

В математике , технике , информатике и экономике задача оптимизации — это проблема поиска наилучшего решения из всех возможных решений .

Задачи оптимизации можно разделить на две категории в зависимости от того, ли переменные являются непрерывными или дискретными :

Задача оптимизации с дискретными переменными известна как дискретная оптимизация , в которой объект , такой как целое число , перестановка или график, должен быть найден из счетного множества .
Задача с непрерывными переменными известна как непрерывная оптимизация оптимальное значение непрерывной функции , в которой необходимо найти . Они могут включать проблемы с ограничениями и мультимодальные проблемы.

Проблема непрерывной оптимизации

Стандартная форма задачи непрерывной оптимизации: ^[1] ${\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}$ где

$ж : ℝ н \to ℝ$ — целевая функция , которую необходимо минимизировать по $вектору n$ -переменной $x$ ,
$g i (x) \leq 0$ называются неравенствами . ограничениями-
$h j (x) = 0$ называются ограничениями равенства , а
$м \geq 0$ и $р \geq 0$ .

Если $m = p = 0$ , проблема является проблемой неограниченной оптимизации. По соглашению стандартная форма определяет задачу минимизации . Задачу максимизации можно решить путем отрицания целевой функции.

Задача комбинаторной оптимизации

Формально комбинаторной оптимизации задача $A$ представляет собой четверную задачу ^{[ нужна ссылка ]} $(я, ж, м, г)$ , где

$Я$ — набор экземпляров;
для данного экземпляра $x \in I$ ; $f (x)$ — множество допустимых решений
учитывая экземпляр $x$ допустимое решение $y$ x $y$ , $m (x, y)$ обозначает меру , $и$ которая обычно является положительным действительным числом .
$g$ — целевая функция, равная $min$ или $max$ .

Цель состоит в том, чтобы найти для некоторого случая $x$ оптимальное решение , то есть допустимое решение $y$ с $m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.$

Для каждой задачи комбинаторной оптимизации существует соответствующая проблема принятия решения , которая спрашивает, существует ли допустимое решение для некоторой конкретной меры $m 0$ . Например, если существует граф $G$ , который содержит вершины $u$ и $v$ , задача оптимизации может заключаться в том, чтобы «найти путь от $u$ до $v$ , который использует наименьшее количество ребер». Ответом на эту задачу может быть, скажем, 4. Соответствующей проблемой решения будет: «Существует ли путь от $u$ до $v$ , который использует 10 или меньше ребер?» На эту проблему можно ответить простым «да» или «нет».

В области аппроксимационных алгоритмов алгоритмы предназначены для поиска почти оптимальных решений сложных задач. Обычная версия решения в таком случае является неадекватным определением проблемы, поскольку она указывает только приемлемые решения. Несмотря на то, что мы могли бы ввести подходящие задачи решения, эту проблему более естественно охарактеризовать как задачу оптимизации. ^[2]

См. также

Задача подсчета (сложность) - Тип вычислительной задачи.
Оптимизация дизайна
Вариационный принцип Экланда - теорема, утверждающая, что существуют почти оптимальные решения некоторых задач оптимизации.
Функциональная проблема - Тип вычислительной задачи
Проблема с перчатками
Исследование операций - Дисциплина, касающаяся применения передовых аналитических методов.
Удовлетворение – когнитивная эвристика поиска приемлемого решения – не обязательно искать оптимальное решение, достаточно найти «достаточно хорошее» решение.
Проблема поиска — тип вычислительной задачи, представленный бинарным отношением.
Полубесконечное программирование - задача оптимизации с конечным числом переменных и бесконечным числом ограничений или бесконечным числом переменных и конечным числом ограничений.

Ссылки

^ Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (pdf) . Издательство Кембриджского университета. п. 129. ИСБН 978-0-521-83378-3 .
^ Озиелло, Джорджо; и др. (2003), Сложность и аппроксимация (исправленная редакция), Springer, ISBN 978-3-540-65431-5

Внешние ссылки

«Как формирование трафика оптимизирует пропускную способность сети» . МПК . 12 июля 2016 года . Проверено 13 февраля 2017 г. .

[1] Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (pdf) . Издательство Кембриджского университета. п. 129. ИСБН 978-0-521-83378-3 .

[Ausiello03-2] Озиелло, Джорджо; и др. (2003), Сложность и аппроксимация (исправленная редакция), Springer, ISBN 978-3-540-65431-5

[1]

[2]

v т и Выпуклый анализ и вариационный анализ
Основные понятия	Выпуклая комбинация Выпуклая функция Выпуклый набор
Темы (список)	Теория Шоке Выпуклая геометрия Выпуклое метрическое пространство Выпуклая оптимизация Двойственность Множитель Лагранжа Преобразование Лежандра Локально выпуклое топологическое векторное пространство Симплекс
Карты	Выпуклое сопряжение Вогнутый ( Закрыто К- Логарифмически Правильный Псевдо- Квази- ) Выпуклая функция Функция инвекс Преобразование Лежандра Полунепрерывность Субпроизводная
Основные результаты (список)	Теорема Каратеодори Вариационный принцип Экланда Теорема Феннеля – Моро Неравенство Фенхеля-Янга Неравенство Дженсена Неравенство Эрмита–Адамара. Теорема Крейна – Милмана Лемма Мазура Лемма Шепли – Фолкмана. Робинсон-Урсеску Саймонс Урсеску
Наборы	Выпуклая оболочка ( Ортогонально , Псевдо- ) Выпуклое множество Эффективный домен Эпиграф Гипограф Джон эллипсоид Объектив Радиальное множество / Алгебраическая внутренняя часть Зонотоп
Ряд	Связанные выпуклые ряды ( (cs, lcs)-замкнутые , (cs, bcs)-полные , (нижние) идеально выпуклые , (H x ) и (Hw x ) )
Двойственность	Двойная система Разрыв двойственности Сильная двойственность Слабая двойственность
Приложения и сопутствующее	Выпуклость в экономике