Given two positive semi-definite matrices $P_1$ and $P_2$,

$$\begin{array}{ll} \text{minimize} & x^T P_1^{-1} x\\ \text{subject to} & x^T P_2^{-1} x = 1\end{array}$$

My approach is to form a Lagrangian function, that is,


and solve this using Newton's Method. The method work fine and the result obey the constraint.

But in an article, another way is followed to solve this problem. Using $df/dx=0$ and simplifying we can write, $$ (P_2P_1^{-1}+\ell I)x=0, $$ where $I$ is the identity matrix. Now it is given that the lagrange multiplier $\ell$ and minimizing points $x$ are the eigenvalues and eigenvectors of the matrix $-P_2P_1^{-1}$ (using $P_2^{-1}$ weighted norm) respectively.

But when I use the eigenvectors of $-P_2P_1^{-1}$, the constraint is not satisfied. Furthermore, the result of the two methods is different.

I want to know if these two methods are same. If yes, what am I missing here? Any help will be greatly appreciated. Thanks

  • $\begingroup$ If $\rm P_1, P_2$ are positive semidefinite, how are they invertible? $\endgroup$ Apr 27, 2017 at 9:26
  • $\begingroup$ If $x$ is an eigenvector, so are its nonzero scalar multiples. Have you tried to scale $x$ to fit the constraint $x^TP_2^{-1}x=1$? $\endgroup$
    – user1551
    Apr 27, 2017 at 9:43
  • $\begingroup$ Lets assume that P1 and P2 have non-zero eigenvalues. $\endgroup$ Apr 27, 2017 at 10:23
  • $\begingroup$ Yes, I tried using scalor multiple of x but to no avail. $\endgroup$ Apr 27, 2017 at 10:28

1 Answer 1


$$\begin{array}{ll} \text{minimize} & \rm x^T P_1^{-1} x\\ \text{subject to} & \rm x^T P_2^{-1} x = 1\end{array}$$

where $\rm P_1, P_2$ are symmetric and positive definite. From the symmetry of $\rm P_2$, we conclude it has a spectral decomposition $\rm P_2 = Q \Lambda Q^{\top}$. From the positive definiteness of $\rm P_2$, we conclude that $\Lambda$ has an invertible square root. Hence,

$$\rm P_2 = Q \Lambda Q^{\top} = Q \Lambda^{\frac 12} \Lambda^{\frac 12} Q^{\top}$$

Thus, we have a QCQP in $\rm y := \Lambda^{-\frac 12} Q^{\top} x$

$$\begin{array}{ll} \text{minimize} & \rm y^T \left( \Lambda^{\frac 12} Q^{\top} P_1^{-1} Q \,\Lambda^{\frac 12} \right) y\\ \text{subject to} & \| \rm y \|_2^2 = 1\end{array}$$


$$\rm y^T \left( \Lambda^{\frac 12} Q^{\top} P_1^{-1} Q \,\Lambda^{\frac 12} \right) y \geq \lambda_{\min} \left( \Lambda^{\frac 12} Q^{\top} P_1^{-1} Q \,\Lambda^{\frac 12} \right) \underbrace{ \| \rm y \|_2^2 }_{= 1} = \lambda_{\min} \left( \Lambda^{\frac 12} Q^{\top} P_1^{-1} Q \,\Lambda^{\frac 12} \right)$$

Let $\rm y_{\min}$ be a normalized eigenvector corresponding to the minimum eigenvalue. Hence, the minimum is attained at

$$\rm x_{\min} := Q \,\Lambda^{\frac 12} y_{\min}$$

  • $\begingroup$ Thank you very much for very simple way to solve it. But I have one question: The result provided by this method and Newton's Method should be same or it can be different? I mean if there can be multiple minimum points? $\endgroup$ Apr 28, 2017 at 3:09
  • $\begingroup$ @user3007505 What is the spectrum of your $\rm \Lambda^{\frac 12} Q^{\top} P_1^{-1} Q \,\Lambda^{\frac 12}$? $\endgroup$ Apr 28, 2017 at 6:18
  • $\begingroup$ For a specific choice of P1 and P2 my eigenvalues are 0.6798 and 1.1952. $\endgroup$ Apr 28, 2017 at 6:24
  • $\begingroup$ @user3007505 I don't understand why you're using Newton's method. The objective may be convex, but the constraint clearly is not. Take a look at Quadratically Constrained Quadratic Programming. $\endgroup$ Apr 28, 2017 at 8:29
  • $\begingroup$ You are right,there is no need for Newton's Method here. I really appreciate your help. Thanks a lot. $\endgroup$ Apr 28, 2017 at 8:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .