2
$\begingroup$

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,

$$f=x^TP_1^{-1}x-\ell(x^TP_2^{-1}x-1)$$

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

$\endgroup$
4
  • $\begingroup$ If $\rm P_1, P_2$ are positive semidefinite, how are they invertible? $\endgroup$
    – Rodrigo de Azevedo
    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$
    – user3007505
    Apr 27, 2017 at 10:23
  • $\begingroup$ Yes, I tried using scalor multiple of x but to no avail. $\endgroup$
    – user3007505
    Apr 27, 2017 at 10:28

1 Answer 1

Reset to default
0
$\begingroup$

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

Hence,

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

$\endgroup$
5
  • $\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$
    – user3007505
    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$
    – Rodrigo de Azevedo
    Apr 28, 2017 at 6:18
  • $\begingroup$ For a specific choice of P1 and P2 my eigenvalues are 0.6798 and 1.1952. $\endgroup$
    – user3007505
    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$
    – Rodrigo de Azevedo
    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$
    – user3007505
    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 .