Recently, I found out why (most) Integer Programming and Mixed Integer Programming optimization problems are usually considered as Non-Convex. This is because even though the objective function in such problems (e.g. Traveling Salesman Problem is a Convex Function - since the set of constraints that this objective function has to be optimized over is Non-Convex (e.g. the set of Integers by definition is a Non-Convex set), the entire problem becomes a Non-Convex problem.
This being said, I have the following question:
1) In the case of the Traveling Salesman Problem, if we look at the "objective function" in this problem:
Is this function $\sum_i \sum_j c_{ij}x_{ij}$ differentiable? Can we take its derivative?
My inclination is "no" - this function is non-differentiable, seeing how I have never seen the Traveling Salesman Problem being solved using an optimization algorithm that requires evaluating a derivative (e.g. gradient descent), and instead always solved using optimization algorithms that do not require evaluating the derivative (e.g. Branch and Bound, Evolutionary and Metaheuristic Algorithms).
2) Consider the "Decision Tree" statistical/machine learning model (e.g. CART https://en.wikipedia.org/wiki/Decision_tree_learning) that is often used for supervised classification and regression tasks.
Given a dataset, a Decision Tree (e.g. CART) is formed by "splitting" variables into smaller subsets (i.e. "nodes") such that "purity" increases in each subsequent subset; "purity" is often measured through some sort of "Information Gain" that is based on measures such as "Gini Index" or "Entropy". Thus, Decision Trees can be interpreted as an optimization problem where "Information Gain" has to be optimized. I have heard that since Decision Trees often have different variable types (e.g. continuous and categorial), searching for the optimal variable splits that optimize "Information Gain" is a Mixed Integer Optimization Problem having an enormous Combinatorial Search Space. For the interest of creating a decent Decision Tree in a reasonable amount of time, "Information Gain" is optimized using a "Greedy Search Algorithm," and as a result, the final Decision Tree (i.e. the answer to this Mixed Integer Optimization Problem) is almost certainly unlikely to be the optimal Decision Tree (as there is very high probability that a better Decision Tree likely exists in this large Discrete Combinatorial Search Space, but finding this Decision Tree would take too much time):
The above equation is the general function for "Information Gain" - is the function differentiable?
Again, my inclination is "no" - this function is not differentiable, because I have never seen any references that show this optimization problem being solved using an optimization algorithm that requires evaluating the derivative (e.g. Gradient Descent), and significant research is being done on improving optimization algorithms for this problem, and these optimization algorithms do not involve derivatives (e.g. Branch and Bound https://arxiv.org/pdf/1904.12847.pdf , Evolutionary Algorithms https://cran.r-project.org/web/packages/evtree/vignettes/evtree.pdf)
Thus, my rationale as to why these above functions are non differentiable are unfortunately non-mathematical reasons, but rather anecdotal reasons.
But in general, is relatively straightforward to establish that "all functions defined over Non-Convex sets are by definition non-differentiable"?
