Encontrar el vector ortogonal que maximiza el producto punto con otro vector

Question

Tengo un vector de origen, $v$ y un vector objetivo $u$ .

Necesito un algoritmo para encontrar un vector $d$ que es ortogonal a $v$ pero maximiza $u \cdot d$ . Por supuesto que puedo obtener un resultado tan grande como quiera haciendo $d$ grande pero sólo me importa la dirección ideal, así que añadamos también la restricción de que $\lVert d \rVert =1$ .

En 2 dimensiones, sólo hay 2 opciones para $d$ para poder comparar los dos y encontrar el resultado.

En 3 dimensiones, he encontrado que el uso de corss prodcut da la respuesta ideal: $d = v \times (v \times u)$ .

Sin embargo, no he encontrado la forma de generalizarlo a dimensiones superiores.

Gracias.

Answer 1

Se podría describir como un programa lineal con restricciones de igualdad: $$\max_d u^Td$$ $$\text{s.t. }v^Td = 0, ~~ d^Td = 1$$ A continuación, construye un Lagrangiano con parámetros de optimización adicionales $\lambda_1$ y $\lambda_2$ : $$\mathcal{L} = -u^Td + \lambda_1(d^Td-1) + \lambda_2 v^Td$$ Obsérvese el signo menos, ya que estamos maximizando la función de coste. A continuación, calcula el óptimo para los 3 parámetros calculando la derivada correspondiente y fijándola en cero: \begin{equation*} \begin{aligned} \frac{\delta\mathcal{L}}{\delta d}=0 &\leftrightarrow 0=-u+2\lambda_1d+\lambda_2v & &\rightarrow d=\frac{1}{2\lambda_1}(u-\lambda_2v) \\ \frac{\delta\mathcal{L}}{\delta \lambda_1}=0 &\leftrightarrow 0=d^Td-1 = \frac{1}{4\lambda_1^2}(u-\lambda_2v)^T(u-\lambda_2v)-1 & &\rightarrow \lambda_1 = 0.5\sqrt{(u-\lambda_2v)^T(u-\lambda_2v)}\\ \frac{\delta\mathcal{L}}{\delta \lambda_2}=0 &\leftrightarrow 0=v^Td = \frac{v^T(u-\lambda_2v)}{2\lambda_1}\rightarrow0=v^Tu-\lambda_2v^Tv & &\rightarrow\lambda_2 = \frac{v^Tu}{v^Tv} \end{aligned} \end{equation*} Sustituyendo los lambda en $d$ y obtener: $$d=\frac{1}{\|u-\frac{v^Tu}{v^Tv}v\|_2}\left(u-\frac{v^Tu}{v^Tv}v\right),$$ donde $\|x\|_2$ es la longitud del vector $x$ calculado como $\sqrt{x^Tx}$ . Con esto, la respuesta óptima, ¡independientemente del tamaño del vector!

Answer 2

Sea $c=\frac{\langle u,v\rangle}{\|v\|^2}$ . Entonces $u=cv+(u-cv)$ donde $cv$ es paralelo a $v$ y $u-cv$ es ortogonal a $v$ . De ello se deduce que $\langle d,u\rangle=\langle d,u-cv\rangle$ siempre que $d$ es ortogonal a $v$ . Puesto que ambos $d$ y $u-cv$ son ortogonales a $v$ es evidente (utilice la desigualdad de Cauchy-Schwarz si lo desea) que la $d$ que maximiza $\langle d,u\rangle$ es el vector unitario que apunta en la misma dirección que $u-cv$ es decir, $d=\frac{u-cv}{\|u-cv\|}$ .