# Convex Sets Versus Convex Functions

Can we specify all convex sets, in terms of convex constraints (convex inequality functions) on a variable?

-
If $C$ is a convex set, then the indicator function $I_C$ is convex, and $x \in C \iff I_C(x) \leq 0$. –  littleO Nov 17 '12 at 7:50
Exactly what @littleO says. If you wanted your function to be continuous, it's possible for closed sets and you can take $f(x)=\mathrm{dist}(x,C)$. –  yo' Nov 17 '12 at 7:57
@littleO: Let $C = [-1,1]$, and I assume you mean $I_C(x)$ is $0$ when $-1\le x\le1$ and $1$ elsewhere. But $I_C$ is not convex, because $I_C(\frac14\cdot 0 + \frac34\cdot 2) = 1 \not\le 0 = \frac14 I_C(0) + \frac34 I_C(2)$, unless you're using a different definition of convex function that I'm not aware of. –  Rahul Nov 17 '12 at 9:34
@Rahul No, in convex analysis the indicator function $I_C$ of a convex set $C$ is defined by $I_C(x) = \begin{cases} 0 &\quad \text{if } x \in C \\ \infty & \quad \text{otherwise}.\end{cases}$. –  littleO Nov 17 '12 at 10:02
@littleO: Ah, I knew it was a matter of definitions. Thanks for the clarification. –  Rahul Nov 17 '12 at 10:05

I hope I interpret your question correctly.

It depends on the space you consider the sets in. I'll assume you are only interested in convexity in Euclidean spaces. In $\mathbb {R}^1$ certainly one can identify convex sets by (very trivial) convex constraints. Simply since the convex sets in $\mathbb {R}^n$ are precisely the intervals (all sorts of intervals: closed, open, half closed, half open, rays etc.).

In $\mathbb {R}^2$ already things get more complicated and a complete answer would depend on what exactly do you mean by 'constraints'. For instance, the set $S=\{(x,y)\mid x^2+y^2<1\}$ is convex and can be described by convex constraints you have in mind. But the set $S\cup\{(x,y)\mid x^2+y^2=1,x\notin \mathbb {Q}\}$ is also convex and I'm not sure it can be given by the constraints you have in mind.

Another type of complication arises if you imagine pinching a point on the boundary of $S$ so as to raise it a bit and create a vertex. You can do that in such a way that the shape stays convex but now your constraining function becomes non-differentiable at that point. Things can be made worse by pinching at infinitely many points, keeping the shape convex, causing the constraining function to be quite nasty. Instead of pinching and creating a vertex you can also pinch and keep the boundary smooth but have the instantaneous rate of change infinite at a point or infinitely many points, again causing the constraining function to be problematic.

The bottom line is that usually sets can be more easily manipulated than functions and thus just setting a condition on a set will not generally be enough to characterize it functionally. This is not always the case of course, as seen the by low dimensional case.

-
What does $\mathbb {Q}$ stand for in your example? –  user25004 Nov 17 '12 at 8:05
The concept you explain here is way too complicated, see both comments to the question, that both give a very simple answer. –  yo' Nov 17 '12 at 8:07
@ user25004, it stands for the rational numbers (and I just corrected a typo stating \notin instead of \in). –  Ittay Weiss Nov 17 '12 at 8:08
@ tohecz, I think it depends on the interpretation of the question. I'm not sure my interpretation is what OP had in mind so you could be right and the comments more than suffice. –  Ittay Weiss Nov 17 '12 at 8:09
Very nice comment! Thank you. –  Saugata Nov 17 '12 at 8:11