Порядковая оптимизация - Ordinal optimization

В математическая оптимизация, порядковая оптимизация является максимизацией функций, принимающих значения в частично заказанный набор ("посеть").^[1]^[2]^[3]^[4] Порядковая оптимизация имеет приложения в теории в очереди сети.

Математические основы

Определения

А частичный заказ это бинарное отношение "≤" над набор п который рефлексивный, антисимметричный, и переходный, т.е. для всех а, б, и c в п, у нас есть это:

а ≤ а (рефлексивность);
если а ≤ б и б ≤ а тогда а = б (антисимметрия);
если а ≤ б и б ≤ с тогда а ≤ с (транзитивность).

Другими словами, частичный порядок - это антисимметричный Предварительный заказ.

Набор с частичным порядком называется частично заказанный набор (также называемый посеть). Период, термин заказанный набор иногда также используется для позы, если из контекста ясно, что никакие другие виды заказов не подразумеваются. В частности, полностью упорядоченные множества также можно назвать «упорядоченными множествами», особенно в областях, где эти структуры более распространены, чем посеты.

За а, б отдельные элементы частично упорядоченного множества п, если а ≤ б или же б ≤ а, тогда а и б находятся сопоставимый. В противном случае они несравненный. Если каждые два элемента ЧУМ сравнимы, ЧУМ называется полностью заказанный набор или же цепь (например, натуральные числа по порядку). ЧУМ, в котором каждые два элемента несравнимы, называется антицепь.

Примеры

Стандартные примеры позет, возникающих в математике, включают:

В действительные числа заказано по стандарту меньше или равно отношение ≤ (также вполне упорядоченное множество).
Набор подмножества данного набора (его набор мощности ) заказан включение
Множество подпространств векторное пространство заказал по включению.
Для частично заказанного набора п, то пространство последовательности содержащий все последовательности элементов из п, где последовательность а предшествует последовательности б если каждый элемент в а предшествует соответствующему элементу в б. Формально, $(а п) п \inℕ \leq (б п) п \inℕ$ если и только если $а п \leq б п$ для всех п в ℕ.
Для набора Икс и частично упорядоченный набор п, то функциональное пространство содержащий все функции из Икс к п, куда ж ≤ грамм если и только если ж(Икс) ≤ грамм(Икс) для всех Икс в Икс.
Множество вершин ориентированный ациклический граф заказан достижимость.
Набор натуральные числа оснащен отношением делимость.

Extrema

Есть несколько понятий "наибольший" и "наименьший" элемент в посете. п, а именно:

Величайший элемент и наименьший элемент: элемент грамм в п является наибольшим элементом, если для каждого элемента а в п, а ≤ грамм. Элемент м в п является наименьшим элементом, если для каждого элемента а в п, а ≥ м. У посета может быть только один наибольший или наименьший элемент.
Максимальные элементы и минимальные элементы: элемент грамм в P является максимальным элементом, если нет элемента а в п такой, что а > грамм. Аналогично элемент м в п является минимальным элементом, если нет элемента а в P такое, что а < м. Если ЧУМ имеет наибольший элемент, он должен быть единственным максимальным элементом, но в противном случае может быть более одного максимального элемента, и то же самое для наименьших элементов и минимальных элементов.
Верхняя и нижняя границы: Для подмножества А из п, элемент Икс в п является верхней границей А если а ≤ Икс, для каждого элемента а в А. Особенно, Икс не обязательно быть в А быть верхней границей А. Аналогично элемент Икс в п это нижняя граница А если а ≥ Икс, для каждого элемента а в А. Величайший элемент п является верхней границей п сам, а наименьший элемент является нижней границей п.

Например, рассмотрим натуральные числа, упорядоченные по делимости: 1 - наименьший элемент, так как он делит все другие элементы, но в этом наборе нет ни самого большого элемента, ни каких-либо максимальных элементов: любой грамм делит 2грамм, так что 2грамм больше, чем грамм и грамм не может быть максимальным. Если вместо этого мы рассматриваем только натуральные числа, которые больше 1, то в результирующем poset не будет ни наименьшего элемента, а любого простое число является минимальным элементом. В этом ЧУМ 60 - это верхняя граница (хотя и не наименьшая верхняя граница) {2,3,5}, а 2 - нижняя граница {4,6,8,12}.

Дополнительная конструкция

Во многих таких случаях poset имеет дополнительную структуру: например, poset может быть решетка или частично упорядоченная алгебраическая структура.

Решетки

А посеть (L, ≤) является решетка если он удовлетворяет следующим двум аксиомам.

Существование бинарных объединений: Для любых двух элементов а и б из L, набор {а, б} имеет присоединиться: ${displaystyle alor b}$ (также известный как наименьшая верхняя граница или супремум).
Существование двоичного кода встречается: Для любых двух элементов а и б из L, набор {а, б} имеет встретить: ${displaystyle aland b}$ (также известный как точная нижняя грань или точная нижняя грань).

Присоединение и встреча а и б обозначаются ${displaystyle alor b}$ и ${displaystyle aland b}$ , соответственно. Это определение делает ${displaystyle lor}$ и ${displaystyle land}$ бинарные операции. Первая аксиома гласит, что L это стыковочная полурешетка; второй говорит, что L это встречная полурешетка. Обе операции монотонны по порядку: а₁ ≤ а₂ и б₁ ≤ б₂ означает, что₁ ${displaystyle lor}$ б₁ ≤ а₂ ${displaystyle lor}$ б₂ и₁ ${displaystyle land}$ б₁ ≤ а₂ ${displaystyle land}$ б₂.

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

А ограниченная решетка имеет величайший (или максимум) и наименее (или минимальный) элемент, условно обозначаемый 1 и 0 (также называемый верх и Нижний). Любую решетку можно превратить в ограниченную, добавив наибольший и наименьший элементы, и каждая непустая конечная решетка ограничена, взяв соединение (соответственно, пересечение) всех элементов, обозначенное ${displaystyle igvee A = a_ {1} lor cdots lor a_ {n}}$ (соотв. ${displaystyle igwedge A = a_ {1} land cdots land a_ {n}}$ ) куда ${displaystyle A = {a_ {1}, ldots, a_ {n}}}$ .

ЧУМ является ограниченной решеткой тогда и только тогда, когда каждый конечный набор элементов (включая пустой набор) имеет соединение и пересечение. Здесь объединение пустого набора элементов определяется как наименьший элемент ${displaystyle igvee varnothing = 0}$ , а встреча пустого множества определяется как наибольший элемент ${displaystyle igwedge varnothing = 1}$ . Это соглашение согласуется с ассоциативностью и коммутативностью функции meet and join: объединение объединения конечных множеств равно объединению объединений множеств, и, соответственно, объединение объединения конечных множеств равно объединению встреч множеств, т. е. для конечных подмножеств А и B посета L,

{displaystyle igvee left (Acup Bight) = left (igvee Aight) vee left (igvee Bight)}

и

{displaystyle igwedge left (Acup Bight) = left (igwedge Aight) клин влево (igwedge Bight)}

держать. Принимая B быть пустым множеством,

{displaystyle igvee left (Acup emptyset ight) = left (igvee Aight) vee left (igvee emptyset ight) = left (igvee Aight) vee 0 = igvee A}

и

{displaystyle igwedge left (Acup emptyset ight) = left (igwedge Aight) клин влево (igwedge emptyset ight) = left (igwedge Aight) клин 1 = igwedge A}

что согласуется с тем, что ${displaystyle Acup emptyset = A}$ .

Упорядоченная алгебраическая структура

Посет может быть частично упорядоченная алгебраическая структура.^[5]^[6]^[1]^[7]^[8]^[9]^[10]

В алгебра, упорядоченная полугруппа это полугруппа (S, •) вместе с частичный заказ ≤ то есть совместимый с операцией полугруппы, что означает, что Икс ≤ у следует z • x ≤ z • y и x • z ≤ y • z для всех Икс, у, z в S. Если S является группа и упорядочена как полугруппа, получаем понятие упорядоченная группа, и аналогично, если S является моноид это можно назвать заказанный моноид. Частично упорядоченные векторные пространства и векторные решетки важны в оптимизация с несколькими целями.^[11]

Порядковая оптимизация в информатике и статистике

Проблемы порядковой оптимизации возникают во многих дисциплинах. Компьютерные ученые изучать алгоритмы выбора, которые проще, чем алгоритмы сортировки.^[12]^[13]

Статистическая теория принятия решений изучает «проблемы отбора», которые требуют определения «лучшей» субпопуляции или определения «почти лучшей» субпопуляции.^[14]^[15]^[16]^[17]^[18]

Приложения

С 1960-х годов область порядковой оптимизации расширилась как в теории, так и в приложениях. Особенно, антиматроиды и "макс-плюс алгебра "нашли применение в сетевой анализ и теория массового обслуживания, особенно в сетях массового обслуживания и дискретно-событийные системы.^[19]^[20]^[21]

Смотрите также

дальнейшее чтение

Фудзишигэ, Сатору Субмодульные функции и оптимизация. Второе издание. Annals of Discrete Mathematics, 58. Elsevier B.V., Амстердам, 2005. xiv + 395 с. ISBN 0-444-52086-4
Гондран, Мишель; Мину, Мишель Графики, дииды и полукольца. Новые модели и алгоритмы. Серия исследований операций / интерфейсов компьютерных наук, 41. Springer, New York, 2008. xx + 383 pp. ISBN 978-0-387-75449-9
Dietrich, B.L .; Хоффман, А. Дж. О жадных алгоритмах, частично упорядоченных множествах и субмодулярных функциях. IBM J. Res. Dev. 47 (2003), нет. 1, 25–30.
Мурота, Кадзуо Дискретный выпуклый анализ. Монографии SIAM по дискретной математике и приложениям. Общество промышленной и прикладной математики (SIAM), Филадельфия, Пенсильвания, 2003. xxii + 389 с. ISBN 0-89871-540-7
Топкис, Дональд М. Супермодульность и дополнительность. Границы экономических исследований. Princeton University Press, Princeton, NJ, 1998. xii + 272 с. ISBN 0-691-03244-0
Певец Иван Абстрактный выпуклый анализ. Серия монографий и продвинутых текстов Канадского математического общества. Публикация Wiley-Interscience. John Wiley & Sons, Inc., Нью-Йорк, 1997. xxii + 491 с. ISBN 0-471-16015-6
Бьёрнер, Андерс; Циглер, Гюнтер М. Введение в гридоиды. Приложения Matroid, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Кембридж, 1992 г.,
Циммерманн, У. Линейная и комбинаторная оптимизация в упорядоченных алгебраических структурах. Анна. Дискретная математика. 10 (1981), viii + 380 с.
Cuninghame-Green, Раймонд Минимаксная алгебра. Конспект лекций по экономике и математическим системам, 166. Springer-Verlag, Berlin-New York, 1979. xi + 258 с. ISBN 3-540-09113-0
Баччелли, Франсуа Луи; Коэн, Гай; Ольсдер, Герт Ян; Квадрат, Жан-Пьер (1992). Синхронизация и линейность: алгебра для дискретных систем событий. Ряд Уайли в вероятности и математической статистике: вероятность и математическая статистика. Чичестер: John Wiley & Sons, Ltd., стр. Xx + 489. ISBN 0-471-93609-X. МИСТЕР 1204266.
Глассерман, Пол; Яо, Дэвид Д. (1994). Монотонная структура в дискретно-событийных системах. Ряд Уайли в вероятности и математической статистике: прикладная вероятность и статистика. Нью-Йорк: John Wiley & Sons, Inc., стр. Xiv + 297. ISBN 0-471-58041-4. МИСТЕР 1266839.
Хайдерготт, Бернд; Олдсер, Герт Ян; ван дер Вуде, Джейкоб (2006). Max plus в работе: моделирование и анализ синхронизированных систем, курс по алгебре max-plus и ее приложениям. Принстонская серия по прикладной математике. Принстон, Нью-Джерси: Издательство Принстонского университета. С. xii + 213. ISBN 978-0-691-11763-8. МИСТЕР 2188299.
Хо, Ю., Шринивас, Р., Вакили, П., "Порядковая оптимизация динамических систем с дискретными событиями", J. of DEDS 2 (2), 61-88, (1992).
Аллен, Эрик и Мария Д. Илич. Решения об обязательствах на основе цены на рынке электроэнергии. Достижения в промышленном контроле. Лондон: Springer, 1999. ISBN 978-1-85233-069-9

внешняя ссылка

Аннотированная библиография по порядковой оптимизации к Ю-Чи Хо

[dh03-1] а ^б Дитрих, Б.Л.; Хоффман, А. Дж. О жадных алгоритмах, частично упорядоченных наборах и субмодульных функциях. IBM J. Res. Dev. 47 (2003), нет. 1, 25–30.

[2] Топкис, Дональд М. Супермодульность и дополнительность. Границы экономических исследований. Princeton University Press, Princeton, NJ, 1998. xii + 272 с. ISBN 0-691-03244-0

[3] Певец Иван Абстрактный выпуклый анализ. Серия монографий и продвинутых текстов Канадского математического общества. Публикация Wiley-Interscience. John Wiley & Sons, Inc., Нью-Йорк, 1997. xxii + 491 с. ISBN 0-471-16015-6

[4] Бьёрнер, Андерс; Циглер, Гюнтер М. Введение в гридоиды. Приложения Matroid, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Кембридж, 1992 г.,

[5] Фудзишигэ, Сатору Субмодульные функции и оптимизация. Второе издание. Annals of Discrete Mathematics, 58. Elsevier B.V., Амстердам, 2005. xiv + 395 с. ISBN 0-444-52086-4

[6] Гондран, Мишель; Мину, Мишель Графики, дииды и полукольца. Новые модели и алгоритмы. Серия исследований операций / интерфейсов компьютерных наук, 41. Springer, New York, 2008. xx + 383 pp. ISBN 978-0-387-75449-9

[7] Мурота, Кадзуо Дискретный выпуклый анализ. Монографии SIAM по дискретной математике и приложениям. Общество промышленной и прикладной математики (SIAM), Филадельфия, Пенсильвания, 2003. xxii + 389 с. ISBN 0-89871-540-7

[8] Топкис, Дональд М. Супермодульность и дополнительность. Границы экономических исследований. Princeton University Press, Princeton, NJ, 1998. xii + 272 с. ISBN 0-691-03244-0

[9] Циммерманн, У. Линейная и комбинаторная оптимизация в упорядоченных алгебраических структурах. Анна. Дискретная математика. 10 (1981), viii + 380 с.

[10] Cuninghame-Green, Раймонд Минимаксная алгебра. Конспект лекций по экономике и математическим системам, 166. Springer-Verlag, Berlin-New York, 1979. xi + 258 pp. ISBN 3-540-09113-0

[11] Зэлинеску, К. (2002). Выпуклый анализ в общих векторных пространствах. Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc., стр. Xx + 367. ISBN 981-238-067-1. МИСТЕР 1921556.

[12] Дональд Кнут. Искусство программирования, Том 3: Сортировка и поиск, Третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89685-0. Раздел 5.3.3: Выбор минимального сравнения, стр.207–219.

[13] Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7. Глава 9: Медианы и статистика порядка, стр. 183–196. Раздел 14.1: Динамическая статистика заказов, стр. 302–308.

[14] Гиббонс, Джин Дикинсон; Олкин, Ингрэм, и Собел, Милтон, Выбор и упорядочивание популяций, Wiley, (1977). (Переиздано SIAM как "Классик прикладной математики".)

[15] Gupta, Shanti S .; Панчапакесан, С. (1979). Процедуры множественных решений: теория и методология отбора и ранжирования популяций. Ряд Уайли по вероятности и математической статистике. Нью-Йорк: Джон Вили и сыновья. С. XXV + 573. ISBN 0-471-05177-2. МИСТЕР 0555416. (Переиздано SIAM как "Классик прикладной математики".)

[16] Сантнер, Томас Дж., И Тамане, А. К., Планирование экспериментов: ранжирование и отбор, М. Деккер, (1984).

[17] Роберт Э. Беххофер, Томас Дж. Сантнер, Дэвид М. Голдсман. Планирование и анализ экспериментов для статистического отбора, скрининга и множественных сравнений. Джон Вили и сыновья, 1995.

[18] Фридрих Лизе, Клаус-Дж. Miescke. 2008 г. Статистическая теория принятия решений: оценка, тестирование и выбор. Springer Verlag.

[19] Глассерман, Пол; Яо, Дэвид Д. (1994). Монотонная структура в дискретно-событийных системах. Ряд Уайли в вероятности и математической статистике: прикладная вероятность и статистика. Нью-Йорк: John Wiley & Sons, Inc., стр. Xiv + 297. ISBN 0-471-58041-4. МИСТЕР 1266839.

[20] Баччелли, Франсуа Луи; Коэн, Гай; Ольсдер, Герт Ян; Квадрат, Жан-Пьер (1992). Синхронизация и линейность: алгебра для дискретных систем событий. Ряд Уайли в вероятности и математической статистике: вероятность и математическая статистика. Чичестер: John Wiley & Sons, Ltd., стр. Xx + 489. ISBN 0-471-93609-X. МИСТЕР 1204266.

[21] Хайдерготт, Бернд; Олдсер, Герт Ян; ван дер Вуде, Джейкоб (2006). Max plus в работе: моделирование и анализ синхронизированных систем, курс по алгебре max-plus и ее приложениям. Принстонская серия по прикладной математике. Принстон, Нью-Джерси: Издательство Принстонского университета. С. xii + 213. ISBN 978-0-691-11763-8. МИСТЕР 2188299.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]