Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Isn't your constraint equal to $\big(\sum_{1\le i\le n} x_i\big)^2 \ge 0.25$? – Rahul 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

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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