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?

  • $\begingroup$ 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. $\endgroup$ – NeedsToKnowMoreMaths Jan 15 at 20:03
  • 1
    $\begingroup$ You need some regularity conditions to apply KKT. For example, the second version of the second constraint can never be strictly feasible. $\endgroup$ – copper.hat Jan 15 at 20:33
  • $\begingroup$ So then the second problem has the same primal solution, but does not have a dual solution? $\endgroup$ – NeedsToKnowMoreMaths Jan 15 at 21:24
  • $\begingroup$ 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. $\endgroup$ – copper.hat Jan 15 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.