While in optimization problems, usually, the goal is to find an extremum, I'm interested in finding the first feasible solution that satisfies all constraints (i.e. the nearest critical point to my initial point). In other words, I want to move from the initial value of the objective function and stop exploring as soon as the constraints are satisfied. Is there any safe technique to find exactly the nearest solution?

To clarify, see this image:

enter image description here

I'm currently using gradient descent to find the critical points of the Lagrangian formed from the objective function and the constraints. The critical points of Lagrangians occur at saddle points, rather than at local maxima (or minima). Unfortunately, many numerical optimization techniques (e.g. gradient descent) are designed to find local maxima (or minima) and not saddle points. So, in my problem, it moves over (or escapes) from some critical points in its path and tends to find an extremum.

  • $\begingroup$ Are you really looking for the nearest solution, or just the first one the algorithm happens to be able to find? If it is the former, then you still have an optimization problem, just one with a different objective; e.g., something like $\|x-x_0\|$. $\endgroup$ – Michael Grant Jun 22 '17 at 0:45
  • $\begingroup$ This should really not be tagged as convex optimization. $\endgroup$ – Michael Grant Jun 22 '17 at 0:46

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.