0

Let $w_1, \ldots, w_m$ and $x$ be vectors in $\mathbb{R}^n$, and $\gamma$ be some constant in $\mathbb{R}$.

How can I prove that the set $\{ x \in \mathbb{R}^n: \max\{w_1^Tx, \ldots, w_N^Tx\} \geq \gamma\}$ is not convex in general?

(I'm asking for a proof and not for a counterexample.)

Thanks

rnegrinho
  • 403
  • 1
    "Prove that some property does not hold in general" is a problem that practically begs for a counterexample. And a counterexample is ample proof. It is often the only way to prove that there are cases where the property does not hold. That being said, if $\gamma > 0$, then $0$ won't be in your set. That's a good place to start looking for a counterexample. – Arthur Jan 31 '14 at 17:13
  • I would like to get the counterexample by assuming a minimal amount of stuff about $w_1, \ldots, w_N$. The constant $gamma$ you can choose for yourself. While it is easy to see that the $\leq$ sign yields a convex set, the non convexity of this set does not seem immediate, even though it is easy to come up with counterexamples in particular cases. – rnegrinho Jan 31 '14 at 17:27

2 Answers2

1

Proposition. Let $n\in \mathbb N$ be arbitray, $N\ge 2$, $w_1,\ldots, w_N\in\mathbb R^n$ arbitrary, $\gamma>0$. Assume that there exist $1\le i<j\le N$ such that the only solution to $$\alpha w_i+\beta w_j=0\qquad\text{with }\alpha\ge0,\beta\le 0 $$ is the trivial solution $\alpha=\beta=0$. (For example, if $w_i,w_j$ are linearly independant).

Then the set $$ S = \{\,x\in\mathbb R^n:\max\{w_1^Tx,\ldots w_N^Tx\}\ge \gamma\,\}$$ is not convex.

Proof: It suffices to show that $S\cap\langle w_i,w_j\rangle$ is not convex. In other words, it suffices to consider the cases

  • $n=2$ and $w_i,w_j$ linearly independant
  • $n=1$ and $ w_i\ne0$, $w_j=cw_i$ with $c<0$.

First case: If $w_i={a\choose b}$ and $w_j={c\choose d}$, then we have $ad-bc\ne0$ from linear independence. Let $v={b+d\choose -a-c}$. Then $$w_i^Tv=a(b+d)-b(a+c)=ad-bc$$ and $$w_j^Tv=c(b+d)-d(a+c)=bc-ad.$$ Therefore the two points $$\pm\frac \gamma{ad-bc}v$$ are in $S$, but theri midpoint $0$ is not.

Second case: We have $\frac{\gamma}{w_i^Tw_i}w_i\in S$ and $\frac{\gamma}{cw_i^Tw_i}w_i\in S$, but the point $0$ between them is $\notin S$. $_\square$

Remark: If no $i,j$ as in the proposition exist, then either all $w_i$ are zero (making $S$ empty and hence convex if $\gamma>0$) or are nonnegative multiples of one nonzero vector (making $S$ a half-space and hence convex, even if $\gamma\le 0$).

Hagen von Eitzen
  • 374,180
  • Why the restriction on $\alpha$ and $\beta$? Couldn't they just belong to $\mathbb{R}$? – rnegrinho Jan 31 '14 at 18:45
  • 1
    If I replace "with $\alpha\ge 0,\beta\le 0$" with "with $\alpha,\beta\in\mathbb R$", the condition just says "linearly independant". My restriction additionally (that's why I added "For example .. independant") catches cases where the vectors are dependant but point in opposite directions. And as the remark shows, this allowed me to "catch them all". – Hagen von Eitzen Jan 31 '14 at 21:11
0

You can see this as a set of inequalities $$ w_ix \geq \gamma $$ which defines a half-space (with boundary hyper-plane which is orthogonal to $w_i$). The way you put the inequalities together (with the $\max$-function) makes the resulting set the union of these half-spaces. Can you take it from there?

Arthur
  • 199,419