Programa cuadrático convexo con restricción de igualdad lineal y límites en las variables

Question

$$\begin{array}{ll} \text{minimize} & \sum \limits_{i=1}^n x_{i}^{2}\\ \text{subject to} & \sum \limits_{i=1}^n x_{i} = m\\ & 0 \leq x_i \leq a_i\end{array}$$

Sé que si el $a_i$ son lo suficientemente grandes (es decir, mayores que $\frac{m}{n}$ ), esto se minimiza cuando $x_i = \frac{m}{n}\ \forall i$ .

También creo (pero no tengo una prueba formal) que cuando algunos de los $a_i$ no son lo suficientemente grandes (digamos $a_1,...,a_k$ ), entonces esto se minimiza cuando:

$x_i = a_i$ para $i \leq k$ y

$x_i = \frac{m -\sum \limits_{i=1}^k a_{i}}{n-k}$ para $i>k$ .

¿Es esto cierto? Y si es así, ¿podría proporcionar una referencia al respecto? Gracias.

Answer 1

Sí, a partir de la observación de que mover dos $x_i$ "más cerca" sin cambiar la suma, es decir, si $x_i < x_j$ y luego reemplazar $x_i$ y $x_j$ con $x_i + \epsilon$ y $x_j - \epsilon$ -siempre reducirá $\sum x_i^2$ . Es fácil ver esto escribiendo $x_i + x_j = k$ y la reescritura $x_i^2 + x_j^2 = x_i^2 + (k-x_i)^2 = 2 \left(x_i - \frac{k}{2}\right)^2 + \frac{k^2}{2}$ que se minimiza cuando $x_i = k/2$ y aumenta con $\left|\frac{k}{2} - x_i\right|$ .

Esto significa que la disposición (necesariamente única) de $x_i$ que da un valor mínimo de $\sum x_i^2$ no puede tener ningún $x_i$ que es menor que sus correspondientes $a_i$ y algunos otros $x_j$ ; de lo contrario, habría espacio para reducir $\sum x_i^2$ al elevar $x_i$ y bajando $x_j$ . Esto obliga a un mínimo de la forma que usted da.

Una nota: es posible que el minimizador de $\sum x_i^2$ para dar $x_i = a_i$ incluso cuando $a_i > m/n$ . Considere el caso $m = 1$ , $n = 3$ , $a_1 = 0.2$ , $a_2 = 0.35$ , $a_3 = 1$ . "Suficientemente grande" no significa necesariamente mayor que $m/n$ .