1
$\begingroup$

I am working with an objective function that is convex globally, but the path downward is lined (if you will) with quartz crystals. In this case, the update vector (gradient solution) of partial derivatives of a potential crystal's surface you land on sometimes points upward, so the algorithm throws you backward. Hence, it's a quite bumpy objective function.

I have thought of an approach similar to genetic algorithms, where I could add a small random value in the range [-0.5,0.5] to each gradient update, and have also thought about using orthogonal vectors for which the question becomes: which dimension and therefore which orthogonal vector?

Overall, a line search assumes a monotonically decreasing function that's continuously differentiable in the limit. Aside from using GA's is there a more recent approach for a bumpy landscape when derivatives are known?

Improve this question
$\endgroup$
2
  • $\begingroup$ You could average out the gradient a few times (each node is an average of it's value and it's neighboring values). This can be equivalently seen as a very big object that covers multiple cells as it runs across your grid, so it has to average all their values. In this way it will "roll over" gaps and such. $\endgroup$
    – Phylliida
    Commented May 4, 2015 at 1:25
  • $\begingroup$ will give it a try - thx. $\endgroup$
    – user15259
    Commented May 5, 2015 at 1:48

1 Answer 1

Reset to default
2
$\begingroup$

A common approach to dealing with noisy objective functions is to use regression techniques to build a smooth and convex surrogate "response surface" that approximates the function and then minimize over the response surface.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sounds like a good idea. Interestingly, the problem is actually a large non-linear regression problem with linear and exponential terms combined. Maybe what could be done is: set the fitness value as the predictor and the gradient vector elements for multiple iterations as the dependent variables, and then use multivariate normal regression with multiple $y$ values regressed on fitness. Whenever fitness decreases (not a descent step), make a prediction of the next lowest gradient values assuming fitness increased by a given increment. Even though this is a linear approach, it may work. $\endgroup$
    – user15259
    Commented May 5, 2015 at 1:46

Your Answer

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