I have a function

$$f(x) = \max_{1 \leq i \leq N} f_i(x)$$

Where the $f_i(x)$ are smooth, concave functions. Furthermore, $f(x)$ is a signed distance function, and I am only interested in the subset of points where $f(x) = 0$.

Given a point $p_h$, I want to find the point $p$ closest to $p_h$ such that $f(p) = 0$. Since the $f_i$ are concave, there are no guarantees as to $f(x)$ being convex nor concave, so I can't directly solve

\begin{equation*} \begin{aligned} & \underset{p}{\text{minimize}} & & || p - p_h||_2^2 \\ & \text{subject to} & & f(p) = 0, \; i = 1, \ldots, N. \end{aligned} \end{equation*}

Instead, my approach is the following

  • If $f(p_h) < 0$, I want the point such that $f(p) \geq 0$, which implies $f_i(p) \geq 0$ or, more precisely, $-f_i(p) \leq 0$; since $-f_i$ are convex, I can optimize as usual.

  • The problem lies when $f(p_h) > 0$. In this case, I need $f_i(p) \leq 0$; at this point, I am lost, as the constraints are not convex.

So there are a few questions here:

  • Is there any way I can turn the $f_i(p) \leq 0$ constraint into a convex constraint so that I can optimize as usual?
  • If not, is there any known transformation I can apply to turn it into a more amenable problem?

Your Answer

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

Browse other questions tagged or ask your own question.