6
$\begingroup$

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$

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer! Could you please elaborate why $\mathbf{u}^T \mathbf{v} = 0$ implies that the support intersection will be empty? $\endgroup$ – iglesias May 1 '17 at 8:04
  • 1
    $\begingroup$ 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$ $\endgroup$ – Richard Zhang May 1 '17 at 19:20
  • $\begingroup$ Do you have a reference regarding the last part of your first answer? A book or article where they are dealing with this type of constraint using any of the techniques you mention. Thanks in advance! $\endgroup$ – iglesias May 29 '17 at 9:42
  • $\begingroup$ Which part? The NP-hard aspect, or the geometric / semidefinite reformulations? For the latter, Boyd & Vandenberghe have a couple of excellent reviews on geometric and semidefinite programming reformulations / relaxations / approximations for nonconvex problems. $\endgroup$ – Richard Zhang May 30 '17 at 12:42
  • $\begingroup$ I referred to the latter indeed; the special cases where an intersection of supports constraint can be reformulated in a convex problem. $\endgroup$ – iglesias May 30 '17 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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