2
$\begingroup$

I think this is a problem a lot of people have in minimization but I couldn't find algorithmic approaches to it.

Given a closed domain $D\subset R^n$ over which a function $f$ is supposed to be minimized and a point $x_0\in R^n$, how can I find $x \in D$ which minimizes $||x - x_0||_2$?

The problem is, $D$ is given rather implicitly through boundary conditions of an optimization problem (linear and nonlinear). I'm trying to find a heuristic in which if I did a "jump outside of my feasible domain", I'd be able to get right back in. I can try to jump somewhere else of course but I've seen often that empirically my violation is rather small and a "small bump" would bring me a lot closer to my local minimum, so I'd rather do that instead of invalidating the step alltogether.

Are there some algorithms that handle this?

$\endgroup$
8
  • 1
    $\begingroup$ Perhaps you can give us details for the entirety of the problem. $\endgroup$ Sep 12, 2023 at 14:53
  • $\begingroup$ I'm looking to improve a non-convex optimization problem heuristically by 'random restarts' and/or random jumps during a search. It's possible that the newly chosen point lands outside of the domain. Is there a way to project it back to the domain? The domain D is defined as 'inside of my boundary conditions', which are mixed between linear and nonlinear inequality constraints. I can of course check whether my point lies within the constraints or not but I was wondering if there is some iterative procedure which would converge when the point is inside my domain. $\endgroup$
    – not_sure95
    Sep 12, 2023 at 15:27
  • $\begingroup$ The only way I know to reliably project into a non-convex constraint set is to use a global solver. The irony that you are doing this as part of a global (?) optimization is not lost on me. That said, depending on the constraints, whose details you have yet to provide, perhaps something better can be done .. or you can be lucky (or at least not unlucky). $\endgroup$ Sep 12, 2023 at 16:12
  • $\begingroup$ That is the exact irony which brought me to stackexchange :) I mean, technically I am trying to maximize $1_{x \in D}$ under the condition that $|| x - x_0 ||$ becomes minimal but that's not solvable for me besides randomly trying out points until I land in the domain by chance first. I worked out a bit more of the problem - the constraints are a bit difficult. I have a $4n$-dimensional problem in which I now have a linear boundary condition $Ax \geq 0$, so I can actually reduce it to linear constraints. I have the feeling that should make it a lot easier. (1/2) $\endgroup$
    – not_sure95
    Sep 12, 2023 at 21:45
  • $\begingroup$ (2/2) The problem itself is a curve fitting problem, $n$ curves with 4 parameters fitting into a cloud of points in a way hat they don't intersect (that condition can be represented at least in a "weak form" as a linear boundary condition) while all curves must lie in a certain domain, which gives the second set of linear boundary conditions (the asymptotics of the curve make the boundary linear, which in practice seems to work out well enough subasymptotically). The fitting itself is more or less LSQ of that problem jointly. $\endgroup$
    – not_sure95
    Sep 12, 2023 at 21:55

1 Answer 1

0
$\begingroup$

I think the problem you are describing is known as constrained optimization or constrained minimization, where you want to minimize a function within a certain domain defined by constraints. In your case, the constraints are given implicitly.

There are several approaches to handle constrained optimization problems, and the choice of method depends on the nature of your problem. Here are a few common methods that might be relevant to your situation:

  1. Penalty Function Method: You can convert the constrained optimization problem into an unconstrained problem by adding a penalty term to your objective function. This penalty term penalizes violations of the constraints, and you can adjust the penalty parameter to balance between staying within the feasible domain and minimizing the objective function.

  2. Barrier Function Method: Similar to the penalty method, you can use barrier functions to transform the constrained problem into an unconstrained one. Barrier functions become very large as you approach the boundary of the feasible region, discouraging the optimization algorithm from moving outside of it.

  3. Interior Point Methods: These methods work directly within the feasible region by iteratively moving towards the optimum while respecting the constraints. They are particularly useful for problems with both equality and inequality constraints.

  4. Augmented Lagrangian Method: This approach combines the ideas of penalty functions and Lagrange multipliers to solve constrained optimization problems. It involves iteratively updating Lagrange multipliers and penalty parameters.

  5. Sequential Quadratic Programming (SQP): SQP is an iterative method that approximates the constrained problem by solving a sequence of unconstrained quadratic subproblems, taking into account the constraints at each step.

And finally, the one I think you have in mind...

  1. Genetic Algorithms or Simulated Annealing: These are heuristic methods that can explore the feasible region, making occasional "jumps" outside and returning while maintaining a balance between exploration and exploitation.

The choice of method depends on the specific characteristics of your problem and the computational resources available. Some problems may benefit from hybrid approaches that combine multiple techniques. You may need to experiment with different methods to find the one that works best for your particular situation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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