Given the optimization problem
$\underset{X,Y\in\mathbb{S}^{+}}{\min}$ Tr($X+AY$)
s.t$X=Y^{-1}$.
where $X_0$ and $A$ positive definite matrices. I was wondering whether the above optimization problem (subject to constraints) is convex?
I believe that the constraint $X=Y^{-1}$ be relaxed to $X\geq Y^{-1}$ without losing the equivalence to the above optimization and then $X\geq Y^{-1}$ be converted to an LMI constraint (using Schur complement) which would make the problem convex. But I am stuck in being able to prove that this relaxation makes the modified problem equivalent to original problem.
No, the constraint $Y=X^{-1}$ makes the problem non-convex. The feasibility set is given by the intersection of that surface and the the set $X\geq X_0$, which is convex.
On the other hand, if we relax the equality constraint into the inequality constraint $Y\succeq X^{-1}$. The problem becomes convex since the $Y\succeq X^{-1}$ defines a convex set as it can be reformulated as the linear matrix inequality in $X$ and $Y$
$$\begin{bmatrix}X & I\\I & Y\end{bmatrix}\succeq0.$$
A way to see why this relaxation yields a zero gap is that the cost function is affine and, therefore, harmonic. Those functions are known to attain their minimum/maximum on boundary of compact sets. The issue here is that the feasibility set is not compact but it is bounded below in this regard the minimum will be attained on the boundary (there is not maximum though). We can easily compactify the set by introducing $X_1\succ0$ large enough so that the optimization problem with that extra constraint $X\preceq X_1$ has the same optimal value. The feasibility set is now compact and the optimal $X,Y$ will be on the boundary of that compact set.
I have shown in my previous answer on a similar question (Analytical solution to trace minimization) that the optimal solution tries to makes $X$ close to $X_0$ (or even at $X_0$ when possible). This is because the optimal solution needs to be at the boundary and because the cost ifs affine and increasing in $X$.
Similarly, one can see that the term $\mathrm{trace}(AY)$ is also an affine and increasing function of $Y$. To see that just perturb $Y$ with $\epsilon uu^T$ for some $\epsilon\in\mathbb{R}$ and $u\in\mathbb{R}^n$. We then have
$$\mathrm{trace}(A(Y+\epsilon uu^T))=\mathrm{trace}(AY)+\epsilon u^TAu.$$
Since $A$ is positive definite (see the other post), them the perturbation is positive for all $u$ and $\epsilon$. This means that the optimization problem will always favor the smallest $Y$ and this smallest $Y$ will be the one that makes the inequality and equality; i.e. $Y=X^{-1}$.
In this regard, one can develop the following procedure: set $X$ to a certain value, pick $Y=X{-1}$ and evaluate the cost, then perturb $X$ and perform the procedure again.