Convex Sets Versus Convex Functions

Question

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

Answer 1

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.