1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – tyrela
    Mar 9 at 3:23
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 10 at 2:28
  • $\begingroup$ Got it! Really thanks for the explanation. Now I got it the slack here is for the linear function here. Sorry for replying late. $\endgroup$
    – tyrela
    Mar 10 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.