# How does the slack variable work in the problem formulation?

Recently I am reading a paper. In it, after they achieve eq(15), which is

$$\operatorname{Tr}(\boldsymbol{Q})-\sqrt{2 \ln (1 / \rho)} \sqrt{\|\boldsymbol{Q}\|_F^2+2\|\boldsymbol{r}\|^2}+\ln (\rho) \cdot \lambda^{+}(\boldsymbol{Q})+s \geq 0$$

Then they said "By introducing suitable slack variables, one can easily show that the above constraint is equivalent to the following system of LMI and SOC constraints: \begin{aligned} & \operatorname{Tr}(\boldsymbol{Q})-\sqrt{2 \ln (1 / \rho)} \cdot x+\ln (\rho) \cdot y+s \geq 0, \\ & \sqrt{\|\boldsymbol{Q}\|_F^2+2\|\boldsymbol{r}\|^2} \leq x, \\ & y \boldsymbol{I}_n+\boldsymbol{Q} \succeq \mathbf{0}, \end{aligned}

where $$\lambda^+(\mathbf{Q}) = max( \lambda_{max}(\mathbf{-Q}) , 0 )$$ and $$\lambda_{max}$$ means take largest eigenvalue.

I didn't quite get how this slack works, could anyone help me a little about it? The first slack actually I basically get it, but the second one I didn't really see how.

Ignoring for a moment that you are dealing with an inequality, then you are trying to introduce a variable $$y$$ that equals $$\lambda^+(Q)$$, the negative of the most negative eigenvalue of $$Q$$. The way you do this is to ask what value does $$y$$ have to have so that if you shift the spectrum of $$Q$$ by $$y$$, you end up with something that is positive semidefinite -- in other words, you need a $$y$$ so that $$Q+ yI \succeq 0.$$ Any $$y$$ that satisfies this inequality will then also satisfy $$y \ge \lambda_\text{max}(-Q).$$ Now you just have to think a bit about the fact that $$\lambda^+$$ isn't just the eigenvalue (but a non-negative version of it).
• Sir, I got a little further question here. So this "slack" procedure is more about to achieve a convex formulation or whether it makes this constraint easier to be satisfied? As for the first slack, we actually now subtracting a larger $x$ here to let the LHS larger than 0, it looks like we are demanding more here but not "slack". Maybe I misunderstand the meaning of "slack" here? Mar 9 at 3:23
• Here, the introduction of a slack variable is because you want to make the objective function linear in $y$ rather than having the awkward, nonlinear and nonsmooth $\lambda^+$ term. Of course, in general you pay for this by introducing a nonlinear and nonsmooth constraint. However, in this particular case, you get a constraint that requires a matrix to be semidefinite, and there are good techniques ("semidefinite programming", SDP) for this specific kind of constraint. Mar 10 at 2:28