I am stuck with the following problem.

Prove that the optimal value to the SDP \begin{align} \text{minimize} \quad &\operatorname{tr}(V) \end{align} \begin{align} \text{subject to} \quad &\begin{bmatrix} X & U \\ U & I \end{bmatrix} \succeq 0, \quad \begin{bmatrix} U & X \\ X & V \end{bmatrix} \succeq 0 \end{align}

is $f(X) = \sum_{i} \lambda_i(X)^{3/2}$, where $X \in \mathbf{S}^{m}_{+}$ and $U, V \in \mathbf{S}^{m}$

I have tried decomposing $X = Q \Lambda Q^T$ and using Schur complement to re-write the constraints but to no avail. My initial idea was to show that the problem is equivalent to the problem \begin{align} \text{minimize} \ \ \operatorname{tr}(V) \end{align} \begin{align} \text{subject to } \quad f(x) \le \operatorname{tr}(V) \end{align} I am writing this question after trying to solve the problem for 6 hours. I have no idea on how to approach this problem. Any help is greatly appreciated.

I really appreciate any help you can provide.

  • $\begingroup$ If everything was 1-dimensional then you would have $x\geq u^2$ and $uv\geq x^2$ which is equivalent to $v\geq x^{3/2}$. This is a standard way to model the function $x^{3/2}$ by quadratic cones. Your case should be an extension of that argument eigenvalue-wise. $\endgroup$ Feb 19 at 7:43

1 Answer 1

  • If $X$ is positive definite, by Schur complement, the optimization problem is equivalent to \begin{align*} &\min_{U, V \in S^{m}} \quad \mathrm{tr}(V)\\ &\mathrm{subject \ to}\quad X \succeq U^2, \quad U \succ 0, \quad V \succeq XU^{-1}X. \end{align*}

From $X \succeq U^2$ and $U \succ 0$, we have $ U^{-1} \succeq X^{-1/2}$. We have $$\mathrm{tr}(V) \ge \mathrm{tr}(XU^{-1}X) = \mathrm{tr}(U^{-1}X^2) \ge \mathrm{tr}(X^{-1/2}X^2) = \mathrm{tr}(X^{3/2}).$$

On the other hand, $(U, V) = (X^{1/2}, X^{3/2})$ is feasible with $\mathrm{tr}(V) = \mathrm{tr}(X^{3/2})$.

Thus, the minimum is $\mathrm{tr}(X^{3/2})$.

  • Some thoughts if $X$ is not positive definite

consider the following optimization problem (for fixed $\delta > 0$) \begin{align*} &\min_{U, V \in S^{m}} \quad \mathrm{tr}(V)\\ &\mathrm{subject \ to}\quad \begin{bmatrix} X + \delta I & U \\ U & I \end{bmatrix} \succeq 0, \quad \begin{bmatrix} U & X + \delta I \\ X + \delta I & V \end{bmatrix} \succeq 0. \end{align*}

Similarly, the minimum is $\mathrm{tr}((X + \delta I)^{3/2})$.

What if $\delta \to 0$?


You must log in to answer this question.

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