Examples of problems with non-convex constraint functions but convex feasible region

Question

I'm looking for examples of (classes of) problems with a non-convex, non-linear formulation, but convex feasible region.

That is, a problem of the sort: $$ \begin{array}{lll} \text{minimize} & c^Tx & \\ \text{subject to} & g_i(x) \le 0 & (i \in I) \end{array} $$ where at least some of the $g_i$ are non-convex.

At the same time, the feasible region $F = \{ x \in \mathbb{R}^n \ | \ g_i(x) \le 0, i \in I \}$ should be a convex set. Preferably $F$ is full-dimensional, in the sense of containing a small ball.

For $g_i$, both smooth and non-smooth examples would be interesting.

UPDATE: Bonus points for problems that have some practical relevance. I would like to use such an example as motivation for a method to solve these kinds of problems.

Answer 1

Couldn't we use a combination of trigonometric functions ? E.g.

\begin{cases} x \in [0, 2\pi] \\ y \le \sin x \\ y \ge -\sin x \end{cases}

Answer 2

+1 for answer by @fpacaud .

Here are two non-contrived examples, which commonly arise in modern O.R. optimization.

1. Rotated Second Order Cone, which arises in Second Order Cone Programming.

For simplicity, I'll show the formulation for 3-D.

\begin{align}x^2 &\le yz\\y &\ge 0\\z &\ge 0\end{align}

Moving everything to the Left-Hand Side (LHS), the first inequality is $x^2 - yz \le 0$, for which the LHS is neither convex nor concave as a function of $x,y,z$, even when restricted to $y \ge 0, z \ge 0$. yet the Rotated Second Order Cone describes a convex region. Re: the update bonus, there are already efficient algorithms for solving these problems.

2. Geometric Programming See A tutorial on geometric programming, Stephen Boyd, Seung-Jean Kim, Lieven Vandenberghe, Arash Hassibi, Optim Eng (2007) 8: 67–127.

As seen in section 2.2 of the link, the standard form has constraints $f_i \le 1$, in which the $f_i$ are non-convex posynomials (although they are log-convex). Yet when a logarithmic transformation is applied, as shown in section 2.5 of the link, the constraint region becomes convex. This shows convexity is not invariant to change of variables, and is not an inherent geometric property of the constraint region. Re: the update bonus, there are already efficient algorithms for solving Geometric Programs.

Answer 3

For any monotonic function $f:\mathbb{R} \rightarrow \mathbb{R}$ your problem is equivalent to $$ \begin{array}{lll} \text{minimize} & c^Tx & \\ \text{subject to} & h_i(x) \le f(0) & (i \in I) \end{array} $$ with $h_i(x) = f(g(x_i))$.

In this case, $h_i(x)$ need not be convex. You can see this by taking $f(x) = x^3$ for example.