0
$\begingroup$

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?
$\endgroup$

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.