Return to Question

• But in general, is relatively straightforward to establish that "all functions defined over Non-Convex sets are by definition non-differentiable"?

• Could we technically still use "Gradient Descent" on problems like Travelling Salesman and Decision Trees (e.g. "Relax" the problem, use Gradient Descent, check to see if the solution falls within the feasible region, Explore for solution in neighborhood, Repeat, etc.), with the only problem being that it would be an extremely inefficient compared to Gradient-Free Optimization Methods (e.g. Metaheuristics/Evolutionary Algorithms, Branch and Bound)? Or is it by definition, we are mathematically unable to use Gradient Descent on problems like Travelling Salesman and Decision Trees?

Thanks!

Note: I have heard that Gradient Descent on Travelling Salesman is like "Nearest Neighbor Search", yet I do not fully understand why this is. I am guessing that maybe you can use Gradient Descent on Travelling Salesman - but it would be extremely ineffective as it would provide no "useful" information on which path to explore next?

• But in general, is relatively straightforward to establish that "all functions defined over Non-Convex sets are by definition non-differentiable"?

• Could we technically still use "Gradient Descent" on problems like Traveling Salesman and Decision Trees (e.g. "Relax" the problem, use Gradient Descent, check to see if the solution falls within the feasible region, Explore for solution in neighborhood, Repeat, etc.), with the only problem being that it would be an extremely inefficient compared to Gradient-Free Optimization Methods (e.g. Metaheuristics/Evolutionary Algorithms, Branch and Bound)? Or is it by definition, we are mathematically unable to use Gradient Descent on problems like Traveling Salesman and Decision Trees?

Note: I have heard that Gradient Descent on Traveling Salesman is like "Nearest Neighbor Search", yet I do not fully understand why this is. I am guessing that maybe you can use Gradient Descent on Traveling Salesman - but it would be extremely ineffective as it would provide no "useful" information on which path to explore next?

Is this function $\sum_i \sum_j c_{ij}x_{ij}$ differentiable? Can we take its derivative?

The above equation is the general function for "Information Gain" - is the function differentiable?

Is this function $\sum_i \sum_j c_{ij}x_{ij}$ differentiable with respect to its constraints? Can we take its derivative with respects to its constraints?

The above equation is the general function for "Information Gain" - is the function differentiable with respect to its constraints (I am guessing that the "constraints" in this case refer to Decision Trees being unable to make "illogical splits" that contradict "previous splits" - or instances in which the user specifies a minimum number of observations to be contained within each split)?

Thanks!

Note: I have heard that Gradient Descent on Travelling Salesman is like "Nearest Neighbor Search", yet I do not fully understand why this is. I am guessing that maybe you can use Gradient Descent on Travelling Salesman - but it would be extremely ineffective as it would provide no "useful" information on which path to explore next?