Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.