¿Restricciones que involucran

16

Suponer

\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*}$

donde es una matriz simétrica , y reestructura en un vector unidimensional con entradas. $U$ $n\times n$ $\mathrm{vec}(U)$ $U$ $n^2$

La parte del programa anterior que me da problemas es el . (Restringir las soluciones a matrices simétricas no negativas parece ser sencillo). $\max\{⋅,⋅\}$

Gracias de antemano por cualquier ayuda o referencias!

optimization linear-programming N21
fuente

¿Alguna razón por la que no puede agregar ambas restricciones?

Aron Ahmadia

1

@AronAhmadia: No puede agregar ambas restricciones porque eso sería equivalente a

para todo

. No creo que haya una reformulación de LP de este problema, pero podría haber una reformulación de MILP, aunque eso probablemente lo haga más costoso de resolver.

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$

Geoff Oxberry

@ N21: ¿Qué tan grande espera que sea

para los problemas que desea resolver?

n

$n$

Geoff Oxberry

@ Geoff: ¡Gracias! En última instancia, espero tener una gran

, pero en este momento estoy más preocupado por obtener una solución preliminar con

menos de, digamos 100, o incluso 10.

n

$n$

n

$n$

N21

Gracias por aclarar a @GeoffOxberry, no lo pensé completamente antes de publicar.

Aron Ahmadia

14

Editar: Intentemos esta explicación nuevamente, esta vez cuando esté más despierto.

Hay tres grandes problemas con la formulación (en orden de gravedad):

No existe una reformulación obvia del problema que sea obviamente suave, convexa o lineal.
No es suave.
No es necesariamente convexo.

No es evidente una reformulación suave / convexa / lineal

En primer lugar, no hay una reformulación estándar y obvia de cada restricción . La sugerencia de Aron se aplica a la restricción más común , en la que una restricción como se reemplaza por las siguientes dos desigualdades equivalentes: $\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$

La reformulación no es ideal, cadarestricción

ha sido reemplazada por

restricciones lineales, pero convierte un programa no lineal no uniforme en un programa lineal, que es de orden de magnitud más rápido de resolver.

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$

No suavidad

$\max$

La no suavidad es un gran problema porque:

inmediatamente hace que su problema no sea lineal
la mayoría de los solucionadores de programación no lineales asumen dos veces funciones continuamente diferenciables

$\max$

Posible no convexidad

$\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.$

Estas funciones son cóncavas.

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

$\mathbf{g}$

Opciones para resolver el problema.

$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,$
Pruebe su suerte en su formulación tal como está con un solucionador de paquetes para programas no suaves. No tengo mucha experiencia con este tipo de solucionadores. (Un colega mío los usa en su investigación.) Probablemente sean lentos, ya que no pueden usar información derivada. (Creo que en su lugar utilizan la información de gradiente generalizada de gradiente o Clarke). También es poco probable que pueda resolver grandes instancias de problemas con un solucionador de paquetes.

Geoff Oxberry
fuente

1

Geoff, buenas cosas; Esto alcanza los puntos clave y ofrece muchas ideas constructivas y sugerencias. Lo voté. Pero parece que estás tratando la no convexidad como algo separado del hecho de que, como lo expresas, "no hay una reformulación estándar de las restricciones máximas en un problema de minimización que yo sepa". Pero, de hecho, lo primero es precisamente por qué lo segundo no es posible. Las restricciones no convexas no se pueden expresar en programación lineal --- ¡punto final! Este es un problema no convexo, y tendrá que reformularse como un problema de enteros mixtos o alguna otra heurística aplicada.

Michael Grant

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$

Respiro de muerte
fuente

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
fuente

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)$ para problemas que entran en la región inviable).

Wolfgang Bangerth
fuente

Es una buena idea. Suponiendo que su prueba pase, el problema se convierte en mover la no linealidad y la no suavidad de las restricciones al objetivo, que todavía son cualidades indeseables en una formulación.

Geoff Oxberry

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

No puedo encontrar el botón de comentarios ...

$log(x)<5$

Si se trata de un conjunto convexo, puede realizar un descenso de gradiente en su función objetivo, utilizando algo como el algoritmo de proyección de Dykstra para proyectar nuevamente en el espacio de restricciones.

Tim
fuente

Votado por el comentario sobre las funciones cóncavas; Debería haber pensado más en mi explicación. Proyectar en el conjunto factible es una posibilidad, aunque no estoy seguro si podría aplicar esos algoritmos con restricciones no suaves.

Geoff Oxberry

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

$x^2+y^2<5$

"Los problemas no convexos son NP-hard solo si tienen un número NP de posibles soluciones". NP significa "polinomio no determinista". Estoy completamente perdido sobre lo que estás hablando. En segundo lugar, mencioné la concavidad porque las funciones lineales son cóncavas y convexas; La función no es convexa. El hecho de que la función no sea suave y lineal por partes no excluye inmediatamente la posibilidad de que exista una reformulación de LP.

Geoff Oxberry

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

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

Lo siento, tuve que abreviar el comentario, así que usé NP para no polinomio y P para polinonomio. El punto era que la optimización no convexa no siempre es NP-hard. Solo es NP-hard si el número de posibles soluciones es PEOR que el polinomio. Perdón por la confusión :) Tienes razón sobre la reformulación como lineal. Parecía decir "En consecuencia, no hay forma de reformular su programa como un programa lineal", debido a la no convexidad, solo estaba señalando que no está relacionado con la convexidad sino con la linealidad.

Tim

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)$

PD
fuente

¿Restricciones que involucran

Respuestas:

No es evidente una reformulación suave / convexa / lineal

No suavidad

Posible no convexidad

Opciones para resolver el problema.