# Correct way to set a quadratic constraint Xpress

I'm implementing on Xpress a problem with different solution proposed on a paper. The idea is to decompose a matrix $$X$$ into a convex sum $$\sum_{t}\lambda_t M^{(t)}$$, where each $$M^{(t)}$$ has only either $$0$$ or $$1$$, better stated we have that $$M^{(t)} = (m^{(t)}_{ij})_{ij}$$ and each $$m_{ij}$$ is a binary variable. In order to find such decomposition, we consider another continuous variable $$\alpha$$ and resolve the problem:

\begin{align} &\min\; \alpha \tag{1}\\ &\text{s.t.}\\ &\sum_{t}\lambda_t = 1 \tag{2}\\ &\sum_{j} m^{(t)}_{ij}\leq 1 \quad \forall i\;\forall t \tag{3}\\ &\sum_{i}m^{(t)}_{ij}\leq q_{i} \quad \forall j\;\forall t \tag{4}\\ &\sum_{t}\lambda_t M^{(t)} - X \geq 0 \tag{5}\\ &\sum_{t}\lambda_t M^{(t)} - X \leq \alpha\tag{6}\\ &\lambda_t,\alpha\geq 0 \end{align}

Equations $$(5)$$ and $$(6)$$ are problematic because they are quadratic and would yield a non convex region. We can linearize it by introducing a variable $$z^{(t)}_{ij}=\lambda_{t}m^{(t)}_{ij}$$ where $$Z^{(t)} = (z^{(t)}_{ij})_{ij}$$ which ultimately changes the equations to: $$\sum_t Z^{(t)} - X \geq 0\qquad\text{and}\qquad \sum_{t}Z^{(t)} - X \leq\alpha$$ which is now linear but requires the additional constraints: $$\forall i, j,t\hspace{2mm}: 0\leq z_{ij}^{(t)}\leq \lambda_t \qquad z_{ij}^{(t)}\geq \lambda_t + m_{ij}^{(t)}-1$$
The code runs perfectly with a non trivial output, meaning that the problem is feasible. Nontheless the new solution looses the meaning of the initial implementetion: the non linearized equation would have given as a result, $$0-1$$ matrixes, which is my aim actually. By linearizing, the solution looses any interpretation (as the $$z$$'s need now to be continuous variables). What's the best idea to set back now? Is dividing each $$Z^{(t)}$$ by its $$\lambda_t$$ and rounding the numbers a meaningful step?

• Is $\lambda_t$ a nonnegative variable? Is $q_i$ a constant? Commented Dec 9, 2022 at 20:22
• What is the relationship between $m_{ij}$ and $M^{(t)}$?
– prubin
Commented Dec 9, 2022 at 22:42
• @prubin I'll edit to clarify. Commented Dec 11, 2022 at 17:10
• @RobPratt the $\lambda_t$ are coefficients of a convex combination, so by definition they are nonnegative. The $q_i$, as well as $X$, are constants given by the problem. Commented Dec 11, 2022 at 17:17
• The reason this is not allowed is that Xpress only supports convex MIQCPs. Any nonlinear equality constraint makes the problem immediately non-convex. Commented Dec 29, 2022 at 17:06

I can't help you with Xpress, but one approach is to linearize the problem by replacing the products $$\lambda_t m_{ij}^{(t)}$$ with new nonnegative variables $$z_{ijt}$$, together with constraints that enforce the product. See How to linearize the product of a binary and a non-negative continuous variable?

• thank you very much for your help. Indeed I did not know about such trick but it introduces a new challenge. How do we get back to binary matrixes? Commented Jan 2, 2023 at 21:49
• @DavideTrono You should still impose that $m_{ij}^{(t)}$ is binary. Commented Jan 2, 2023 at 21:54
• $m^{(t)}_{ij}$ is binary, the $z^{(t)}_{ij}$ I thought should be the same type as the $\lambda$'s. This is so because otherwise the output is: $\lambda_0=1$ (with all the remanings equal to 0) and $Z^{(0)}$ being $1$ where $X$ is non zero. Arguably okay result. Commented Jan 2, 2023 at 22:09
• Yes, $z$ is the same type (nonnegative continuous) as $\lambda$. Your linearization is missing $z_{ij}^{(t)} \le m_{ij}^{(t)}$. Commented Jan 2, 2023 at 22:15
• Without the missing constraint, you are not enforcing the implication $m_{ij}^{(t)} = 0 \implies z_{ij}^{(t)} = 0$. Commented Jan 2, 2023 at 22:22