0
$\begingroup$

Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$

$\pmb{c}$ is a $n\times1$ matrix.

$G$ is a $n\times n$ matrix which is also positive definite.

matrices $G$ and $c$ are real.

$L$ is a $n\times 1$ matrix whose entries are from the set $\{-1,1\}$.

Can this equation be solved for the matrix $\pmb{c}$? Suppose there is no signum function there, then the solution is $$\pmb{c} = (G+I_n)^{-1}L$$ and as $G$ is positive definite, there exists a unique solution. But with the presence of the $\text{sign}$ function, the problem doesn't seem to belong to linear algebra. I request for a reference to any subject or book for this type of equations. Does this belong to linear programming?(I don't know anything about it, so I am hoping it is related).

PS: please tag appropriately.

PS 2: $\text{sign}([a_{i,j}]_{m\times n}) = [\text{sign}(a_{i,j})]_{m\times n}$.

$\endgroup$
1
  • $\begingroup$ Cross-posted here $\endgroup$
    – RobPratt
    Sep 27, 2020 at 16:36

1 Answer 1

1
$\begingroup$

You can solve the problem via mixed integer linear programming as follows. Let $\epsilon>0$ be a small constant tolerance. For $i \in \{1,\dots,n\}$, let $[\ell_i,u_i]$ be constant lower and upper bounds on $(Gc)_i$, and let binary decision variables $z^-_i$ and $z^+_i$ indicate whether $(Gc)_i<0$ or $(Gc)_i>0$, respectively, so $\text{sign}(G\pmb{c})=\pmb{z^+}-\pmb{z^-}$. The constraints are: \begin{align} c_i - z^-_i + z^+_i &= L_i &&\text{for all $i$} \tag1\\ z^-_i + z^+_i &\le 1 &&\text{for all $i$} \tag2\\ \ell_i z^-_i + \epsilon z^+_i \le (Gc)_i &\le -\epsilon z^-_i + u_i z^+_i &&\text{for all $i$} \tag3 \end{align} Constraints $(2)$ and $(3)$ together enforce three cases: \begin{align} (z^-_i,z^+_i)=(1,0) &\implies (Gc)_i\le -\epsilon < 0 \\ (z^-_i,z^+_i)=(0,0) &\implies (Gc)_i = 0 \\ (z^-_i,z^+_i)=(0,1) &\implies (Gc)_i\ge \epsilon > 0 \end{align}

$\endgroup$
8
  • $\begingroup$ Thanks RobPratt. Any algorithm available to solve this? $\endgroup$
    – Rajesh D
    Sep 27, 2020 at 22:03
  • $\begingroup$ Branch-and-cut is the state-of-the-art algorithm for mixed integer linear programming (MILP). $\endgroup$
    – RobPratt
    Sep 27, 2020 at 23:01
  • $\begingroup$ One last question, I understood the constraints, but what is it that should be minimized? As I read any MILP problem has constraints and a minimization problem. $\endgroup$
    – Rajesh D
    Sep 28, 2020 at 3:16
  • $\begingroup$ Should we minimize the tolerance $\epsilon$? $\endgroup$
    – Rajesh D
    Sep 28, 2020 at 3:56
  • $\begingroup$ If you only care about finding a vector that satisfies the constraints, just use the constant 0 as the objective function. More generally, you can use any linear function of the decision variables. $\endgroup$
    – RobPratt
    Sep 28, 2020 at 3:56

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.