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?