[Math] minimizing linear combination of inner products

inner-productsoptimization

$\mathbf{x},\mathbf{y_1},\mathbf{y_2}\in \mathbb{R}^{m}$ and $\alpha_1,\alpha_2 \in \mathbb{R}$. Also $\|\mathbf{y_1}\|_2 = \|\mathbf{y_2}\|_2 = 1$ and $\alpha_1\geq\alpha_2\geq0$.

How should we find $\mathbf{x}$ that minimizes

\begin{equation}
\begin{array}{c}
\text{min} \hspace{4mm} \alpha_1 \langle \mathbf{x},\mathbf{y_1} \rangle + \alpha_2 \langle \mathbf{x},\mathbf{y_2} \rangle \\
s.t \hspace{17mm}\|\mathbf{x}\|_2 = 1,
\end{array}
\end{equation}

$\mathbf{y_1},\mathbf{y_2}$ are pointing in arbitrary directions.
We can start by considering $\alpha_1=\alpha_2=1$ and find $\mathbf{x}$. But how to approach when $\alpha_1\neq\alpha_2$ is the problem.

Variant of original formulation (added later)

\begin{equation}
\begin{array}{c}
\text{min} \hspace{4mm} \alpha_1 \big(\langle \mathbf{x},\mathbf{y_1} \rangle \big)^2+ \alpha_2 \big(\langle \mathbf{x},\mathbf{y_2} \rangle \big)^2 \\
s.t \hspace{17mm}\|\mathbf{x}\|_2 = 1,
\end{array}
\end{equation}

Best Answer

Since $\alpha_1\langle x,y_1\rangle+\alpha_2\langle x,y_2\rangle=\langle x,y\rangle$ with $y:=\alpha_1y_1+\alpha_2y_2$, the problem is equivalent to finding $x$ such that $\langle x,y\rangle$ is minimal with $\|x\|_2=1$.

The Cauchy-Schwarz inequality states that $|\langle x,y\rangle|\leq\|x\|_2\|y\|_2=\|y\|_2$ with the equality if and only if $x$ is a scalar multiple of $y$. Varying $x$ over the boudnary of the unit ball, $\langle x,y\rangle$ hence attains the values between $-\|y\|_2$ and $\|y\|_2$, with the minimum achieved by $x=x_*:=-y/\|y\|_2$.

EDIT For the second problem, since $\alpha$'s are nonnegative, you can "merge" them into $y$'s and consider a problem of minimizing $\langle x,z_1\rangle^2+\langle x,z_2\rangle^2$ instead. Note that with $Z:=[z_1,z_2]$, we have $$\langle x,z_1\rangle^2+\langle x,z_2\rangle^2=\|Z^Tx\|_2^2.$$ If $Z=USV^T$ is the SVD of $Z$ ($U$ is $m\times 2$ with orthonormal columns, $V$ is $2\times 2$ orthogonal matrix, and $S$ is $2\times 2$ diagonal), the minimizer $x_*$ is hence given by the left singular vector associated with the minimal singular value of $Z$. The minimal value is given by the square of this minimal singular value.

Related Question