Maximización de una forma cuadrática en puntos de celosía cúbica unitaria $\{ -1 , 1 \}^n$

Question

Consideremos el problema: dada una forma cuadrática simétrica, definida positiva, con matriz $A = A^T \in \mathbb R^{n \times n}$ calcular el vector $y \in \{-1,1\}^n$ alcanzar el máximo

$$\max_{x \in \{-1,1\}^n } x^TAx$$

¿Existe un algoritmo eficaz?

Estaba considerando dos posibilidades. ¿Funcionan para casi todos los ejemplos? Si ambas funcionan, ¿cuál es más eficiente desde el punto de vista computacional?

1. La función $f(x)=x^TAx$ alcanza su máximo (el radio espectral de $A$ ) en la esfera unitaria $\{\|x\|_2=1\}$ exactamente cuando $x$ es un vector propio para el valor propio dominante. Así que usted podría obtener una estimación decente para el problema mediante el cálculo de la dominante eigenvector $u$ con $\|u\|_\infty =1$ y luego redondear cada componente de $u$ a $\pm 1$ . ¿Hay alguna razón por la que esto podría fallar genéricamente? El cálculo de los vectores propios es difícil, pero aquí no hay que preocuparse mucho por la precisión, ya que se redondea de todos modos.

2. El gradiente de $f$ es $\nabla f(x) = 2Ax$ . Podrías realizar un flujo gradiente en la esfera unidad $[-1,1]^n$ para encontrar un punto $p$ alcanzando al menos un máximo local en $[-1,1]^n$ . ¿Podría $p$ sea un punto de red para un $A$ ? Si no es así, ¿qué podría impedir que el punto de red más cercano fuera el máximo deseado?

Answer 1

Desafortunadamente, tu problema es NP-Hard, por lo que no puedes esperar encontrar un algoritmo eficiente. En la práctica, estos problemas suelen abordarse mediante algoritmos heurísticos. Si realmente desea una solución óptima demostrable, los métodos de bifurcación y acotación son los más adecuados.

Para ver que este problema es NP-Duro, empecemos con el problema MAX-CUT en un grafo. Este problema es bien conocido como un problema NP-Duro. Sea $L$ sea el laplaciano del grafo. Una propiedad del laplaciano del grafo es que $L$ es semidefinida positiva. El problema MAX-CUT puede formularse como

$\max_{x_{i}=\pm 1} \frac{1}{4} x^{T}Lx$

Por lo tanto, un algoritmo eficiente (tiempo polinómico) para su problema podría ser utilizado para resolver MAX-CUT en tiempo polinómico.

Answer 2

Tenemos el siguiente problema booleano de optimización en $\mathrm x \in \{\pm 1\}^n$

$$\max_{\mathrm x \in \{\pm 1\}^n} \mathrm x^\top \mathrm A \,\mathrm x$$

Desde $\{\pm 1\}$ es el conjunto de soluciones de la ecuación cuadrática $x_i^2 = 1$ tenemos lo siguiente (no convexo) programa cuadrático con restricciones cuadráticas (QCQP) en $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{maximize} & \mathrm x^\top \mathrm A \,\mathrm x\\ \text{subject to} & x_i^2 = 1, \quad \forall i \in \{1,2,\dots,n\}\end{array}$$

Evaluación exhaustiva de la función objetivo en todos $2^n$ puntos sólo es factible para pequeños $n$ . Aunque este problema es duro encontrar un límite superior del máximo es fácil .

---

Relajación SDP

Tenga en cuenta que

$$\mathrm x^\top \mathrm A \,\mathrm x = \mbox{tr} \left( \mathrm x^\top \mathrm A \,\mathrm x \right) = \mbox{tr} \left( \mathrm A \mathrm x \mathrm x^\top \right) = \langle \mathrm A , \mathrm x \mathrm x^\top \rangle$$

Desde $\mathrm x \in \{\pm 1\}^n$ todos $n$ entradas en la diagonal principal de $\mathrm x \mathrm x^{\top}$ son iguales a $1$ . Así, $\mathrm x \mathrm x^{\top}$ es simétrico, semidefinido positivo y sólo tiene unos en su diagonal principal, es decir, es un correlación matriz. Además, su rango es $1$ . Por lo tanto, el problema de optimización booleano original puede escribirse de la siguiente manera rango limitado problema de optimización en $n \times n$ matriz simétrica $\rm X$

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & x_{ii} = 1, \quad \forall i \in \{1,2,\dots,n\}\\ & \mathrm X \succeq \mathrm O_n\\ & \mbox{rank} (\mathrm X) = 1\end{array}$$

que es un problema difícil debido a la restricción de rango. Relajante el problema de optimización anterior descartando la restricción de rango, obtenemos lo siguiente programa semidefinido (SDP) en $\rm X$

$$\boxed{\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & x_{ii} = 1, \quad \forall i \in \{1,2,\dots,n\}\\ & \mathrm X \succeq \mathrm O_n\end{array}}$$

que es convexa y computacionalmente manejable. Esta relajación SDP proporciona una límite superior sobre el máximo del problema de optimización booleano original. En el caso muy, muy afortunado de que la solución óptima del SDP sea rank- $1$ También hemos resuelto el problema original.