Question

Partial derivative of an algorithm?

Answer 1

Are x and y defined on an open space (a circle for example) or over a graph? Dijkstra is an algorithm for finding a shortest path over a discrete graph and can’t have partial derivatives. You may need to redefine your model or find another optimization algorithm.

Answer 2

Interesting problem. Not sure but I believe you can formulate the optimization problem as a minimum cost flow problem and use network simplex algorithm to solve it. And then use sensitivity analysis to determine how the changes in some input variables, constraints and right hand side affects the output from the optimal simplex network.

Answer 3

This sounds really interesting. Could you give more information on the problem and what it is you're trying to optimize? You have as an input a bunch of x, y coordinates, presumably representing something. What do they represent? And what are trying to optimize?

The shortest path algorithm really just gives you one answer. So I'm not sure that differentiation really makes sense in that context, if I understand your goals correctly. Again, I'm guessing at what you're doing, but it sounds like you would want to calculate the shortest path for a variety of points around the current point. That might be chaotic depending on the constraints though.

Answer 4

I don't think the shortest path function is nicely differentiable. Consider two points (origin and destination) with the same x-coordinate in the x,y-plane. Now suppose there is a horizontal wall obstructing the straight path from one point to the other. If you move the origin to the left, the shortest path goes around the obstruction's left side. If you love it to the right, the shortest path goes around the obstruction's right side. At some point in the middle, the shortest path function jumps from one path to the other, in a non-continous manner, which suggests that the function is not differentiable at this point. In fact, there must be a curve (not just a point) along which the shortest path function is not differentiable.

I don't know the specifics of your problem, and I think the non-differentiability may be worked around with some effort, but perhaps there's a simpler approach? A* has long been used to solve pathing problems in videogames. It may be worth checking out.

Answer 5

You don't really need to "differentiate Dijkstra's algorithm" if you can just figure out what the derivative of the shortest-path function is and then tweak the algorithm to compute that. If you think about what happens if you change the weight of an edge by some small ε, it's not too hard to convince yourself that the partial derivative of the shortest-path length with respect to the weight of some edge e is simply 1 if e appears on every shortest path, 0 if it appears on none of them, and undefined if it appears on some but not all. So if you implement a version of Dijkstra that keeps track of which edges appear on the paths it's trivial to get the derivatives out.

Answer 6

I mean for doing something similar to gradient desent with something that has a poorly defined curve or gradient like this you could do ~~back tracking~~ backpropagation instead.

Answer 7

Try control theory, pontragyin maximum principle, HJB equations

Answer 8

I would not expect gradient descent to work well for a problem like this. I would try simulated annealing.

Answer 9

Hey I didn’t read all the answers and don’t know if this was already suggested but a much simpler derivative free solution would be to use a bayesian optimizer. It is easy to parallelize, its a common tool in literature, familiar to most supervisors and in most languages there is a good implementation already existent. Also you can choose yourself how long to run the optimizer and thus how sure you want to be that you have a good solution. Hope this helped!

Answer 10

To clarify some other information here (much of which is good info) you don't want the derivative of an algorithm. You want the ability to evaluate the derivative of your algorithm. There is a crucial difference and what you want is much easier to obtain. Depending on the calls in your function evaluation you either want to use automatic differentiation (this is the ideal case) or numerical differentiation (if the former isn't applicable).

The main point I want to make contrary to some other people's answers is that no matter what you should not be implementing anything yourself. Find the library which has this functionality and then use it. There are tons of pitfalls which people have already figured out and overcome. One of them was already mentioned (small steps in finite differencing) but there are tons of others. Please just use an existing library once you determine what best suites your needs.