# Problem understanding dual optimization problem?

I am reading this paper: http://dl.acm.org/citation.cfm?id=1390696

Following optimization problem is defined in section 2: \begin{align} \max_{\mathbf{X}>0} \log det(\mathbf{X})-trace(\mathbf{SX})-\lambda||\mathbf{X}||_1 \end{align} where $\mathbf{X}$ and $\mathbf{S}$ are $p\times p$ matrix and $\mathbf{X}$ is constrained to be positive definite.

In the next subsection, the author creates a dual representation by writing \begin{align} ||\mathbf{X}||_1 = \max_{||\mathbf{U}||_\inf \leq 1} trace(\mathbf{XU}) \end{align}

This is fine, as $||\mathbf{X}||_1 = trace(\mathbf{XU})$, if all entries of U are 1, and that is the maximum value possible. But in the next step, this is substituted in the original optimization problem to form: \begin{align} \max_{\mathbf{X}>0} \min_{||\mathbf{U}||_\inf \leq \lambda}\log det(\mathbf{X})-trace(\mathbf{(S+U)X}) \end{align} and the $\max_{||\mathbf{U}||_\inf \leq 1}$ is changed $\min_{||\mathbf{U}||_\inf \leq \lambda}$ . Changing 1 to $\lambda$ is obvious, but why is the max changed to min. Shouldn't a minus sign be placed before $\mathbf{U}$ in that case?
Is there some property of trace operator which allowed for this step?

$$a-\max_{x\in X} f(x)=\min_{x\in X}(a-f(x)),$$ this is just placing the minus sign inside the max which makes it a min.

• but then it should be $\min_{||\mathbf{U}||_\inf \leq \lambda}\log det(\mathbf{X})-trace(\mathbf{(S-U)X})$ instead of $\min_{||\mathbf{U}||_\inf \leq \lambda}\log det(\mathbf{X})-trace(\mathbf{(S+U)X})$ – user2329744 May 29 '14 at 17:13
• No, because then you would have a double negation, $-tr(-UX)=tr(UX)$. – Lutz Lehmann May 29 '14 at 17:26
• @LutzL is right; it's really that simple. Try breaking apart $\mathop{\textrm{Tr}}((S+U)X)$ into two terms, $\mathop{\textrm{Tr}}(UX)+\mathop{\textrm{Tr}}(SX)$, to help see it. – Michael Grant May 29 '14 at 19:17
• Yes, I see it now. It is simple arithmetic. Thanks for your responses – user2329744 May 31 '14 at 11:13