1
$\begingroup$

Recently, I found out why (most) Integer Programming and Mixed Integer Programming optimization problems are usually considered as Non-Convex (Why is the Set of Integers Non-Convex?). This is because even though the objective function in such problems (e.g. Travelling Salesman Problem https://en.wikipedia.org/wiki/Travelling_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 Travelling Salesman Problem, if we look at the "objective function" in this problem:

enter image description here

Is this function sum(sum(c_ij*x_ij)) differentiable when subject to its constraints? Can we take its derivative?

My inclination is "no" - this function is non-differentiable, seeing how I have never seen the Travelling 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):

enter image description here

The above equation is the general function for "Information Gain" , again I ask - when subject to its constraints, is the above 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 - and this of course is not an acceptable way to present arguments in math.

But in general, is it relatively straightforward to establish that:

  • Are 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!

References:

$\endgroup$

1 Answer 1

2
$\begingroup$

First of all, it is not because you have not seen any references that show this optimization problem being solved using an optimization algorithm that requires evaluating the derivative, that the function is nondifferentiable.

It is important to define the domain of the function. If you view the function as a function of real variables on $\mathbb{R}^{n^2}$, yes it is differentiable. If the domain is $\{0,1\}^{n^2}$, it is also trivially differentiable but with the discrete definition for the derivative.

It has nothing to do with the fact that the set is nonconvex. It has to do with the fact that the set is discrete (or continuous). The reason why there is no derivative involved in the traveling salesman problem is that it is not necessary to use it to solve it. Same comment for the decision tree.

$\endgroup$
3
  • $\begingroup$ @ KBS: thank you for your reply! I agree - "First of all, it is not because you have not seen any references that show this optimization problem being solved using an optimization algorithm that requires evaluating the derivative, that the function is nondifferentiable." - this is exactly the reason why I asked my question! $\endgroup$ Feb 28, 2022 at 1:43
  • 1
    $\begingroup$ You cannot infer that a mathematical object does not have a certain property from the absence of resources using it. $\endgroup$
    – KBS
    Feb 28, 2022 at 1:46
  • $\begingroup$ Yes, I agree with you! $\endgroup$ Feb 28, 2022 at 1:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .