2
$\begingroup$

I have the following constraints:

$\sum_{1\leq i,j\leq n,\ i\neq j} x_ix_j\geq 0.25$

$0\leq x_i \leq 1$ for $i=1, \ldots, n$

Is this set convex?

I think so, but $0.25-\sum_{1\leq i,j\leq n} x_ix_j$ is a convex function? or not? Note that I have $x_i$ are all nonnegative.

Can someone give me a reference on these questions. Standard textbook often talks about a function $R^n \rightarrow R$.

Many thanks.


Updated: following some feedbacks after the first post, I realized that I forgot to put $i\neq j$. I meant constraints like $xy\geq 0.2$ and $0\leq x \leq 1$ and $0\leq y\leq 1$.

  • 0
    Following @RahulNarain's comment, in the context of the other constraints on $x_i$, the first constraint is equivalent to $(x_1+...+x_n) \geq 0.5$, so yes the set is convex.2012-04-16

1 Answers 1

2

Consider the set $\mathcal{A} = \{\mathbf{x}:0.25 -\mathbf{x}^T \mathbf{Q} \mathbf{x} \leq 0; \mathbf{x} \in \mathbb{R}^n\}$, where $\mathbf{Q}$ is a matrix with $0$s on the diagonal and $1$s everywhere else. $-\mathbf{Q}$ has $n-1$ eigenvalues equal to $1$ and one eigenvalue equal to $-(n-1)$. Hence, it is not non-negative definite, making $\mathcal{A}$ non-convex. A simple diagram in $\mathbb{R}^2$ illustrates this. $\mathcal{A}$ would consist of the region bounded by the rectangular hyperbola $x_1x_2 = 0.25$ excluding the origin. This set is clearly non-convex due to the presence of two disconnected lobes.

However, I think that its intersection with the set $\mathcal{B} = \{\mathbf{x}:x_i \in [0,1] \forall i\}$ is convex. I would summon the picture in $\mathbb{R}^2$ to help my case. Intersection of $\mathcal{A}$ with $\mathcal{B}$ restricts the set to a subset of only one shaded lobe of $\mathcal{A}$, which is a convex set. Hence, we have the intersection of two convex sets, and end up with a convex set.

  • 0
    What does the two disconnected lobes here mean? Could please provide the picture drawn by Matlab? Since my picture shows it is convex. (Maybe my result is wrong)2015-01-19