A quadratically constrained quadratic program (QCQP)

1.2k Views Asked by At

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

1

There are 1 best solutions below

5
On BEST ANSWER

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