Máx. De una combinación convexa sobre un casco convexo de variables reales

Tengo el siguiente programa lineal: donde,denota la suma de las entradas de, yes conocido y tiene entradas distintas estrictamente positivas.

\begin{array}{cc} Maximize & a^{T} x \\ Subject to & x_{min} \leq x \leq x_{max} \\ 1^{T} x = 1 \end{array}

$\begin{array}{cc} \text{Maximize} & a^T x \\ \text{Subject to} & x_{\min} \leq x \leq x_{\max} \\ & \mathbf{1}^T x = 1 \end{array}$

x \in R^{n}

$x \in \mathbb{R}^n$

1^{T} x

$\mathbf{1}^T x$

x

$x$

a

$a$

Estoy buscando una forma rápida de resolver lo anterior sin usar un solucionador de LP. ¿Hay un procedimiento rápido a seguir? (además de Simplex).

¡Gracias!

optimization convex-optimization Mohammad Fawaz
fuente

Respuestas:

La solución óptima es la siguiente: establecer todas las variables iguales a sus mínimos. Luego, comenzando desde el más grande hasta el más pequeño, establezca iterativamente el correspondiente más grande posible hasta que presione . Si o entonces el problema es inviable. Creo que esta es la misma solución que genera el algoritmo de Geoffrey Irving. $a_i$ $x_i$ $\sum_i x_i = 1$ $\sum_i x_{i,min} > 1$ $\sum_i x_{i,max} < 1$

La razón por la que esto funciona es que puede transformar su problema en la relajación LP del problema de la mochila 0-1 a través de

y_{i} = \frac{x_{i} - x_{i, m i n}}{x_{i, m a x} - x_{i, m i n}} .

$y_i = \frac{x_i - x_{i,min}}{x_{i,max} - x_{i,min}}.$

En el espacio variable , el problema se convierte en $y$

\begin{array}{cl} Maximize & \sum_{i} c_{i} y_{i} \\ Subject to & 0 \leq y_{i} \leq 1, for each i \\ \sum_{i} b_{i} y_{i} = d, \end{array}

$\begin{array}{cl} \text{Maximize} & \sum_i c_i y_i \\ \text{Subject to} & 0 \leq y_i \leq 1, \text{ for each } i \\ & \sum_i b_i y_i = d, \end{array}$

donde , y . Si el problema original es factible, entonces $c_i = a_i (x_{i,max} - x_{i,min})$ $b_i = (x_{i,max} - x_{i,min})$ $d = 1 - \sum_i x_{i,min}$ $d \geq 0$ . Las 'sy ' s no son negativas, por lo que tenemos la relajación LP de 0-1 mochila. (La expresión aparece técnicamente en el objetivo, pero como es una constante, podemos descartarla). $c_i$ $b_i$ $\sum_i a_i x_{i,min}$

Suponiendo que las variables están ordenadas por la relación $\frac{c_i}{b_i} = a_i$ $y_1 = y_2 = \cdots = y_k = 1$ $k$ $y_{k+1} = d - \sum_{i=1}^k b_i$ $y_{k+2} = \cdots = y_n = 0$ $x$ El espacio problemático variable proporciona la solución que acabo de describir.

$\leq$ $=$ $x$ $\sum_i x_{i,max} < 1$

Mike Spivey
fuente

$x_i$ $a_i$ $x_{\max}$ $x_j$ $a_j$ $x_{\min}$ $O(n \log n)$ $a$ $O(n)$

$x_i$ $x_{\max}$ $a_i$ $x_j$ $x_{\min}$ $a_j$ $x_k$ $x_{\min} < x_k < x_{\max}$ $a_i > a_k > a_j$ $x$ $x_j$ $x_k$ $x_i$ $x_k$

Geoffrey Irving
fuente

x

$x$

Gracias por su respuesta. El enfoque parece interesante, pero secundo la solicitud de @ArnoldNeumaier de proporcionar un argumento.

Mohammad Fawaz

Cambia dos componentes por iteración, por lo que no estoy seguro de lo que quieres decir con no correcto si se toma literalmente. Agregaré una breve explicación.

Geoffrey Irving

x_{i}

$x_i$

i

$i$

i j

$ij$

Ah, tienes razón sobre lo mismo en cada iteración. Debería arreglarse ahora.

Geoffrey Irving