2
$\begingroup$

$\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}

$\endgroup$
1
  • $\begingroup$ Yes only variable is $x$. and I removed my "interesting problem" comment from original post. You are right…its trivial. how about the second problem that I added later $\endgroup$ – NAASI Jan 28 '15 at 19:07
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I was thinking of using $\alpha_1\langle x,y_1\rangle^2 + \alpha_2\langle x,y_2\rangle^2=\alpha_1x^Ty_1y_1^Tx + \alpha_2x^Ty_2y_2^Tx = x^T \big(\alpha_1y_1y_1^T + \alpha_2^Ty_2y_2^T \big)x$ and this matches to your formulation but here we didnt change the dimension as was in the case of $Z$. Your reply was very helpful. Thank you $\endgroup$ – NAASI Jan 29 '15 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.