Reordenar los vectores dados para minimizar la suma de $\ell_1$ normas de las sumas por pares

Question

Dejemos que $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_n$ sean vectores reales con la siguiente propiedad

$$\sum_{i=1}^{n}\mathbf{x}_i=0$$

Quiero encontrar un agrupación estrategia para lograr el mínimo de

$$\|\mathbf{x}_{i_1}+\mathbf{x}_{i_2}\|_1+\|\mathbf{x}_{i_3}+\mathbf{x}_{i_4}\|_1+\cdots+\|\mathbf{x}_{i_{n-1}}+\mathbf{x}_{i_n}\|_1$$

donde $\|\cdot\|_1$ es el $\ell_1$ norma.

Answer 1

Consideremos el problema algorítmico en el que se dan valores enteros $x_{i,k}$ y debe elegir una permutación $i_1,\dots,i_n$ para minimizar la $\ell_1$ norma de las sumas por pares.

Esto puede resolverse encontrando una correspondencia perfecta de peso mínimo en el gráfico sobre $[n]=\{1,\dots,n\}$ donde el peso de la arista $ij$ es $|\mathbf x_i +\mathbf x_j|$ . Al negar los pesos, encontrar una correspondencia perfecta de peso mínimo es algorítmicamente equivalente a encontrar una correspondencia perfecta de peso máximo.

Esta reducción es en realidad una "equivalencia" en sentido amplio, que demuestra que se necesita algún tipo de algoritmo al menos tan complicado como el de máxima coincidencia. Para el sentido inverso, dado un grafo ponderado en $[n]$ , elija una orientación arbitraria de sus aristas, y una enumeración arbitraria de sus aristas, y defina $x_{i,k}$ para ser el peso de la $k$ Si $i$ es la fuente del borde $k$ la negación del peso de la $k$ Si $i$ es el objetivo de la arista $k$ y $0$ de lo contrario. Entonces un mínimo $\ell_1$ -La suma por pares de la norma corresponde a un emparejamiento de peso máximo; cada $\mathbf x_i$ contribuye $|\mathbf x_i|-x_{i,k}$ a la final $\ell_1$ norma si se empareja con alguna $\mathbf x_j$ donde $k$ El borde es $ij$ . Por lo tanto, minimizar el $\ell_1$ significa maximizar el peso de las aristas elegidas.

Answer 2

Supongamos que nos dan $d$ -vectores dimensionales $\mathrm v_1, \mathrm v_2, \dots, \mathrm v_{2n} \in \mathbb R^d$ . Dejemos que $\rm V$ sea el $d \times 2n$ matriz cuya $k$ -la columna es $\mathrm v_k$ . Dejemos que

$$\mathrm S := \mathrm I_n \otimes 1_2^\top = \begin{bmatrix} 1 & 1 & & & & & \\ & & 1 & 1 & & & \\ & & & \ddots & \ddots & & \\ & & & & & 1 & 1 \end{bmatrix}$$

ser un $n \times 2n$ matriz. Nos gustaría encontrar un $2n \times 2n$ matriz de permutación tal que $\| \mathrm V \mathrm P \mathrm S^\top \|_1$ se minimiza. Obsérvese que utilizamos la siguiente definición para el $1$ -norma de un $m \times n$ matriz

$$\| \mathrm A \|_1 := \sum_{i=1}^m \sum_{j=1}^n | a_{ij} |$$

Dado que hay $(2n)!$ matrices de permutación, tenemos una discreto problema de optimización sobre el conjunto de $2n \times 2n$ matrices de permutación. Tomando el casco convexo de todas las $(2n)!$ matrices de permutación, obtenemos la Politopo de Birkhoff $B_{2n}$ . Por lo tanto, ahora tenemos un continuo problema de optimización en $\mathrm X \in \mathbb R^{2n \times 2n}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm V \mathrm X \mathrm S^\top \|_1\\ \text{subject to} & 1_{2n}^\top \mathrm X = 1_{2n}^\top\\ & \mathrm X 1_{2n} = 1_{2n}\\ & \mathrm X \geq \mathrm O_{2n}\end{array}$$

Introducción de una nueva variable matricial, $\mathrm Y \in \mathbb R^{d \times n}$ obtenemos un programa lineal en $\rm X$ y $\rm Y$

$$\begin{array}{ll} \text{minimize} & \langle 1_d 1_n^\top , \mathrm Y \rangle \\ \text{subject to} & 1_{2n}^\top \mathrm X = 1_{2n}^\top\\ & \mathrm X 1_{2n} = 1_{2n}\\ & - \mathrm Y \leq \mathrm V \mathrm X \mathrm S^\top \leq \mathrm Y \\ & \mathrm X \geq \mathrm O_{2n}\end{array}$$

Sea la solución óptima de este programa lineal denotada por $(\mathrm X^{\star}, \mathrm Y^{\star})$ . Si la matriz $\mathrm X^{\star}$ resulta ser una matriz de permutación, entonces hemos resuelto el problema original.