0

I want to minimize a function which has sharp gradients close to each local minimum. Due to process tolerances, I want to find solutions which meet some minimum criterion (e.g. lower than x), but have a shallow gradient near to the found minimum.

My question is: is this simply a case of me assigning a penalty factor to minima with sharp nearby gradients, or is there a class of algorithm that can handle this sort of constraint as part of its optimization routine?

Sean
  • 101
  • 1
  • What do you mean by "sharp"? – anymous.asker Nov 08 '18 at 19:51
  • @anymous.asker: large gradient. – Sean Nov 08 '18 at 21:27
  • Well, every local optima should have a small gradient around that turns to zero as it approaches it, otherwise it wouldn't be a local optimum. If the gradients are not lipschitz, then gradient descent might not be the right tool for the job. If you are up to coding something yourself, you might want to use something like guided local search, perhaps by adding log-barriers or something at those minima. Or you might want to instead try global optimization techniques not based on gradients. Would be helpful if you could provide an example. – anymous.asker Nov 09 '18 at 07:45
  • @anymous.asker: I mean that, for a good solution, the approach to the minimum should be shallow, i.e. the rate of change of the function should be less than some parameter. My question is essentially about whether this parameter is something I have to define in my cost function, or if there are algorithms that can consider this property already. Currently I'm trying to find existing algorithms before attemping to code something myself. Right now I just don't know what to search for. – Sean Nov 09 '18 at 08:10
  • @anymous.asker: I don't have a problem providing the solution except it's a large piece of code that I don't think is relevant. My question is more about classes of algorithm rather than the intricacies of my particular problem right now. – Sean Nov 09 '18 at 08:11

2 Answers2

1

Well, that’s a tricky question. Do the gradients turn large somehow because they are discontinuous? (gradient descent will likely not work then) Is it maybe because the variables are in too different scales (Newton & related would help)? Is there some sort of barrier that would limit the domain (e.g. log(x))? Does the function have some flat uniform area, e.g. __/? Are these saddle points? Is your problem constrained and these are solutions at the boundaries? In some of these cases, switching to something different like subgradients might help you, but this highly depends on the reason why your problem has these optima that you want to avoid.

Generally speaking, gradient-based techniques converge to whatever local optimum they find first, and if you are not happy with that, you’ll have to use other metaheuristics (e.g. add restarts, incorporate penalties at known optima, use derivative-free methods). Perhaps other techniques that carry momentum like ADAM might somehow allow you to dodge these too.

anymous.asker
  • 844
  • 4
  • 10
  • My function is continuous. I don't think there are saddle points, just local minima of different depths. There are 6 parameters given to the function, each with the same bounds (they can be between 0 and 0.5). Thank you for your help. I think I will investigate gradient-free methods. I tried a basin hopping algorithm in SciPy, which seems to jump around the parameter space and then try to find the local minimum using gradient descent, which worked reasonably well as far as I can tell but didn't have an option to look for "shallow" minima. – Sean Nov 09 '18 at 09:03
0

You can try Backtracking Gradient descent (as well as backtracking versions of Momentum and NAG). More details can be found in my answer in this link (and you can look at the cited paper and link to GitHub, for source code, for more detail):

Stephen Rauch
  • 1,783
  • 11
  • 21
  • 34
Tuyen
  • 131
  • 1
  • 4