Maximización del producto interior de los vectores unitarios

Question

Estoy trabajando en un proyecto de investigación y el algoritmo principal se basa en el cálculo de la siguiente función:

Dada una matriz simétrica $A$ y un vector unitario $x_0$ computar: $\max\langle Ax,x\rangle : ||x|| = 1$ y $\langle x,x_0\rangle= 0$ .

Tengo algunos límites pero no una fórmula cerrada ni solución numérica o aproximación. Cualquier idea será bienvenida.

Gracias

Answer 1

Para cualquier vector $y$ con $\|y\|\le1$ , dejemos que $x=Py$ donde $P=I-x_0x_0^T$ . Entonces $\|x\|\le1$ y $\langle x,x_0\rangle=0$ . Además, cada $x$ que satisface estas restricciones se obtiene como $x=Py$ para algunos $y$ (por ejemplo, basta con tomar $y=x$ ).

Por lo tanto, el problema es equivalente a maximizar $\langle Py,APy\rangle=\langle y,P^TAPy\rangle$ con sujeción a $\|y\|\le1$ y la solución viene dada por el vector propio correspondiente al mayor valor propio de $P^TAP$ .

Answer 2

Pregunta antigua, pero se puede utilizar iteración de potencia para optimizar un Cociente de Rayleigh sobre un subespacio. Para adaptar el algoritmo de iteración de la potencia a la restricción del subespacio, se alterna la aplicación de la matriz $A$ y una proyección $P$ en el subespacio (en su caso el subespacio son los vectores ortogonales a $x_0$ ).

Es decir, elegir un vector inicial $v_0$ al azar, y repetidamente hacer

$$ v_{n+1} \gets PAv_n$$ $$ v_{n+1} \gets \frac{v_{n+1}}{\|v_{n+1}\|_2}$$

Después de suficientes iteraciones, $\langle v_n, A v_n\rangle$ estará cerca de $\max_{v \in S, \|v\|_2 = 1} \langle v, Av\rangle$ .