I have the following question about why Combinatorial and Discrete Optimization Problems are Considered to be "Difficult":
- For continuous optimization problems (e.g. Loss Functions in Machine Learning Models) - we are often told that these problems are difficult because when the objective functions are non-convex, the function can have "saddle points" which can "trap" the optimization algorithm before it reaches its intended destination:
- Recently, I have learned that the objective functions in discrete combinatorial optimization problems (e.g. Traveling Salesman) can also be non-convex. This is because even though the objective function corresponding to Traveling Salesman is linear and therefore convex, when integer constraints are applied to the objective function, the feasible region and the optimization problem ends up becoming non-convex (this is because the set of integers and therefore integer constraints automatically turn a problem into a non-convex problem):
Intuitively, in the case of continuous optimization problems with non-convex functions, we can understand why these functions might be difficult to optimize. We can imagine the optimization algorithm getting stuck in the saddle points.
Mathematically, we can also understand why continuous non-convex functions and saddle points can pose an obstacle - In a saddle point, the first derivatives of the function are 0. Since optimization algorithms that are commonly used for optimizing continuous functions (e.g. gradient descent) iteratively move towards their future destination (k+1) based on the current value (k) of the gradient (i.e. derivative), if they are in a saddle point and the derivative at a saddle point is zero - the optimization algorithm will become perpetually stuck in the saddle point and can't move forward (without some "intervention", e.g. stochastic momentum):
- The same way, is there any visual or mathematical or visual intuition that we can use to understand why Combinatorial and Discrete Optimization Problems are difficult? For instance, what would be the equivalent of "saddle point" obstacles in discrete and combinatorial optimization problems?