Ограничения с участием

16

предполагать

\begin{aligned} min A & v e c (U) \\ subject to U_{i, j} \leq max {U_{i, k}, U_{k, j}}, i, j, k = 1, \dots, n \end{aligned}

$\begin{align*} \min A &\mathrm{vec}(U) \\ &\text{subject to } U_{i,j} \leq \max\{U_{i,k}, U_{k,j}\}, \quad i,j,k = 1, \ldots, n \end{align*}$

где - симметричная матрица , а преобразует в одномерный вектор с элементами. $U$ $n\times n$ $\mathrm{vec}(U)$ $U$ $n^2$

Часть вышеупомянутой программы, которая доставляет мне проблемы, это . (Ограничение решений для неотрицательных симметричных матриц кажется простым.) $\max\{⋅,⋅\}$

Заранее спасибо за любую помощь или ссылки!

optimization linear-programming N21
источник

любая причина, почему вы не можете добавить оба ограничения?

Арон Ахмадиа

1

@AronAhmadia: Он не может добавить оба ограничения, потому что это будет эквивалентно

для всех

. Я не думаю, что существует переформулировка этой проблемы LP, но может быть переформулировка MILP, даже если это, вероятно, сделает ее более дорогостоящей.

U_{i, j} \leq min {U_{i, k}, U_{k, j}}

$U_{i,j} \leq \min\{U_{i,k}, U_{k,j}\}$

i, j, k

$i, j, k$

Джефф Оксберри

@ N21: Насколько велика вы ожидаете

для проблем, которые вы хотите решить?

n

$n$

Джефф Оксберри

@Geoff: спасибо! В конечном итоге я надеюсь, что у меня будет большое

, но сейчас я больше всего заинтересован в том, чтобы получить предварительное решение с

меньше, скажем, 100 или даже 10.

n

$n$

n

$n$

N21

Спасибо за разъяснение @GeoffOxberry, я не продумал это до публикации.

Арон Ахмадиа

14

Изменить: Давайте попробуем это объяснение еще раз, на этот раз, когда я больше не сплю.

Есть три больших проблемы с формулировкой (в порядке серьезности):

Нет очевидной переформулировки проблемы, которая является явно гладкой, выпуклой или линейной.
Это негладко.
Это не обязательно выпукло.

Нет очевидной гладкой / выпуклой / линейной переформулировки

Во-первых, нет стандартной, очевидной переформулировки каждого ограничения. Предложение Арона применимо к более общему ограничению, в котором ограничение типа заменяется следующими двумя эквивалентными неравенствами: $\max$ $\min$

U_{i j} \leq min_{k} {U_{i k}, U_{k j}}

$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$

U_{i j} \leq U_{i k}, \forall k

$U_{ij} \leq U_{ik}, \quad \forall k$

Переформулировка не идеальна, каждое

ограничение заменено

линейными ограничениями, но оно преобразует негладкую нелинейную программу в линейную программу, решение которой на порядки быстрее.

U_{i j} \leq U_{k j}, \forall k .

$U_{ij} \leq U_{kj}, \quad \forall k.$

min

$\min$

2 n

$2n$

$\max$ $\max$ $n^2$ $\max$ $2n$

$\max$

негладкости

$\max$

Негладкость - огромная проблема, потому что:

это сразу делает вашу проблему нелинейной
большинство решателей нелинейного программирования принимают дважды непрерывно дифференцируемые функции

$\max$

Возможная невыпуклость

$\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$

U_{i j} - max_{k} {U_{i k}, U_{k j}} \leq 0, \forall i, j, k .

$U_{ij} - \max_{k}\{U_{ik}, U_{kj}\} \leq 0, \quad \forall i,j,k.$

Эти функции вогнуты.

$-U_{ij}$ $\max_{k}\{U_{ik}, U_{kj}\}$

$\mathbf{g}$

Варианты решения проблемы

$U_{i j} \leq max_{k} {U_{i k}, U_{k j}}, \forall i, j, k$ $U_{ij} \leq \max_{k}\{U_{ik}, U_{kj}\} , \quad \forall i,j,k$ $U_{i j} \leq min_{k} {U_{i k}, U_{k j}}, \forall i, j, k,$ $U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\} , \quad \forall i,j,k,$
Испытайте свою удачу на своей формулировке, как это с пакетным решателем для негладких программ. У меня нет большого опыта с этими типами решателей. (Мой коллега использует их в своих исследованиях.) Они, вероятно, медленные, так как не могут использовать производную информацию. (Я думаю, что вместо этого они используют субградиент или обобщенную информацию о градиенте Кларка.) Также маловероятно, что вы сможете решать большие экземпляры задач с помощью решателя пакетов.

Джефф Оксберри
источник

1

Джефф, хорошие вещи; это затрагивает ключевые моменты и предлагает много конструктивного понимания и предложений. Я проголосовал за это. Но вы, похоже, рассматриваете невыпуклость как нечто отдельное от того факта, что, как вы выразились, «в известной мне проблеме минимизации нет стандартной переформулировки максимальных ограничений». Но на самом деле, именно поэтому последнее невозможно. Невыпуклые ограничения не могут быть выражены в линейном программировании --- полная остановка! Это невыпуклая проблема, и ее придется либо переформулировать как смешанную целочисленную проблему, либо применять какую-то другую эвристическую методику.

Майкл Грант

g (x) \leq 0

$\mathbf{g}(x) \leq \mathbf{0}$

g

$\mathbf{g}$

g (x) \leq 0

$\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$

g

$\mathbf{g}$

1

x \leq max {y, z}

$x \le \max\{y,z\}$

(x, y, z)

$(x,y,z)$

1

max {y, z}

$\max\{y,z\}$

3

$-\infty$

U = (\begin{matrix} 1 & \dots & 1 \\ ⋮ & ⋮ \\ 1 & \dots & 1 \end{matrix}) .

$U=\left(\begin{matrix} 1&\cdots &1\\ \vdots & & \vdots\\1&\cdots&1\end{matrix}\right).$

A \cdot vec (U)

$A\cdot\mbox{vec}(U)$

U

$U$

t

$t$

\pm U

$\pm U$

min_{V} (A \cdot vec (V)) \leq m i n_{t} (A \cdot vec (t U)) = - \infty

$\min_V(A\cdot\mbox{vec}(V)) \le min_{t}(A\cdot \mbox{vec}(tU))=-\infty$

Deathbreath
источник

U

$U$

- \infty

$-\infty$

U

$U$

\leq 0

$\le 0$

2 tr ({\hat{A}}^{*} U) = ‖ \hat{A} - U ‖^{2} - ‖ \hat{A} ‖^{2} - ‖ U ‖^{2}

$2\mbox{tr}(\hat{A}^\ast U)=\|\hat{A}-U\|^2-\|\hat{A}\|^2-\|U\|^2$

2

$f \le \max \{ f_1, f_2,...,f_n \}$ $n$ $b_i \in \{0,1\}$ $1 \le i \le n$ $M$ $f$

$f \le f_i + (1-b_i) M, \forall i$

$\sum_i b_i = 1$

$M := max_i f_i - min_i f_i$ $f_i$

Kevin
источник

1

x_{i} <= max (a_{i 1}, a_{i 2}, . . ., a_{i n})

$x_i <= \max(a_{i1}, a_{i2}, ..., a_{in})$

x_{i} <= s_{i}

$x_i <= s_i$

s_{i} >= a_{i 1}

$s_i >= a_{i1}$

s_{i} >= a_{i 2}

$s_i >= a_{i2}$

. . .

$...$

s_{i} >= a_{i n}

$s_i >= a_{in}$

c * max (s_{i} - max (a_{i}), 0)

$c*\max(s_i-\max(a_i), 0)$

s_{i} - max (a_{i})

$s_i-\max(a_i)$

c

$c$

$s_i>=\max(a_i)$ $x_i=s_i$ $s_i-\max(a_i)$ для проблем, которые уходят в неосуществимый регион.)

Вольфганг Бангерт
источник

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

Джефф Оксберри

a_{i j}

$a_{ij}$

(x_{i}, a_{i 1}, a_{i 2}, . . ., a_{i n})

$(x_i,a_{i1},a_{i2},...,a_{in})$

(x_{i}, s_{i}, a_{i 1}, a_{i 2}, . . ., a_{i n})

$(x_i,s_i,a_{i1},a_{i2},...,a_{in})$

1

Я не могу найти кнопку комментария ...

$log(x)<5$

Если это выпуклый набор, вы можете выполнить градиентный спуск к вашей целевой функции, используя что-то вроде Dykstra's_projection_algorithm, чтобы проецировать обратно в пространство ограничений.

Тим
источник

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

Джефф Оксберри

x^{2} + y^{2} < 5

$x^2+y^2<5$

«Невыпуклые проблемы NP-сложны, только если у них есть NP-число возможных решений». NP означает «недетерминированный полином». Я полностью потерян о том, о чем ты говоришь. Во-вторых, я упомянул вогнутость, потому что линейные функции вогнутые и выпуклые; функция не выпуклая Тот факт, что функция является негладкой и кусочно-линейной, не исключает сразу возможности переформулировки LP.

Джефф Оксберри

U_{i j} \leq min_{k} {U_{i k}, U_{k j}}

$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$

Извините, пришлось коротко комментировать, поэтому я использовал NP для неполинома и P для полинома. Дело в том, что невыпуклая оптимизация не всегда NP-сложна. Это NP-сложно, если число возможных решений МНОГО БОЛЬШЕ, чем полиномиальное. Извините за путаницу :) Вы правы в отношении переформулировки как линейной. Вы, казалось, сказали: «Следовательно, нет способа переформулировать вашу программу как линейную программу», из-за невыпуклости, я просто заметил, что она связана не с выпуклостью, а с линейностью.

Тим

0

$-\infty$ $0$

$U \ge 0$ $A$ $n$ $-\infty$ $0$

$a \le b \le c$ $c \le \max(a,b)$ $b=c$ $i,j,k$

$U_{ij} < U_{jk} = U_{ik}$
$U_{ik} < U_{jk} = U_{ij}$
$U_{jk} < U_{ik} = U_{ij}$
$U_{ij} = U_{jk} = U_{ik}$

$t$ $G(t)$ $U_{ij}=t$ $U_{ij}=U_{j k}=t$ $\ell$ $U_{j \ell}=t$ $U_{i\ell}=U_{k\ell}=t$ $G(t)$

п.с.
источник

Ограничения с участием

Ответы:

Нет очевидной гладкой / выпуклой / линейной переформулировки

негладкости

Возможная невыпуклость

Варианты решения проблемы