1
$\begingroup$

(a) Find the maximum value of $X^TAX$ subject to the constraints $X^TX = 1$. (A is a $n * n$ symmetric matrix)

It is easy to solve (a) by using spectral decomposition.

(b) Let A, B be $n * n$ symmetric matrices. By using (a), Find the maximum value of $X^TAX$ and $X$ subject to the constraint is $X^TBX = 1$

How to find?

$\endgroup$
4
  • $\begingroup$ Why should there be a maximum? $\endgroup$ Sep 29 '18 at 14:02
  • $\begingroup$ @0 Hong Do you still assume that $X^TX=1$ in part (b)? $\endgroup$
    – AnyAD
    Sep 29 '18 at 14:09
  • $\begingroup$ Do you know if $B$ is also positive definite? $\endgroup$
    – leonbloy
    Sep 29 '18 at 15:16
  • $\begingroup$ @AnyAD I don't know.. but is (b) possible to solve if assume $X^TX = 1$ in part(b)? $\endgroup$
    – 0 Hong
    Sep 30 '18 at 2:34
1
$\begingroup$

Assume $B$ is invertible. Set $x=B^{-1/2}y$, then $\left\langle x,Bx\right\rangle =1\Longleftrightarrow\left\langle y,y\right\rangle =1$. Thus, \begin{align*} \left\langle x,Ax\right\rangle & =\left\langle y,B^{-1/2}AB^{-1/2}y\right\rangle , \end{align*} and \begin{align*} \max_{\left\langle x,Bx\right\rangle =1}\left\{ \left\langle x,Ax\right\rangle \right\} \end{align*} is the largest eigenvalue of $B^{-1/2}AB^{-1/2}$.

$\endgroup$
0
$\begingroup$

Hint: can you maximise $x^2+ay^2$ subject to $x^2+by^2=1$? Yes, iff $a,\,b\ge 0$. Working in a basis that diagonalises $B$, how in general do the signs of its eigenvalues matter?

$\endgroup$
0
$\begingroup$

It is equivalent to $\max f(x)=x^tAx$ with constraint $g(x)=x^tBx-1=0$. By Lagrange multiplier, to find critical point we solve following equation for $(\lambda,x)$ $$\nabla f=\lambda \nabla g,\ \ \ \ \ \ g(x)=0$$ Here $\nabla f=2Ax$ and $\nabla g=2Bx$. (Try to understand why we get such calculations). Then above equation becomes $$Ax=\lambda Bx$$

(1) if $B$ is invertible (notice that symmetric doesn't imply invertible), then $B^{-1}Ax=\lambda x$, that means solution $x^*$ is eigenvector w.r.t. eigenvalue $\lambda$. Thus $$f=(x^*)^tAx^*=\lambda (x^*)^tBx^*=\lambda\leq \max \lambda_i$$ Thus the maximum of $f$ is just the maximum eigenvalue of matrix $B^{-1}A$.

(2) If $B$ is not invertible, we can't move $B$ to the left. But we still have $(A-\lambda B)x=0$. To solve this system, note that we want a nonzero solution $x$. So by basic linear algebra, we must have $$det(A-\lambda B)=0$$ Therefore we can solve $\lambda^*$, then $$f=x^tAx=\lambda^* x^tBx=\lambda^*$$ In conclusion, comparing above results and choose the maximum one.

$\endgroup$

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.