Un interesante problema de asignación de recursos

Question

Este es el problema: \begin{array}{ll} \text{minimize} & \sum_{i=1}^N \frac{1}{1 + \textrm{exp}(C_i + x_i)}\\ \text{subject to} & \sum_{i=1}^N x_i \le R \\ & x_i \ge 0, ~ i = 1,2,...,N \end{array}

$C_1,C_2,...,C_N$ El problema parece fácil, pero después de varios días todavía no tengo idea de cómo resolverlo. Gracias por cualquier comentario.

Answer 1

¡Me pareció interesante considerar este problema! ¿De qué aplicación proviene? No es convexo a menos que $\min_i C_i\geq 0$ y ya que ha dicho explícitamente que $C_i$ puede ser negativo, no puede ser tratado como convexo. Además, el problema es inviable si $R<0$ y trivial si $R=0$ Así que vamos a suponer que $R>0$ .

Dado que las restricciones son lineales y el objetivo es suave, las condiciones KKT son condiciones necesarias que debe cumplir cualquier óptimo. Estas condiciones se construyen en torno al Lagrangiano \begin{aligned} L(x,\lambda,\nu) &= \sum_i \frac{1}{1+\exp(C_i+x_i)} - \sum_i \lambda_i x_i - \nu ( R - \sum_i x_i ) \\ &= -R\nu + \sum_i \frac{1}{1+\exp(C_i+x_i)} + (\nu-\lambda_i) x_i \end{aligned} donde $\lambda_i\geq 0$ , $i=1,2,\dots,n$ son los multiplicadores de Lagrange para $x_i\geq 0$ y $\nu \geq 0$ es el multiplicador de Lagrange para $\sum_i x_i \leq R$ . Las condiciones son:

• Estacionariedad: $$\frac{\exp(C_i+x_i)}{(1+\exp(C_i+x_i))^2}=\nu-\lambda_i, \quad i=1,2,\dots, n.$$
• Viabilidad primaria y dual: $$\sum_i x_i \leq R \quad \nu\geq 0 \quad x_i,\lambda_i\geq 0, ~ i=1,2,\dots, n$$
• Flojedad complementaria: $$\nu \left( R- \sum_i x_i \right) = 0 \quad\Longrightarrow\quad \nu =0 \text{or}\sum_i x_i=R$$ $$\lambda_i x_i = 0 \quad\Longrightarrow\quad x_i=0\text{or}\lambda_i=0, \quad i=1,2,\dots, n.$$

La condición de holgura complementaria en $\nu$ no es tan útil, porque debe sea cierto que $\sum_i x_i = R$ en el punto óptimo. Después de todo, si $\sum_i x_i < R$ entonces podemos aumentar cualquier $x_i$ hasta lograr la igualdad, y disminuir el objetivo al hacerlo.

La condición de holgura complementaria en $\lambda$ es mucho más interesante. Obsérvese la implicación: si $x_i>0$ entonces $\lambda_i=0$ , lo que significa que $$x_i > 0 \quad\Longrightarrow\quad \frac{\exp(C_i+x_i)}{(1+\exp(C_i+x_i))^2}=\nu$$ En otras palabras, todos los valores no nulos de $x_i$ debe obtener el mismo valor para esa cantidad de la izquierda. Resolviendo para $\exp(C_i+x_i)$ tenemos $$\exp(C_i+x_i) = -1 + \frac{1}{2\nu} ( 1 \pm \sqrt{1-2\nu} )$$ Ya tenemos $\nu\geq 0$ y para que el lado derecho sea real, debemos tener también $\nu\leq 1/2$ . La inspección nos dice que para $\nu\in(0,1/2)$ sólo una de las raíces es positiva; y cuando $\nu=1/2$ ambos son cero. Por lo tanto, nosotros hacer tienen $$x_i > 0 \quad\Longrightarrow\quad x_i = \log\left(-1 + \frac{1}{2\nu}( 1 + \sqrt{1-2\nu} )\right)-C_i \quad\nu\in(0,1/2)$$ La cantidad desordenada de la derecha es irrelevante: ahora sabemos que todos los valores no nulos de $x_i$ debe obtener el mismo valor de $C_i+x_i$ .

Esto nos lleva a lo que se llama un algoritmo de llenado de agua . La idea es la siguiente: empezamos con el valor más pequeño de $C_i$ y empezar a "añadir agua" $C_i+x_i$ hasta que sea igual al siguiente el valor más pequeño, por ejemplo $C_j$ . A continuación, añadimos a ambos $C_i+x_i=C_j+x_j$ hasta que sean iguales al tercer valor más pequeño. El proceso continúa hasta llegar a $\sum_i x_i = R$ .

EDIT: Está claro que esa parte en la que yo hacer La mano, que describe el algoritmo de llenado de agua, no es correcta. Pero tenga en cuenta que el ejemplo de Bob a continuación cumple con las condiciones de optimalidad anteriores . Voy a pensar en esto y editaré más si es necesario.