Finding orthogonal vector that maximizes dot product with some other vector I have an origin vector, $v$ and a goal vector $u$.
I need an algorithm to find a vector $d$ that is orthogonal to $v$ but maximizes $u \cdot d$. Of course I can get a result as large as I want by making $d$ large but I only care about the ideal direction, so let's also add the constraint that $\lVert d \rVert =1$.
In 2 dimensions, there are only 2 options for $d$ so I can compare the two of them and find the result.
In 3 dimensions, I found that using corss prodcut gives the ideal answer:
$d = v \times (v \times u)$.
I couldn't find a way to generalize to higher dimensions though.
Thanks.
 A: you could describe this as a linear program with equality constraints:
$$\max_d u^Td$$
$$\text{s.t. }v^Td = 0, ~~ d^Td = 1$$
Then construct a Lagrangian with additional optimization parameters $\lambda_1$ and $\lambda_2$:
$$\mathcal{L} = -u^Td + \lambda_1(d^Td-1) + \lambda_2 v^Td$$
note the minus sign as we are maximizing the cost function. Next, compute the optimum for all 3 parameters by computing the corresponding derivative and setting that to zero:
\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*}
Substituting the lambda's back into $d$ and obtain:
$$d=\frac{1}{\|u-\frac{v^Tu}{v^Tv}v\|_2}\left(u-\frac{v^Tu}{v^Tv}v\right),$$
where $\|x\|_2$ is the length of vector $x$, computed as $\sqrt{x^Tx}$.
With this, the optimal answer, regardless of the size of the vector!
A: Let $c=\frac{\langle u,v\rangle}{\|v\|^2}$. Then $u=cv+(u-cv)$, where $cv$ is parallel to $v$ and $u-cv$ is orthogonal to $v$. It follows that $\langle d,u\rangle=\langle d,u-cv\rangle$ whenever $d$ is orthogonal to $v$. Since both $d$ and $u-cv$ are orthogonal to $v$, it is evident (use Cauchy-Schwarz inequality if you want) that the $d$ that maximises $\langle d,u\rangle$ is the unit vector pointing in the same direction as $u-cv$, i.e., $d=\frac{u-cv}{\|u-cv\|}$.
