# Equivalent Convex programs with different solutions

Let $$R_\kappa \in \mathbb{R}^{d \times d}_{sym}$$, $$S_\kappa \in \mathbb{R}^{d \times d}_{sym}$$, $$\eta_\kappa \in \mathbb{R}^+$$, for a set $$\{ \kappa \}$$. Define a optimization problem $$(1)$$ as \begin{align} &\min_{\{S_\kappa\}} \sum_\kappa \eta_\kappa \exp( tr(R_\kappa S_\kappa) )\\ \text{s.t.}\quad& 2 (\sum_\kappa \exp(tr(S_\kappa)/2) - C) \leq 0\\ &\frac{1}{2}(\| S_\kappa \|^2_{Fr} -\alpha^2 ) \leq 0,\quad \forall \kappa \end{align} which is convex, and provided there is a feasible interior point has an optimal solution.

If I then have the function $$\phi(x) = \begin{cases} x^2,&x>0\\0,& x\leq 0 \end{cases}$$ and apply this to the second constraint I can get optimization problem $$(2)$$ \begin{align} &\min_{\{S_\kappa\}} \sum_\kappa \eta_\kappa \exp( tr(R_\kappa S_\kappa) )\\ \text{s.t.}\quad& 2 (\sum_\kappa \exp(tr(S_\kappa)/2) - C) \leq 0\\ &\frac{1}{4}\phi(\| S_\kappa \|^2_{Fr} -\alpha^2)\leq 0,\quad \forall \kappa \end{align}

$$\phi$$ is a convex function, and the feasible sets for both optimizations are the same, thus both $$(1)$$ and $$(2)$$ should have the same solution.

The first KKT condition for $$(1)$$ applied to the Lagrangian gives \begin{align} 0 &= \eta_\kappa R_\kappa \exp(tr(R_\kappa S_\kappa) ) + \lambda \mathcal{I} + \mu_\kappa S_\kappa \end{align} and applying the trace decomposition $$A = a\mathcal{I} + \tilde{A}$$ where $$tr(\tilde{A}) = 0$$ gives \begin{align} 0 &= \eta_\kappa \tilde{R}_\kappa \exp(tr(R_\kappa S_\kappa) ) + \mu_\kappa \tilde{S}_\kappa \end{align}

The Lagrangian of $$(2)$$ is \begin{align} \sum_\kappa \eta_\kappa \exp(tr(R_\kappa S_\kappa) + 2\lambda (\sum_\kappa \exp(tr(S_\kappa)/2) - C) + \sum_\kappa \frac{\mu_\kappa}{4}\phi(\| S_\kappa \|^2_{Fr} -\alpha^2) \end{align} differentiating w.r.t $$S_\kappa$$ and setting equal to $$0$$ gives \begin{align} 0 &= \eta_\kappa R_\kappa \exp(tr(R_\kappa S_\kappa) ) + \lambda \mathcal{I} + \mu_\kappa S_\kappa \begin{cases} (\| S_\kappa \|^2_{Fr} -\alpha^2), & \| S_\kappa \|^2_{Fr} -\alpha^2 > 0\\ 0, & \| S_\kappa \|^2_{Fr} -\alpha^2 \leq 0 \end{cases} \end{align} applying the trace decomposition gives \begin{align} 0 &= \eta_\kappa \tilde{R}_\kappa \exp(tr(R_\kappa S_\kappa) ) + \mu_\kappa \tilde{S}_\kappa \begin{cases} (\| S_\kappa \|^2_{Fr} -\alpha^2), & \| S_\kappa \|^2_{Fr} -\alpha^2 > 0\\ 0, & \| S_\kappa \|^2_{Fr} -\alpha^2 \leq 0 \end{cases} \end{align}

which gives a contradiction: from primal feasibility we are on the $$0$$ branch, but we also know that $$\tilde{R}_\kappa\neq 0$$. What have I done wrong here?

• Taking the derivative of the trace gives the identity, $\frac{d tr(S_\kappa)}{d S_\kappa} = \mathcal{I}$, and taking the derivative of the exponential of trace comes from the chain rule. – NeedsToKnowMoreMaths Jan 15 at 20:03
• You need some regularity conditions to apply KKT. For example, the second version of the second constraint can never be strictly feasible. – copper.hat Jan 15 at 20:33
• So then the second problem has the same primal solution, but does not have a dual solution? – NeedsToKnowMoreMaths Jan 15 at 21:24
• I would have to think about that. The first problem has no duality gap because of Slater. I would need to do a little work to check if strong duality holds for the second problem. – copper.hat Jan 15 at 21:31