1
$\begingroup$

I have a reasonably smooth non-convex non-monotone function in high(ish) dimensional space, that I wish to find a local minimizer for, over a convex feasible region (the intersection of a ball with a set of halfspaces, so a "wedge" of the ball or a polytope), with the caveat that I want the minimizer to be away from the boundary of the feasible region.

Are there any sound ways, or even just good heuristics, for doing that?

Edit: If all minimizers (or regions looking like minimizers) are around the boundary, then is there a way to detect that?

One idea I had is to use barrier functions near the boundary and then just use gradient descent, but the barrier functions might create false local minima...

Thanks!

$\endgroup$
1
$\begingroup$

Your question is not well-defined yet. You have described two criteria you want to optimize over: minimize the function, and be away from the boundary. You often can't simultaneously optimize both; the way to minimize the function might be near the boundary, and points away from the boundary might not minimize the function.

So, before you can solve this problem, you first must figure out how to formulate it in a well-posed way. Basically, you will have to decide how to trade off between your two goals. One way would be to define an objective function $\Psi(x)$ that is a sum of your function and some penalty term, where the penalty is larger the closer to the boundary you are. e.g.,

$$\Psi(x) = f(x) + 1/d(x),$$

where $f$ is your function and $d(x)$ is the distance from $x$ to the nearest point on the boundary of the feasible region. Then, you could try to minimize $\Psi(x)$. That's one possibility, but there are of course others. (This particular approach is sometimes known as a barrier method.)

Once you have formulated the problem, then you can select an optimization algorithm. Gradient descent would be a good starting point if the problem is high-dimensional and you can compute gradients. If the number of dimensions is not too large, you can also consider second-order methods, like Newton's method, trust region methods, and many others. The choice of method will depend on the properties of the function, and might also require some experimentation.

Alternatively, rather than treating both goals as soft goals to be balanced, you might decide that the "away from the boundary" is a hard requirement that absolutely must not be violated. Then you would define the region $\mathcal{R}$ of points that are away from the boundary (e.g., distance at least $D$ from the boundary, for some constant $D$ of your choice), and then your problem becomes to minimize $f$ over the region $\mathcal{R}$. There are a number of methods for doing that; you might start by trying projected gradient descent.

If you want to detect whether all minimizers are near the boundary, you can first find the absolute minimum within the feasible region (e.g., using gradient descent or projected gradient descent), then find the minimum within the region $\mathcal{R}$ of points that are away from the boundary (e.g., using projected gradient descent); if the latter is larger than the former, you know that all the minima are near the boundary (at least, up to the optimality of your optimization routine).

We can't tell you how to formulate your problem, because that depends on what you want to achieve, and only you know that. You will have to decide what your goals and requirements are, and then choose a formulation that matches your needs and goals.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer. It is exactly the "posing" of the problem I'm hoping insights for. As I mentioned, a barrier method will create false local minima, which is why I'm not doing it this way. You mentioned that sometimes the function might have only have minimizers near the boundary, in that case it'd be great to somehow detect that (I know, a lot to ask for!). $\endgroup$ – user113925 Jul 6 '18 at 17:33
  • $\begingroup$ @user113925, see updated answer. We can't tell you how to pose the problem because only you know what you're trying to achieve. Once you've figured out how to specify/formulate your problem in an unambiguous way, then we might be able to suggest algorithms or methods that might be suited for those needs, but we can't tell you what your problem is. $\endgroup$ – D.W. Jul 6 '18 at 18:05

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.