# Intersections of supports constraint

Let $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ and $\text{supp}(\mathbf{x}) \subset \{1,2,...,n\}$ denote the set of indices such that $\mathbf{x}$ is non-zero.

What type of optimization problem can model the following constraint? $\text{supp}(\mathbf{x}) \ \cap \ \text{supp}(\mathbf{y}) = \emptyset$

Suppose that $\mathbf{x}\ge0$ and $\mathbf{y}\ge0$. Then a necessary and sufficient condition for $\mathrm{supp}\{\mathbf{x}\}\cap\mathrm{supp}\{\mathbf{y}\}=\emptyset$ is for the two vectors to be orthogonal, $\mathbf{x}^{T}\mathbf{y}=0$. Indeed, this is the familiar strong duality condition for linear programming: $$\mathbf{x}_{i}\mathbf{y}_{i}=0\;\forall i\in\{1,\ldots,n\}\overset{\mathbf{x}\ge0,\;\mathbf{y}\ge0}{\iff}\mathbf{x}^{T}\mathbf{y}=0.$$
In the general case, we may define $\mathbf{u}$ and $\mathbf{v}$ to bound the element-wise absolute values of $\mathbf{x}$ and $\mathbf{y}$, as in $$-\mathbf{u}\le\mathbf{x}\le\mathbf{u},\quad-\mathbf{v}\le\mathbf{y}\le\mathbf{v}.\tag{*}$$ It is clear that $\mathbf{u}\ge0$ and $\mathbf{v}\ge0$ are implicitly enforced. Now, combining this with the orthogonality condition, the following is a necessary and sufficient statement for $\mathrm{supp}\{\mathbf{x}\}\cap\mathrm{supp}\{\mathbf{y}\}=\emptyset$: $$\text{There exists }\mathbf{u},\mathbf{v} \text{ satisfying (*) and } \mathbf{u}^{T}\mathbf{v}=0.$$ Note that the condition is generally nonconvex, and problems involving such constraints are usually NP-hard. Some special cases, however, can be solved in polynomial time using geometric programming or semidefinite programming techniques.
• Thanks for your answer! Could you please elaborate why $\mathbf{u}^T \mathbf{v} = 0$ implies that the support intersection will be empty? – iglesias May 1 '17 at 8:04
• I'm essentially making the argument that $\mathrm{supp}(\mathbf{x})\cap\mathrm{supp}(\mathbf{y}) = \emptyset$ is equivalent to the condition $|\mathbf{x}_i| |\mathbf{y}_i| = 0$ for all $i$. Then I used a basic identity from linear programming to show that this is true if and only if $\sum_i |\mathbf{x}_i| |\mathbf{y}_i| = 0$ – Richard Zhang May 1 '17 at 19:20