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

Лексикографическая оптимизация максимального порядка (также называемая лексмаксмин или лексимин или лексимакс или лексикографическая оптимизация максимального порядка ) — это разновидность многокритериальной оптимизации . В общем, многокритериальная оптимизация имеет дело с задачами оптимизации, в которых две или более целевые функции подлежат оптимизации одновременно. Оптимизация Lexmaxmin предполагает, что лицо, принимающее решения, хочет, чтобы наименьшее целевое значение было как можно выше; при этом вторая по величине цель должна быть как можно выше; и так далее. Другими словами, лицо, принимающее решения, ранжирует возможные решения в соответствии с лексимным порядком значений их целевой функции.

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

Алгоритмы оптимизации lexmaxmin (без использования этого названия) были разработаны для вычисления ядрышка кооперативной игры. Раннее применение lexmaxmin было представлено Мелвином Дрешером. в своей книге по теории игр , в контексте максимального использования ошибок противника в игре с нулевой суммой . Берингер приводит множество других примеров из теории игр, а также теории принятия решений .

Обозначения

Задача lexmaxmin может быть записана как: $${\begin{aligned}\operatorname {lex} \max \min &&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$.

Сравнение с лексикографической оптимизацией

Оптимизация Lexmaxmin тесно связана с лексикографической оптимизацией . Однако в лексикографической оптимизации существует фиксированный порядок функций, такой что $f_{1}$ является самым важным, $f_{2}$ является следующим по важности и так далее. Напротив, в lexmaxmin все цели одинаково важны. Чтобы представить lexmaxmin как частный случай лексикографической оптимизации, обозначим через $f_{[1]}(x):=\min(f_{1}(x),\ldots ,f_{n}(x))=$ наименьшее целевое значение в x . Аналогично обозначим через $f_{[2]}(x):=$ второе по величине целевое значение по x и т. д., так что $f_{[1]}(x)\leq f_{[2]}(x)\leq \cdots \leq f_{[n]}(x)$. Тогда задачу оптимизации lexmaxmin можно записать как следующую задачу лексикографической максимизации: $${\begin{aligned}\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$$

Уникальность

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

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

Алгоритмы для непрерывных переменных

Алгоритм насыщения для выпуклых задач

Алгоритм насыщения работает, когда допустимое множество является выпуклым , а цели — вогнутыми функциями . Варианты этого алгоритма появляются во многих статьях. Самое раннее появление приписывается Александру Копеловицу. Элькинд и Пасечник. Другие варианты появляются в.

Алгоритм сохраняет набор целей, которые считаются насыщенными (также называемые блокировкой ). Это означает, что их ценность не может быть повышена без ущерба для менее ценных целей. Остальные цели называются свободными . Изначально все цели бесплатны. В целом алгоритм работает следующим образом:

• Хотя некоторые цели бесплатны:
  • (P1) Решите следующую однокритериальную задачу, где $z_{k}$ значение насыщения цели $f_{k}$: $${\begin{aligned}\max ~~~z\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)=z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z{\text{ for all free objectives }}k\end{aligned}}$$
  • Если проблема неосуществима или неограниченна, остановитесь и заявите, что решения нет.
  • В противном случае, пусть $z_{\max }$ быть максимальным значением первой задачи.
  • Ищите бесплатные цели, ценность которых не может увеличиться выше $z_{\max }$ без уменьшения какой-либо другой цели ниже $z_{\max }$. В любом решении lexmaxmin значение любой такой цели должно быть точно $z_{\max }$. Добавьте все такие цели в набор насыщенных целей, установите для них значение насыщенности $z_{\max }$и вернитесь к (P1).

Осталось объяснить, как мы можем находить новые насыщенные цели на каждой итерации.

Способ 1: оптимизаторы интерьера . Внутренний оптимизатор линейной программы — это оптимальное решение, при котором наименьшее возможное количество ограничений является жестким. Другими словами, это решение в интерьере оптимального лица. Внутренний оптимизатор (P1) можно найти, решив (P1) с использованием метода эллипсоида или метода внутренней точки .

Набор жестких ограничений во внутреннем оптимизаторе уникален. Доказательство . Предположим от противного, что существуют два внутренних оптимизатора, x1 и x2, с разными наборами жестких ограничений. Поскольку допустимое множество выпукло, среднее решение x3 = (x1+x2)/2 также является оптимизатором. Любое ограничение, которое не является жестким ни по x1, ни по x2, не является жестким по x3. Следовательно, количество жестких ограничений в x3 меньше, чем в x1 и x2, что противоречит определению внутреннего оптимизатора.

Следовательно, набор жестких ограничений во внутреннем оптимизаторе соответствует набору свободных целей, которые становятся насыщенными. Используя этот метод, решение лексимина можно вычислить не более чем за n итераций.

Метод 2: перебор всех целей . Найти хотя бы одну насыщенную цель можно, используя следующий алгоритм.

• Для каждой свободной цели $f_{j}$:
  • (P2) Решите следующую однокритериальную задачу: $${\begin{aligned}\max ~~~f_{j}(x)\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z_{\max }{\text{ for all free objectives }}k\end{aligned}}$$
  • Если оптимальное значение равно $z_{\max }$ цель j становится насыщенной. , то с этого момента
  • В противном случае оптимальное значение должно быть больше, чем $z_{\max }$; цель j пока остается свободной.
• Конец на

На каждом этапе хотя бы одна свободная цель должна стать насыщенной. Это связано с тем, что, если бы ни одна цель не была насыщена, то среднее значение всех оптимальных решений (P2) было бы допустимым решением, в котором все целевые значения превышают $z_{\max }$ - противоречащее оптимальности решения (П1). Например, предположим $z_{\max }=1$, цель 1 не является насыщенной, поскольку существует решение с вектором значений (3,1), а цель 2 не является насыщенной, поскольку существует решение с вектором значений и (1,3). Тогда существует решение с вектором значений не ниже (2,2), но $z_{\max }$ должно было быть не менее 2.

Таким образом, после не более чем n итераций все переменные насыщаются и находится оптимальное для лексиминов решение. На каждой итерации t алгоритм решает не более n - t +1 линейных программ; следовательно, время работы алгоритма не превышает $(n+2)(n+1)/2\in O(n^{2})$ раз превышает время работы решателя LP.

В некоторых случаях время работы алгоритма насыщения можно улучшить. Вместо поиска всех насыщенных целей мы можем выйти из внутреннего цикла после нахождения одной насыщенной цели; алгоритм по-прежнему останавливается не более чем через n итераций и может уменьшить количество линейных программ (P2), которые нам нужно решить.

Более того, вместо циклического перебора всех целей в поисках насыщенной цели алгоритм может найти насыщенную цель, используя двойственную задачу (P1). В некоторых случаях двойственные переменные задаются как побочный продукт решения (P1), например, когда цели и ограничения линейны, а решателем является симплексный алгоритм . В этом случае (P2) вообще не требуется и время работы алгоритма не превышает $n$ раз больше времени работы решателя (P1).

Все эти варианты работают только для выпуклых задач. Для невыпуклых задач насыщенная цель может отсутствовать, поэтому алгоритм может не остановиться.

Алгоритм упорядоченных результатов для общих задач

Алгоритм упорядоченных результатов работает в произвольных областях (не обязательно выпуклых). Его разработали Огрычак и Сливинский. а также представлено в контексте телекоммуникационных сетей Огрычаком, Пиоро и Томашевским, и в контексте проблем с локацией Огрычака. Алгоритм сводит оптимизацию lexmaxmin к более простой задаче лексикографической оптимизации . Лексикографическую оптимизацию можно выполнить с помощью простого последовательного алгоритма, который решает не более n линейных программ. Сокращение начинается со следующего представления lexmaxmin: $${\begin{aligned}(L1)\\\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$$

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

Эту проблему можно решить итеративно, используя лексикографическую оптимизацию , но количество ограничений на каждой итерации t равно C( n , t ) — количеству подмножеств размера t . Это растет экспоненциально с n . Можно свести проблему к другой задаче, в которой количество ограничений полиномиально от n .

Для каждого t сумма $f_{[1..t]}(x)$ может быть вычислено как оптимальное значение для следующей задачи с n +1 вспомогательными переменными (неограниченная переменная $r_{t}$и неотрицательные переменные $d_{t,j}$ для всех j в 1,..., n ) и n дополнительных ограничений: $${\begin{aligned}(L3)\\\max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}$$Доказательство . Вычислим значения вспомогательных переменных в оптимальном решении.

• Для всех j , $d_{t,j}$ должно быть не меньше 0 и $r_{t}-f_{j}(x)$, и при этом его следует минимизировать, так как в объективе он фигурирует со знаком минус. Поэтому, $d_{t,j}=\max(0,r_{t}-f_{j}(x))$. Таким образом, цель можно записать так: $t\cdot r_{t}-\sum _{j=1}^{n}\max(0,r_{t}-f_{j}(x))$.
• Для любого k от 0 до n, если $r_{t}$ больше, чем наименьшее k целевых значений (т. е. $r_{t}\geq f_{[k]}(x)$), то сумма в правой части содержит ровно k положительных элементов: $\sum _{j=1}^{k}(r_{t}-f_{[j]}(x))=k\cdot r_{t}-f_{[1..k]}(x)$. В этом случае цель можно записать так: $(t-k)\cdot r_{t}+f_{[1..k]}(x)$. Обратите внимание, что $(t-k)\cdot r_{t}$ увеличивается с $r_{t}$ когда k < t и уменьшается с $r_{t}$ когда к > т . Следовательно, максимальное значение достигается при k = t , т.е. $r_{t}$ больше, чем наименьшее t объективных значений; в этом случае цель точно равна $f_{[1..t]}(x)$, как утверждается.

Следовательно, задача (L2) эквивалентна следующей задаче лексикографической максимизации: $${\begin{aligned}(L4)\\\operatorname {lex} \max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})_{t=1}^{n}\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}$$

Эта задача (L4) имеет $n^{2}+n$ дополнительные переменные и $n^{2}$ дополнительные ограничения. Ее можно решить любым алгоритмом решения лексикографической максимизации , например: последовательным алгоритмом с использованием n линейных программ или лексикографическим симплексным алгоритмом (если цели и ограничения линейны).

Примерные решения по чтению

Одним из преимуществ алгоритма упорядоченных результатов является то, что его можно использовать, даже если решатель одной задачи неточен и возвращает только приблизительные решения. В частности, если решатель одной задачи аппроксимирует оптимальное решение одной задачи с мультипликативным коэффициентом α ∈ (0,1] и аддитивным коэффициентом ϵ ≥ 0, то алгоритм возвращает решение, которое аппроксимирует оптимальное для лексимина решение с мультипликативным коэффициентом α. ² /(1 − α + α ² ) и аддитивный коэффициент ϵ/(1 − α + α ² ).

Алгоритм упорядоченных значений для общих задач

Алгоритм упорядоченных значений работает в любой области, в которой множество возможных значений целевых функций конечно. Его разработали Огрычак и Сливинский. Позволять $V=\{v_{1},\ldots ,v_{r}\}$ быть набором всех значений, которые могут быть возвращены функциями $f_{1},\ldots ,f_{n}$, такой, что $v_{1}<\cdots <v_{r}$. Учитывая решение x и целое число k из {1,.., r }, определите $h_{k}(x)$ как количество вхождений значения v _r в вектор $f_{1}(x),\ldots ,f_{n}(x)$. Тогда проблему lexmaxmin можно сформулировать как следующую задачу лексикографической минимизации: $${\begin{aligned}(H1)\\\operatorname {lex} \min &&h_{1}(x),\ldots ,h_{r-1}(x)\\{\text{subject to}}&&x\in X\end{aligned}}$$поскольку мы хотим иметь как можно меньше функций, достигающих наименьшего значения; при этом как можно меньше функций достигают следующего наименьшего значения; и так далее. Огрычак и Сливинский покажите, как преобразовать эту нелинейную программу в линейную программу со вспомогательными переменными. В своих вычислительных экспериментах алгоритм упорядоченных значений работает намного быстрее, чем алгоритм насыщения и алгоритм упорядоченных результатов.

Алгоритм Берингера для квазивогнутых функций

Берингер представил последовательный алгоритм оптимизации lexmaxmin когда цели являются квазивыпуклыми функциями , а допустимое множество X является выпуклым множеством .

Средневзвешенное значение

Ягер представил способ аналитического представления упорядочения лексиминов с помощью оператора упорядоченного взвешенного усреднения . Он предполагает, что все объективные значения являются действительными числами от 0 до 1, а наименьшая разница между любыми двумя возможными значениями — это некоторая константа d < 1 (так что значения с разницей меньше d считаются равными). Вес $w_{t}$ из $f_{[t]}(x)$ установлено приблизительно $d^{t}$. Это гарантирует, что максимизация взвешенной суммы $\sum _{t}w_{t}f_{[t]}(x)$ эквивалентно лексмаксмин.

Алгоритмы для дискретных переменных

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

Но если область определения велика, описанный выше подход становится невозможным из-за большого количества возможных значений, которые может иметь эта функция: ${m+n-1 \choose n}$, где m — количество различных значений в области определения, а n — количество переменных.

Бувере и Леметр представляют пять различных алгоритмов для поиска оптимальных по лексимину решений дискретных задач удовлетворения ограничений:

1. Ветвь и граница на основе ограничения LEXIMIN — ограничения на два вектора x и y , говорящего, что y больше лексимина, чем x .
2. Ветвление по насыщенным подмножествам — поиск подмножеств переменных, для которых необходимо зафиксировать минимальное значение, и поиск максимально-минимального значения для остальных переменных.
3. Использование ограничения SORT — ограничения на два вектора x и y , говорящего, что y содержит те же элементы, что и x, отсортированные в порядке возрастания. Это ограничение можно эффективно вычислить с помощью нескольких алгоритмов.
4. Использование ограничения ATLEAST.
5. Использование преобразований max-min.

В их экспериментах наиболее эффективным подходом был 4 (ATLEAST), затем 3 (SORT), а затем 1 (LEXIMIN).

Из чеснока представляет алгоритм вычисления оптимального для лексимина распределения ресурсов.