Minimize the trace of a combination of PSD matrices analytically

169 Views Asked by At

I have the following problem:

Define $H$ and $R_k$ for $k=1\dots N$, to be $M\times M$ positive definite matrices.

The problem is to find optimal weights $p_k$that solves the following problem

\begin{equation*} \begin{aligned} & \underset{p}{\text{minimize}} & & tr\left(\sum_{k=1}^N p_k^2 H^{-1}R_k\right) \\ & \text{subject to} & & \sum_{k=1}^Np_k = 1, \;\;\; p_k>0 \;\;\;\forall \; k \end{aligned} \end{equation*}

I know that the solution is given by the following

\begin{equation*} p^0_k = \frac{1}{tr\left(H^{-1}R_k\right)} \left( \sum_{l=1}^N\frac{1}{tr\left(H^{-1}R_l\right)}\right)^{-1}. \end{equation*}

It is obvious that $\sum_{k=1}^Np^0_k = 1$ and that $p^0_k>0 \;\;\;\forall \; k$, so the given solution satisfies the constraint. But how to show that it minimizes the trace?

1

There are 1 best solutions below

0
On BEST ANSWER

A constrained optimisation problem can be tackled by the use of Lagrangian multipliers.

The Lagrangian of the problem is given as

$$\Lambda=tr(\sum_{k=1}^Np_k^2H^{-1}R_k)+\lambda(1-\sum_{k=1}^Np_k)$$

where $\lambda$ is known as the Lagrange multiplier.

In order to find the values of $p_k$ that minimises $tr(\sum_{k=1}^Np_k^2H^{-1}R_k)$ we need to solve for the following sets of equations

$$\frac{\partial \Lambda}{\partial p_m}=2(tr(H^{-1}R_m))p_m-\lambda=0\text{ for } m\in\{1,2,..,N\}$$

$$\frac{\partial \Lambda}{\partial \lambda}=1-\sum_{k=1}^Np_k=0$$

We have

$\large p_m^0=\frac{\lambda}{2(tr(H^{-1}R_m))}$ for $m\in\{1,2,..,N\}$

where $p_m^0$ is the optimal value of $p_m$ that minimises the cost function.

Summing across the $p_k$

$\large \sum_{k=1}^Np_k^0=\lambda(\sum_{k=1}^N\frac{1}{2(tr(H^{-1}R_k)})=1$

leading to

$\large \lambda=\frac{1}{(\sum_{k=1}^N\frac{1}{2(tr(H^{-1}R_k)})}$

We can then substitute the expression for $\lambda$ back into the optimal values of $p_k$ resulting in

$\large p_k^0=\frac{\lambda}{2(tr(H^{-1}R_k))}=\frac{1}{(\sum_{k=1}^N\frac{1}{2(tr(H^{-1}R_k)})}\frac{1}{2(tr(H^{-1}R_k))}\\\large=\frac{1}{2(tr(H^{-1}R_k))}(\sum_{k=1}^N\frac{1}{2(tr(H^{-1}R_k)})^{-1}$