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

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.

• I find it difficult to select an answer, among multiple valid examples. I think I will go with the trigonometric functions because they have the nice property that the convexity of the feasible set is only given by the intersection of the individual constraint's regions. – Robert Schwarz Oct 11 '19 at 18:51

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}$$

• That's interesting. So the region would be restricted to $x \in [0, \pi]$, actually, and look kind of like a lemon? – Robert Schwarz Oct 11 '19 at 14:04
• Exactly. And we could adapt this formulation in a non-smooth setting, by taking a triangle wave signal for instance. – fpacaud Oct 11 '19 at 14:09

+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.

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.

• Yes, those are important classes. I was actually aware of both. But in these cases, suitable reformulations are known, so one would not have to solve them directly. – Robert Schwarz Oct 11 '19 at 18:48

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.

• Yes, my Geometric Programming example is a special case of this. – Mark L. Stone Oct 11 '19 at 18:43
• So, this is basically a method of taking a convex optimization problem and then "destroying" the structure? – Robert Schwarz Oct 11 '19 at 18:49
• The structure is still there, it is just obscured. The term "hidden convexity" is also used. – Kevin Dalmeijer Oct 12 '19 at 2:47