¿Restricciones que involucran

16

Suponer

minAvec(U)subject to Ui,jmax{Ui,k,Uk,j},i,j,k=1,,n

donde es una matriz simétrica n × n , y v e c ( U ) reestructura U en un vector unidimensional con n 2 entradas.Un×nvec(U)Un2

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!

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 i , j , k . 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. Ui,jmin{Ui,k,Uk,j}i,j,k
Geoff Oxberry
@ N21: ¿Qué tan grande espera que sea para los problemas que desea resolver? 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 n menos de, digamos 100, o incluso 10.nn
N21
Gracias por aclarar a @GeoffOxberry, no lo pensé completamente antes de publicar.
Aron Ahmadia

Respuestas:

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

  1. No existe una reformulación obvia del problema que sea obviamente suave, convexa o lineal.
  2. No es suave.
  3. 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ínima más común , en la que una restricción como U i jmin k { U i k , U k j } se reemplaza por las siguientes dos desigualdades equivalentes: U i jU i k ,maxmin

Uijmink{Uik,Ukj}
U i jU k j ,
UijUik,k
La reformulación no es ideal, cadarestricción mínima ha sido reemplazada por 2 n 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.
UijUkj,k.
min2n

maxmaxn2max2n

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

g(x)0

Uijmaxk{Uik,Ukj}0,i,j,k.

Estas funciones son cóncavas.

Uijmaxk{Uik,Ukj}

g

Opciones para resolver el problema.

  • Uijmaxk{Uik,Ukj},i,j,k
    Uijmink{Uik,Ukj},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)0gg(x)0g
1
xmax{y,z}(x,y,z)
1
max{y,z}
3

U=(1111).
Avec(U)Ut±UminV(Avec(V))mint(Avec(tU))=
Respiro de muerte
fuente
U
U02tr(A^U)=A^U2A^2U2
2

fmax{f1,f2,...,fn}n bi{0,1}1inMf

ffi+(1bi)M,i

ibi=1

M:=maxifiminififi

Kevin
fuente
1

xi<=max(ai1,ai2,...,ain)
xi<=si
si>=ai1
si>=ai2
...
si>=ain
cmax(simax(ai),0)
simax(ai)c

si>=max(ai)xi=sisimax(ai) 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
aij(xi,ai1,ai2,...,ain)(xi,si,ai1,ai2,...,ain)
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
x2+y2<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
Uijmink{Uik,Ukj}
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

0

U0An0

abccmax(a,b)b=ci,j,k

  1. Uij<Ujk=Uik
  2. Uik<Ujk=Uij
  3. Ujk<Uik=Uij
  4. Uij=Ujk=Uik

tG(t)Uij=tUij=Ujk=tUj=tUi=Uk=tG(t)

PD
fuente