Problema de viabilidad de programación lineal con estrictas restricciones de positividad.

15

Hay un sistema de restricciones lineales ${\bf Ax} \leq {\bf b}$ . Deseo encontrar un vector estrictamente positivo que satisfaga estas restricciones. Eso significa que es necesario para cada componente de . ¿Cómo puedo usar un solucionador de LP para encontrar un vector tan estrictamente positivo (o confirmar que no existe )? No puedo simplemente introducir otro sistema de restricciones , porque siempre se debe permitir la igualdad en un LP, pero puedo usar el solucionador de LP varias veces, con funciones objetivas cambiantes. Creo que debería usar el método de variable de holgura, pero no sé cómo. ${\bf x} > 0$ $x_i > 0$ $x_i$ ${\bf x}$ ${\bf x}$ ${\bf x}$ $x_i > 0$

optimization linear-programming sara
fuente

15

Puede sortear el problema de elegir un pequeño $\epsilon>0$ siendo un poco más ambicioso: intente encontrar $\mathbf{x}$ tal que $\mathbf{Ax}\leq \mathbf{b}$ y que la entrada más pequeña en $\mathbf{x}$ sea la mayor posible.

y = [\begin{matrix} X \\ ϵ \end{matrix}] \in R^{norte + 1}

$\mathbf{y} = \begin{bmatrix} \mathbf{x}\\ \epsilon\end{bmatrix}\in\mathbb{R}^{n+1}$

x

$\mathbf{x}$

R^{n}

$\mathbb{R}^n$

max_{y} [0 0 ... 0 0 1] \cdot y S t [UN 0 0] y \leq si y 0 0 \leq [\begin{matrix} 1 & 0 0 & \dots & 0 0 & - 1 \\ 0 0 & 1 & \dots & 0 0 & - 1 \\ ⋱ & ⋮ \\ 0 0 & \dots & 1 & - 1 \end{matrix}] y .

$\max_y [0 \dots 0\ 1]\cdot \mathbf{y}\quad \text{s.t.}\quad [A\ \mathbf{0}]\mathbf{y}\leq\mathbf{b}\quad \text{and}\quad \mathbf{0}\leq \begin{bmatrix}1 & 0 & \cdots & 0 & -1 \\ 0 & 1 & \cdots & 0 & -1 \\ & \ddots & &\vdots \\ 0 & \cdots & & 1 & -1 \end{bmatrix}\mathbf{y}.$

Esta es una reformulación del siguiente problema:

max ϵ S t UN X \leq si y X \geq ϵ 1 .

$\max \epsilon \quad\text{s.t}\quad \mathbf{Ax\leq b}\quad\text{and}\quad \mathbf{x}\geq\epsilon\mathbf{1}.$

Puñal
fuente

bien hecho, esto es equivalente a un truco que un coautor y acabo de usar en un artículo reciente, y definitivamente superior al enfoque que sugerí.

Aron Ahmadia

Convenido. Bien jugado, señor.

Geoff Oxberry

El problema reformulado puede tener un objetivo ilimitado en los casos en que la respuesta al problema original es trivial. Por ejemplo, si el sistema de restricciones es solo . Eso está bien siempre que verifique si es factible, óptimo o ilimitado en el estado de retorno de su solucionador lp, o vincula explícitamente el .

x \geq - 1

$x \ge -1$

ϵ

$\epsilon$

David Nehme

@DavidNehme: se puede agregar la restricción para obtener un objetivo acotado.

y_{n + 1} \leq 1

$y_{n+1}\le 1$

Arnold Neumaier

5

Para un problema de viabilidad de LP, no usaría el simplex estándar. Los algoritmos símplex primarios estándar (o duales) solo visitarán los vértices del conjunto factible de los problemas primarios (o duales).

Supongamos que el conjunto factible del problema que realmente desea resolver es , y suponga que, en cambio, debe resolver el problema ( ): $F = \{\mathbf{x}: \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} > \mathbf{0}\}$ $F_{\varepsilon}$

\begin{aligned} min_{X} 0 0 \\ S t & UN X \leq si \\ X \geq ε \cdot 1 . \end{aligned}

$\begin{alignat}{1} & \min_{\mathbf{x}} \quad 0 \\ \textrm{s.t.} & \quad \mathbf{Ax} \leq \mathbf{b} \\ & \quad \mathbf{x} \geq \varepsilon \cdot \mathbf{1}. \end{alignat}$

La aproximación más cercana del problema que desea resolver es , que admite demasiados puntos. El problema es que el límite del ortante positivo (es decir, el conjunto podría formar parte del límite del conjunto factible de . les gusta excluir esos puntos. Una forma de hacerlo es hacer lo que Aron sugirió, que es establecer $F_{0}$ $B = \{\mathbf{x}: \mathbf{x} \geq 0, \exists{i}: x_{i} = 0\}$ $F_{0}$ $\varepsilon$ a algún valor positivo pequeño, y luego use cualquier algoritmo LP estándar. Esta estrategia es buena y probablemente funcionará en una amplia variedad de situaciones. Sin embargo, fallará si es factible. Sabemos que para todos (para abusar de la notación y referirse a un conjunto factible por su problema correspondiente), y es posible que incluso si selecciona pequeños valores positivos de , el solucionador LP indicará que tu LP no es factible. $F_{\varepsilon}$ $F_{0} \subset F \subset F_{\varepsilon}$ $\varepsilon > 0$ $\varepsilon$

Para un software de PL, que haría uso de cualquier algoritmo de punto interior para discos que se inicia con un punto factible y estancias factibles, que es otra manera de excluir puntos en . No es necesario que proporcione un punto factible para estos algoritmos; Los solucionadores estándar lo harán por usted. Métodos como el escalado afín, la reducción de potencial y los métodos de barrera establecen LPs auxiliares que encontrarán soluciones factibles, y los iteraciones para estos algoritmos atraviesan el interior de la región factible. Solo necesita ubicar un punto en su región factible, por lo tanto, mientras los problemas auxiliares utilizados por los solucionadores de LP encuentren un punto factible para su problema, y ese punto factible sea estrictamente positivo, debería estar bien. Si la resolución de falla para pequeños valores positivos de $B$ $F_{\varepsilon}$ $\varepsilon$ , aún puede utilizar estos métodos para localizar un punto factible estrictamente positivo dentro de . $F_{0}$

Sin embargo, no use simplex, ya que solo explorará los vértices de , que es exactamente lo que desea evitar hacer. $F_{\varepsilon}$

Geoff Oxberry
fuente

4

Los problemas de viabilidad son un juego un poco más complicado que los problemas lineales generales, que usted ha notado. Si está resolviendo aproximadamente (mediante el uso de una representación de coma flotante del sistema de ecuaciones y restricciones), es legítimo requerir , donde es un valor numérico muy pequeño, lo suficientemente grande como para asegurar que realmente vive en , pero lo suficientemente pequeño como para que no se considere una solución en el límite. $x_i >= \epsilon$ $\epsilon$ $x_i$ $\Re_+$

Puede que tenga que ajustar , y su solución estará calificada para "dentro de un factor de ", pero esto es suficiente para muchas situaciones. $\epsilon$ $\epsilon$

Aron Ahmadia
fuente

2

La respuesta dada por aeismail debe ser leída cuidadosamente, tenga en cuenta el lp

$\max( x_1 + x_2)$

S t

$x_1 + x_2 \le 1$

$x_1,x_2 \ge 0$

Tiene soluciones y así como otras (degeneradas). La generalidad de la pregunta implica que estos casos también deben tratarse. $(1,0)$ $(0,1)$

Como puede elegir su función objetivo, puede intentar modificarla de forma iterativa. Por ejemplo, comience con todos los coeficientes para todas las variables iguales a uno, verifique si obtiene una solución adecuada. Si una variable es cero, aumente su coeficiente y comience de nuevo ...

Aunque no puedo dar una prueba matemática de que esto funciona (o un procedimiento bien definido sobre cómo modificar la función objetivo). Espero que esto ayude :)

Dan
fuente

Sin embargo, si tiene una gran cantidad de soluciones degeneradas, ¿cómo trataría esto numéricamente? ¿Casi ningún solucionador numérico arrojará una advertencia (o peor) sobre la resolución de este problema?

aeismail

No, no lo harán; solo devolverán la primera solución óptima encontrada. La forma en que continuaría generando soluciones es agregando planos de corte (u otras restricciones) que excluyan las soluciones óptimas calculadas previamente. En este caso, agregar tales planos de corte le permitiría devolver una aproximación discreta del conjunto infinito de soluciones óptimas.

Geoff Oxberry

Vería eso como una extraña decisión de programación; ¿por qué no querrías decirle al usuario que la función objetivo estaba haciendo algo extraño en la vecindad de la solución informada? Para un solucionador no lineal, pude ver que hay un problema para descubrir lo que está sucediendo; pero ¿no debería ser más fácil saberlo con un sistema lineal?

aeismail

Tendría que pensar cómo se detectaría la degeneración al construir problemas, pero por lo general, los usuarios quieren una solución óptima, por lo que la información más importante para un LP es regresar si la solución es óptima, factible (pero no óptima), inviable o ilimitado. (Estos estados son, de hecho, lo que devolvería un solucionador como CPLEX). La degeneración es principalmente una cuestión teórica; La única razón por la que se trataría en un contexto numérico es en el diseño de algoritmos o en la práctica, para notar que la degeneración generalmente ralentiza a un solucionador.

Geoff Oxberry

Problema de viabilidad de programación lineal con estrictas restricciones de positividad.

Respuestas: