This SDP problem with the variable $X \in \mbox{S}^n$ where $\rho \gt 0$ $$\max \mbox{Tr}(AX) - \rho \mbox{1}\lvert X \rvert \mbox{1} \\ \mathrm{subject\; to}\;\mbox{Tr}(X)=1, \\ X \succeq 0 $$

is rewritten as $$\max_{\mbox{Tr}(X)=1, \\ X \succeq 0} \;\; \min_{\lvert U_{ij} \rvert \le \rho} \mbox{Tr}(X(A+U)) \\ $$

Then this yields the following dual $$ \min \lambda^{max}(A+U) \\ \mathrm{subject\; to}\;\lvert U_{ij} \rvert \le \rho\;\;i,j=1,\dots, n $$

Why is this dual problem maximum eigenvalue problem? My old optimization text says the dual problem obtained from Lagrange Dual function which is the infimum of the Lagrangian. So I think $\rho$ is the Lagrange multiplier but maximum eigenvalue problem seems so different type of problem.

This is from the paper http://www.cs.berkeley.edu/~jordan/papers/CSD-04-1330.pdf



You must log in to answer this question.