2

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$.

Michael Hardy
  • 1
user29271
  • 247
  • Isn't your constraint equal to $\big(\sum_{1\le i\le n} x_i\big)^2 \ge 0.25$? –  Apr 16 '12 at 22:10
  • 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. – copper.hat Apr 16 '12 at 23:40

1 Answers1

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.

Kartik Audhkhasi
  • 1,496
  • 9
  • 12
  • 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) – sleeve chen Jan 19 '15 at 23:08