0
$\begingroup$

I need to find the minimum of the function $x^TAx$ with the condition, that $x^TBx = 1$, where both $A$ and $B$ are positive definite (symmetric) matrices.

I put a lagrangian $L = x^TAx - \alpha * x^TBx$ and obtained $Ax = \alpha * Bx$. From there, I can get $x = \alpha * A^{-1}Bx$ and $B^{-1}Ax = \alpha * x$, since both $A$ and $B$ are regular.

Combining those two, I get $B^{-1}AB^{-1}Ax = \alpha^2 x$. Now, since both $A$ and $B$ were symmetric positive definite, they will have real, positive eigenvalues. Also, from our constraint ($x^TBx = 1$), we obtain $\alpha = x^TAx$. Is it then safe to assume, that taking square root of the smallest eigenvalue is the solution to the original problem, with the eigenvector associated (scaled appropriately for the condition to hold) as its argument?

Is there any other way, how to solve this?

$\endgroup$
  • $\begingroup$ Test your hypothesis in two dimensions with $A=I$ and $B$ diagonal, so that it represents an axis-aligned ellipse. Which eigenvalue corresponds to the shorter principal axis? $\endgroup$ – amd Dec 4 '18 at 0:17
1
$\begingroup$

First of all, the problem is not convex. Non-convexity stems from the equality constraint. You try to solve a Quadratically Constrained Quadratic Program(QCQP). So, although I could not fully understand your argument, the Lagrangian may not help you to find the exact solution, rather it provides a good lower bounds. I will offer a different perspective, consider following problem: $$min \ x^TAx,\ s.t.\ x^TBx = 1 \\ \equiv min\ trace(x^TAx),\ s.t. \ trace(x^TBx) = 1 \\\equiv min\ trace(Axx^T),\ s.t.\ trace(Bxx^T) = 1 \\ \equiv min\ trace(AX),\ s.t.\ trace(BX) = 1,\ rank(X) = 1$$ Your original problem is transformed into Semi-definite Program (SDP) which is still non-convex, but you can relax the rank constraint and you will get a convex Relaxed SDP, which is a linear program in your case: $$ min\ trace(AX),\ \\s.t.\ trace(BX) = 1 $$ Nice thing about this relaxation is that the solution of the relaxed SDP is equivalent to original SDP (so your original problem), since you have only one constraint. All of this relaxation procedure and the conditions for optimal solution can be found in the Lou et al's excellent lecture notes[1]. Solving this problem analytically rather than via software may not be possible.

[1]Luo, Zhi-Quan, et al. "Semidefinite relaxation of quadratic optimization problems." IEEE Signal Processing Magazine 27.3 (2010): 20-34.

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