Лексикографическая оптимизация

Лексикографическая оптимизация — это разновидность многокритериальной оптимизации . В общем, многокритериальная оптимизация имеет дело с задачами оптимизации, в которых две или более целевые функции подлежат оптимизации одновременно. Часто различные цели можно ранжировать в порядке важности для лица, принимающего решения, так что цель $f_{1}$ является наиболее важной и объективной $f_{2}$ является следующим по важности и так далее. Лексикографическая оптимизация предполагает, что лицо, принимающее решения, предпочитает даже очень небольшое увеличение $f_{1}$ , даже к очень большому увеличению $f_{2},f_{3},f_{4},$ и т. д. Точно так же лицо, принимающее решение, предпочитает даже очень небольшое увеличение $f_{2}$ , даже к очень большому увеличению $f_{3},f_{4},$ и т. д. Другими словами, лицо, принимающее решения, имеет лексикографические предпочтения , ранжируя возможные решения в соответствии с лексикографическим порядком значений их целевой функции. Лексикографическую оптимизацию иногда называют упреждающей оптимизацией . ^[1] поскольку небольшое увеличение одной объективной ценности предвосхищает гораздо большее увеличение менее важных объективных ценностей.

В качестве примера рассмотрим компанию, которая ставит безопасность превыше всего. Компания хочет максимизировать безопасность своих работников и клиентов. При условии достижения максимально возможной безопасности он хочет максимизировать прибыль. Эта фирма выполняет лексикографическую оптимизацию, где $f_{1}$ означает безопасность и $f_{2}$ обозначает прибыль.

В качестве другого примера: ^[2] в управлении проектами при анализе сетей PERT часто хочется минимизировать среднее время завершения и при этом минимизировать дисперсию времени завершения.

Обозначения

Задачу лексикографической максимизации часто записывают так: ${\begin{aligned}\operatorname {lex} \max &&f_{1}(x),f_{2}(x),\ldots ,f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$ где $f_{1},\ldots ,f_{n}$ функции, которые необходимо максимизировать, упорядочены от наиболее важных к наименее важным; $x$ – вектор переменных решения; и $X$ - допустимое множество множество возможных значений $x$ . Аналогично можно определить задачу лексикографической минимизации.

Алгоритмы

Существует несколько алгоритмов решения задач лексикографической оптимизации. ^[3]

Последовательный алгоритм для общих целей

Задача оптимизации лексиминов с n целями может быть решена с использованием последовательности из n задач одноцелевой оптимизации следующим образом: ^[1]^[3]^{: Алг.1}

Для t = 1,...,n делаем
- Решите следующую однокритериальную задачу: ${\begin{aligned}\max ~~~f_{t}(x)\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{ for all }}k{\text{ in }}1,\ldots ,t-1.\end{aligned}}$
- Если проблема неосуществима или неограниченна, остановитесь и заявите, что решения нет.
- В противном случае подставьте значение оптимального решения в $z_{t}$ и продолжить.
Конец на

Итак, на первой итерации мы находим максимально возможное значение наиболее важной цели. $f_{1}(x)$ и поместите это максимальное значение в $z_{1}$ . На второй итерации мы находим максимально возможное значение второй по важности цели. $f_{2}(x)$ с дополнительным ограничением, согласно которому наиболее важная цель должна сохранять максимальное значение $z_{1}$ ; и так далее.

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

Лексикографический симплексный алгоритм для линейных целей

Линейная лексикографическая оптимизация ^[2] является частным случаем лексикографической оптимизации, в котором цели линейны, а допустимое множество описывается линейными неравенствами. Это можно записать как: ${\begin{aligned}\operatorname {lex} \max &&c_{1}\cdot x,c_{2}\cdot x,\ldots ,c_{n}\cdot x\\{\text{subject to}}&&A\cdot x\leq b,x\geq 0\end{aligned}}$ где $c_{1},\ldots ,c_{n}$ — векторы, представляющие линейные цели, которые необходимо максимизировать, упорядоченные от наиболее к наименее важным; $x$ – вектор переменных решения; а допустимое множество определяется матрицей $A$ и вектор $b$ .

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

Средневзвешенное значение для линейных целей

Шерали и Сойстер ^[1] докажите, что для любой задачи линейной лексикографической оптимизации существует набор весов $w_{1}>w_{2}>\cdots >w_{n}$ такая, что множество лексикографически-оптимальных решений идентично множеству решений следующей однокритериальной задачи: ${\begin{aligned}\max &&w_{1}f_{1}(x)+\cdots +w_{n}f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$ Один из способов вычисления весов предложен Ягером . ^[4] Он предполагает, что все объективные значения являются действительными числами от 0 до 1, а наименьшая разница между любыми двумя возможными значениями — это некоторая константа d < 1 (так что значения с разницей меньше d считаются равными). Тогда вес $w_{t}$ из $f_{t}(x)$ установлено приблизительно $d^{t}$ . Это гарантирует, что максимизация взвешенной суммы $\sum _{t}w_{t}f_{t}(x)$ эквивалентно лексикографической максимизации.

Кокоччони, Паппалардо и Сергеев ^[5] покажите, что, имея компьютер, который может выполнять числовые вычисления с бесконечно малыми числами , можно выбирать веса, которые являются бесконечно малыми (в частности: $w_{1}=1$ ; $w_{2}$ бесконечно мал; $w_{3}$ имеет бесконечно малый квадрат; и т. д.), и таким образом свести линейную лексикографическую оптимизацию к одноцелевому линейному программированию с бесконечно малыми числами. Они представляют адаптацию симплексного алгоритма к бесконечно малым числам и представляют несколько работающих примеров.

Характеристики

(1) Уникальность . В общем, задача лексикографической оптимизации может иметь более одного оптимального решения. Однако, если $x^{1}$ и $x^{2}$ являются двумя оптимальными решениями, то их значения должны быть одинаковыми, т. е. $f_{i}(x^{1})=f_{i}(x^{2})$ для всех $i\in [n]$ . ^[3]^{: Thm.2} Более того, если допустимая область представляет собой выпуклое множество , а целевые функции строго вогнутые , то задача имеет не более одного оптимального решения, поскольку если бы существовало два разных оптимальных решения, их среднее было бы другим допустимым решением, в котором целевые функции достигают более высокого значения, что противоречит оптимальности исходного решения.

(2) Частичные суммы . Учитывая вектор $f_{1},\ldots ,f_{n}$ функций для оптимизации, для всех t в 1,..., n определите $f_{1..t}:=\sum _{i=1}^{t}f_{i}$ = сумма всех функций от самой важной до t -й по важности. Тогда исходная задача лексикографической оптимизации эквивалентна следующей: ^[3]^{: Thm.4} ${\begin{aligned}\operatorname {lex} \max &&f_{1...1}(x),f_{1..2}(x),\ldots ,f_{1..n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$ В некоторых случаях вторую проблему решить проще.

См. также

Лексикографическая максим-минутная оптимизация — это вариант лексикографической оптимизации, в котором все цели одинаково важны, а цель состоит в том, чтобы максимизировать наименьшую цель, затем вторую наименьшую цель и так далее.
В теории игр ядрышко определяется как лексикографически минимальное множество решений. ^[6]

Ссылки

^ Jump up to: ^а ^б ^с Шерали, HD; Сойстер, Алабама (1 февраля 1983 г.). «Упреждающее и невытесняющее многоцелевое программирование: взаимосвязь и контрпримеры» . Журнал теории оптимизации и приложений . 39 (2): 173–186. дои : 10.1007/BF00934527 . ISSN 1573-2878 .
^ Jump up to: ^а ^б ^с Изерманн, Х. (1 декабря 1982 г.). «Линейная лексикографическая оптимизация» . Операции-Исследования-Спектр . 4 (4): 223–228. дои : 10.1007/BF01782758 . ISSN 1436-6304 .
^ Jump up to: ^а ^б ^с ^д Огрычак, В.; Пиоро, М.; Томашевский, А. (2005). «Проектирование телекоммуникационной сети и задача максим-мин оптимизации» . Журнал телекоммуникаций и информационных технологий . 3 : 43–56. ISSN 1509-4553 .
^ Ягер, Рональд Р. (1 октября 1997 г.). «Об аналитическом представлении упорядочения Лексимина и его применении к гибкому распространению ограничений» . Европейский журнал операционных исследований . 102 (1): 176–192. дои : 10.1016/S0377-2217(96)00217-2 . ISSN 0377-2217 .
^ Кокоччони, Марко; Паппалардо, Массимо; Сергеев, Ярослав Д. (01.02.2018). «Лексикографическое многокритериальное линейное программирование с использованием методологии Гроссона: Теория и алгоритм» . Прикладная математика и вычислительная техника . Последние тенденции в числовых вычислениях: теория и алгоритмы. 318 : 298–311. дои : 10.1016/j.amc.2017.05.058 . hdl : 11568/877746 . ISSN 0096-3003 .
^ Кольберг, Илон (1 июля 1972 г.). «Ядрышко как решение задачи минимизации» . SIAM Journal по прикладной математике . 23 (1): 34–39. дои : 10.1137/0123004 . ISSN 0036-1399 .

[:3-1] Jump up to: ^а ^б ^с Шерали, HD; Сойстер, Алабама (1 февраля 1983 г.). «Упреждающее и невытесняющее многоцелевое программирование: взаимосвязь и контрпримеры» . Журнал теории оптимизации и приложений . 39 (2): 173–186. дои : 10.1007/BF00934527 . ISSN 1573-2878 .

[:1-2] Jump up to: ^а ^б ^с Изерманн, Х. (1 декабря 1982 г.). «Линейная лексикографическая оптимизация» . Операции-Исследования-Спектр . 4 (4): 223–228. дои : 10.1007/BF01782758 . ISSN 1436-6304 .

[:0-3] Jump up to: ^а ^б ^с ^д Огрычак, В.; Пиоро, М.; Томашевский, А. (2005). «Проектирование телекоммуникационной сети и задача максим-мин оптимизации» . Журнал телекоммуникаций и информационных технологий . 3 : 43–56. ISSN 1509-4553 .

[4] Ягер, Рональд Р. (1 октября 1997 г.). «Об аналитическом представлении упорядочения Лексимина и его применении к гибкому распространению ограничений» . Европейский журнал операционных исследований . 102 (1): 176–192. дои : 10.1016/S0377-2217(96)00217-2 . ISSN 0377-2217 .

[5] Кокоччони, Марко; Паппалардо, Массимо; Сергеев, Ярослав Д. (01.02.2018). «Лексикографическое многокритериальное линейное программирование с использованием методологии Гроссона: Теория и алгоритм» . Прикладная математика и вычислительная техника . Последние тенденции в числовых вычислениях: теория и алгоритмы. 318 : 298–311. дои : 10.1016/j.amc.2017.05.058 . hdl : 11568/877746 . ISSN 0096-3003 .

[6] Кольберг, Илон (1 июля 1972 г.). «Ядрышко как решение задачи минимизации» . SIAM Journal по прикладной математике . 23 (1): 34–39. дои : 10.1137/0123004 . ISSN 0036-1399 .

[1]

[2]

[3]

[4]

[5]

[6]