How to show that the following two problems are equivalent?

204 Views Asked by At

I am doing exercise 5.40 of Convex Optimization book (By Boyd and Vandenberghe). In the book it is mentioned that we can formulate the problem

$$\begin{array}{ll} \text{minimize} & \displaystyle\lambda_{\max} \left( \sum_{i=1}^p x_i v_iv_i^T \right)^{-1}\\ \text{subject to} & 1^T x = 1\\ & x \succeq 0\end{array}$$

as the following problem $$\min. ~~~~ 1/t \\ s.t. ~~~~\sum _{i=1}^px_iv_iv_i^T \succeq tI \\ x \succeq 0\\ 1^Tx=1.$$ I tried to show that they are equivalent but in my attempt I get the following equivalent problem $$\max. ~~~~1/t\\ s.t. ~~~~\sum _{i=1}^px_iv_iv_i^T \succeq \frac{1}{t} I\\ x \succeq 0\\ 1^Tx=1.$$ In my attempt I assumed $G=(\sum_{i=1}^p x_i v_iv_i^T)^{-1}$ and then formulated the problem as $$\min. ~~~~ t \\ s.t.~~~~ \lambda_{max}(G)\leq t\\ G=(\sum_{i=1}^p x_i v_iv_i^T)^{-1}\\ x \succeq 0\\ 1^Tx=1.$$ Where am I wrong? Any help in this regard will be much appreciated. Thanks in advance.

1

There are 1 best solutions below

1
On

Let $H=\sum_{i=1}^p x_i v_iv_i^T$.

I think you understood the original problem to be

$$\min. ~~\lambda_{max} (H^{-1})\\ s.t.~~~~ 0\preceq x,~~~ 1^Tx=1,$$

whereas the original problem is actually meant to be

$$\min. ~~(\lambda_{max} (H))^{-1}\\ s.t.~~~~ 0\preceq x,~~~ 1^Tx=1.$$

This is not the same. I have not checked the of the work, but this mistake will lead to a wrong result.