Soluciones de punto medio para programas lineales

Hay un programa lineal para el que quiero no solo una solución, sino una solución que sea lo más central posible en el politopo que asuma el valor mínimo.

A priori, esperamos que la cara de minimización sea de alta dimensión por varias razones, incluyendo que la función objetivo que se minimiza es el máximo de muchas de las restricciones:

Minimice sujeto a con linear y para todo y . $\epsilon$ $f_i(\bar x) \leq \epsilon < 0$ $f_i$ $x_i > 0$ $i$ $\sum_i x_i = 1$

Por supuesto, nunca obtendríamos ninguna propiedad similar a la centralidad del algoritmo simplex. Sin embargo, ¿alguno de los algoritmos habituales de punto interior exhibe tales propiedades? ¿Alguno garantiza que evitarán vértices o caras de dimensiones inferiores siempre que sea posible?

De hecho, probablemente estoy contento con un programa cuadrático fácil que encuentra el punto medio de todo el politopo ya que la centralidad es más importante que la minimidad, solo un poco curioso si otros algoritmos de programación lineal ofrecen propiedades relevantes.

Actualización: he reducido el problema subyacente a un simple problema de minimización restringida solucionable con multiplicadores de Lagrange, pero la pregunta anterior sigue siendo interesante de todos modos.

ds.algorithms linear-algebra linear-programming Jeff Burdges
fuente

no es exactamente su pregunta sino: calcular el centroide es # P-hard; No estoy seguro de cuál es la mejor aproximación, pero para algunas aplicaciones es suficiente colocar el politopo en posición isotrópica y tomar el promedio de polinomios de muchas muestras uniformes del politopo (transformado). vea estas notas, Lema 15 por ejemplo: cc.gatech.edu/~vempala/acg/notes.pdf

Sasho Nikolov

¿Es esto más una pregunta teórica o más práctica? quizás sería factible generar todos los vértices de la cara óptima y luego usar alguna combinación convexa adecuada de ellos.

anónimo

Respuestas:

Tengo algunas observaciones que son demasiado largas para comentarios. Aquí hay un resumen.

Cualquier algoritmo para resolver su problema exactamente puede usarse para resolver programas lineales exactamente (es decir, "programación lineal fuerte", que se usa en la solución de Sariel, y actualmente no tiene un algoritmo de tiempo polinómico).
El seguimiento natural es si las soluciones aproximadas (es decir, "programación lineal débil") pueden proporcionar una solución. Si bien la respuesta es sí, parece que la condición de detención para este procedimiento requiere cantidades que, que yo sepa, no se pueden calcular en tiempo polinómico. (es decir, el algoritmo encuentra algo bueno, pero certificar esto es difícil). Mi sugerencia principal aquí es hacer una definición significativa de una " solución óptima de " para su problema, en cuyo caso este enfoque es manejable. (Esta estrategia efectivamente arroja pequeñas caras del poliedro). $\epsilon$

En general, mientras pensaba en su declaración actual de su problema, seguí encontrándome con consideraciones de eficiencia. Pero hay una intuición razonable en esto: los objetos que arrojamos (vértices, caras, etc.) son discretos y exponencialmente abundantes.

(1.) Supongamos que tenemos un algoritmo que resuelve exactamente su problema. Observe que cualquier punto expuesto de cualquier cara que contenga el punto medio proporcionado será una solución exacta al programa lineal original. Entonces proceda de la siguiente manera. Agregue una nueva restricción lineal que diga que el valor objetivo original debe ser igual al valor óptimo (que ahora sabemos), y establezca un nuevo objetivo que diga para maximizar la primera coordenada de la solución. Repita este procedimiento una vez para cada dimensión, cada vez que agregue una restricción y elija una nueva coordenada para maximizar. Este proceso reducirá la dimensión de la solución cada vez; necesariamente, cuando el proceso se completa, tenemos un conjunto afín de 0 dimensiones, lo que significa un solo punto. Así con $\mathcal O(d)$ iteraciones de su algoritmo de resolución de punto medio (y solo aumentando la descripción del problema en una cantidad de polinomios en cada vez), se resuelve una programación lineal fuerte. Esto muestra que si bien la solución de Sariel requiere una programación lineal sólida, una solución exacta a su pregunta no puede evitarla. ( Editar : tenga en cuenta que mi prueba supone un poliedro compacto (un politopo) como entrada; de lo contrario, tiene que trabajar un poco más para encontrar vértices). $d$

(2.) Aquí hay un esquema iterativo, que utiliza un solucionador convexo completo en cada iteración, cuyas soluciones convergerán en una noción leve de solución de punto medio. Elija una secuencia positiva pero decreciente de parámetros de penalización ; Es razonable que estos disminuyan geométricamente, es decir, . Ahora, para cada , minimice aproximadamente la función convexa $\{\lambda_i\}_{i=1}^\infty\downarrow 0$ $\lambda_i = 2^{-i}$ $i$

⟨ c, x ⟩ - λ_{i} \sum_{j = 1}^{m} \ln (⟨ a_{j}, x ⟩ - b),

$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$

donde es su objetivo original, y extiende sobre las restricciones originales , ahora colocadas en el objetivo a través de barreras logarítmicas (nota, esto es estándar). Ahora, si pensamos en la cara minimizadora (de la dimensión más grande) de su poliedro, tenga en cuenta que para y tolerancia suficientemente pequeñas para su caja negra opcional convexa, su óptimo aproximado estará cerca de esta cara, sin embargo, las barreras empujarán lo más lejos posible de las otras restricciones. Dicho de otra manera, como $\langle c,x\rangle$ $j$ $m$ $\lambda_i$ $\tau$ $\lambda_i$ disminuye, el objetivo lineal original eventualmente dominará algunas barreras delicadas que lo mantenían alejado de la cara apropiada, pero no afectará las barreras que lo mantienen fuera de otros límites, en particular los de la cara objetivo.

En un mundo perfecto, nos sentaríamos y determinaríamos analíticamente un valor perfecto , o al menos un tiempo de parada para que no tenga que resolver, bueno, infinitos problemas. Desafortunadamente, esto parece difícil. Una idea es, por ejemplo, determinar el ancho más pequeño de cualquier cara que tenga una dimensión mayor que 0; Este es un problema de minimización bien definido con óptimo positivo, porque hay muchas caras (y el ancho se calcula en relación con cada una). Con esto, podemos establecer suficientemente pequeño como para que la influencia de las barreras sea pequeña en el centro de cada cara. Desafortunadamente, podría haber exponencialmente muchas caras, por lo que calcular esta cantidad no tiene sentido. $\lambda$ $\lambda$

Todas las condiciones de detención que pude encontrar tuvieron este tipo de dificultades computacionales. (Además, muchos podrían usarse nuevamente para convertir esto en un solucionador de programación lineal fuerte).

Por esta razón, mi recomendación es construir una noción de `` -close punto medio óptimo '', y resolverlo eligiendo y su tolerancia convexa de caja negra apropiadamente. Creo que esta es una opción razonable porque puede que realmente no te interesen las caras que tienen un ancho máximo como máximo . $\epsilon$ $\lambda$ $\tau$ $\epsilon$

(Algunos comentarios finales.) Parece que la noción de "punto medio" es crucial; El comentario de Sasho señala que el centroide (¿centro de masa?) Es un problema extremadamente difícil, mientras que encontrar, digamos, la bola inscrita más grande es fácil. Las barreras logarítmicas que he sugerido anteriormente en general no serán consistentes con ninguna de estas nociones de punto medio. Por otro lado, para las barreras y la pelota, puede derivar un límite inferior en la distancia desde su centroide hasta el límite relativo de la cara; tal vez esto te sea más útil?

Por último, según su descripción, ¿creo que quiso decir que la "cara objetivo" tenía la mayor dimensión posible? Esto está bien definido, sin embargo, también hay caras de solución para todas las dimensiones más pequeñas posibles. De todos modos, tanto el enfoque de Sariel como el enfoque de barrera anterior funcionarán con la cara de la dimensión más grande.

matus
fuente

Sí, consideré trucos como este, pero finalmente por minimizar sujeto a usando multiplicadores de Lagrange. Produce una propiedad de centralidad débil para en la diagonal, que podría no ser la superficie de minimización, pero es sin duda una de las superficies de restricción que nunca se mueve. Simplemente ejecuto un programa lineal separado una vez que las contracciones dejan de evolucionar y realmente necesito el mínimo real para . En última instancia, no era necesario mantener minimizado para ayudar a que las restricciones evolucionaran más rápido. Gracias sin embargo! :)

\sum_{i} f_{i} (x)^{2} + \sum_{j} x_{j}^{2}

$\sum_i f_i(x)^2 + \sum_j x_j^2$

\sum_{j} x_{j} = 1

$\sum_j x_j = 1$

x

$x$

ϵ

$\epsilon$

ϵ

$\epsilon$

Jeff Burdges

Ahh # 2 parece interesante, no lo que inicialmente pensé que era. ¡lindo! Como dije, perdono a por no aterrizar en la cara minimizadora, siempre que vaya a un lugar razonablemente rápido. Jugaré con esto en algún momento. De hecho, tendré que leer sobre la optimización convexa de todos modos ya que he encontrado una razón para hacer que mi objetivo sea bilineal en lugar de lineal.

x

$x$

Jeff Burdges

No entiendo el punto sobre "programación lineal fuerte" y nunca antes había escuchado esta expresión. No se sabe cómo resolver un LP en tiempo polinómico fuerte. pero, por supuesto, es bien conocido resolver un polinomio LP en el tiempo en la descripción de entrada (es decir, tiempo polinomial débil). si el OP quiere un algoritmo que se ejecute en un tiempo polinómico débil, entonces la solución de Sariel + un algoritmo de punto interior de tiempo múltiple hará el trabajo, ¿no?

Sasho Nikolov

@ SashoNikolov, aquí está mi comprensión actual. Cualquier solucionador existente (poly-time débil) tomará una tolerancia como entrada y devolverá una solución -optimal. Mientras tanto, la solución de Sariel depende crucialmente de una solución exacta: en particular, un método de punto interior devolverá un óptimo aproximado relativamente interior, lo que significa que el paso que identifica el casco afinado de la cara óptima deseada realmente seleccionará el casco de todo el factible conjunto. Estoy de acuerdo en que debería revisar lo que escribí sobre fuerte / débil, donde el tema clave es realmente obtener soluciones exactas de cualquier manera.

τ

$\tau$

τ

$\tau$

matus

@SashoNikolov, ahora que lo pienso, la misma noción de optimización (con los mismos problemas) puede trabajarse en la solución de Sariel, por ejemplo, tratando las restricciones que están dentro de una pequeña tolerancia para ser realmente ajustadas, y ajustando este valor de manera apropiada. Actualizaré mi solución esta noche.

matus

Primero encuentre la solución óptima, luego agregue la restricción lineal de que la solución debe tener un valor igual al óptimo que desea, y repita su LP como el que busca la bola más grande dentro de la región factible. Resuelve este LP modificado y tienes lo que quieres.

Por qué el segundo problema puede resolverse usando LP es un problema estándar en Geometría Computacional ...

==============

Más formalmente, encuentra el subespacio afín que abarca los puntos factibles que contienen la solución óptima. Por lo tanto, suponga que la solución óptima se encuentra en el hiperplano (es decir, era la función objetivo LP original). Si es la región factible del LP original, estamos buscando la bola más grande en . Para este fin, necesitamos calcular el subespacio afín dimensional más pequeño que contiene este conjunto. Una vez que encuentre este subespacio, cambie las variables para que solo considere este subapce afín. Ahora, su politopo es completamente dimenisonal, y puede usar el segundo LP como describí anteriormente. $h \equiv cx = \alpha$ $\min c x$ $P$ $P \cap h$

Entonces, sea el vértice calculado por el primer LP. Considerando todos los vértices vecinos a . Considere el subespacio afín de junto con todos sus vecinos que tienen el mismo valor objetivo (es decir, ). No es difícil ver que este subespacio afín es el subespacio deseado. $v$ $v$ $v$ $\alpha$

Entonces, para veranear: (A) resuelva LP para descubrir el valor óptimo. (B) Calcule el subespacio dimensional más pequeño que contiene la solución factible con el valor óptimo. (C) Reescriba el LP original en esta subpsacia afín (es decir, eliminando todas las dimensiones irrelevantes), agregue una variable y conviértala en un LP para encontrar la bola más grande dentro de este politopo.

Sariel Har-Peled
fuente

¿Qué se entiende por "bola más grande" en un poliedro no de dimensión completa?

Kristoffer Arnsfelt Hansen

@KristofferArnsfeltHansen, el poliedro seguramente es un conjunto convexo que se encuentra en un subespacio afín de alguna dimensión.

Sasho Nikolov

para que esto funcione, deberá especificar una restricción que lo limite a la (s) cara (s) que encontró en el primer paso. También necesitaría saber que la solución era constante en este aspecto (presumiblemente, la holgura complementaria revelaría esto)

Suresh Venkat

¿Hay alguna forma de hacer los pasos después de la optimización inicial en tiempo polinómico? Tal como está escrito, parece requerir la consideración de todos los vértices en la cara del objetivo, de los cuales puede haber exponencialmente muchos.

matus

Es más fácil que eso: solo debe tener en cuenta los vértices adyacentes al vértice óptimo: hay como máximo adyacentes a él, y puede calcularlos en tiempo polinómico ... Para ver por qué es cierto, considere el politopo en el subespacio afín: lo abarcan los vecinos de que se encuentran en este subespacio afín, pero estos son un subconjunto de los vértices adyacentes a v en el politopo original. Y sí, me llevó bastante tiempo ver eso.

d

$d$

v

$v$

Sariel Har-Peled