9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Robert Schwarz Oct 11 '19 at 18:51
10
$\begingroup$

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}

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

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

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Robert Schwarz Oct 11 '19 at 18:48
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.