5
$\begingroup$

I was thinking about the Traveling Salesman Problem the other day - for such types of discrete combinatorial optimization problems, do they have a "loss function"?

It seems that there is some "vague" function which takes inputs as different combinations of cities, and returns the total distance traveled if these cities are visited in that order.

Would this be (along with problems such as "scheduling") considered as "gradient free optimization"?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

In no particular order ...

  • I wouldn't call the objective function of the TSP "vague". It is quite explicit.
  • The term "gradient-free" applies to algorithms, not to problems. You might find yourself choosing between gradient-based and "gradient-free" algorithms for the same problem. The confusion may arise from the fact that you have to use a "gradient-free" algorithm when the problem's objective function does not have a gradient.
  • The simplex method is gradient-based, so any TSP algorithm that involves solving an LP will not be "gradient-free".
  • The Nelder-Mead algorithm for nonlinear optimization (confusingly known as the "simplex algorithm", but not that "simplex algorithm") is an example of a gradient-free algorithm.
Improve this answer
$\endgroup$
8
  • $\begingroup$ thank you for your answer! Just to clarify: the objective function for tsp has no gradient? Thank you so much! $\endgroup$
    – stats_noob
    Commented Jan 23, 2022 at 16:25
  • $\begingroup$ I would have thought that for all discrete combinatorial optimization problems, the objective function will not have a gradient? $\endgroup$
    – stats_noob
    Commented Jan 23, 2022 at 16:32
  • $\begingroup$ The TSP objective function depends on how you define your variables. Most commonly, you will use binary variables $x_{ij}$, taking value 1 if $i\rightarrow j$ is part of the tour. The objective function is linear in the $x_{ij}$ variables, and linear functions have (constant) gradients. $\endgroup$
    – prubin ♦
    Commented Jan 23, 2022 at 17:00
  • $\begingroup$ Thank you for your reply! "Most commonly, you will use binary variables xij" - in this case, the objective function will not have a gradient, correct? $\endgroup$
    – stats_noob
    Commented Jan 23, 2022 at 17:12
  • 3
    $\begingroup$ No, the objective function will have a gradient. The issue with discrete variables is not whether the objective function has a gradient but to what extent that gradient is meaningful/useful, since "small" changes to the variables do not make sense. $\endgroup$
    – prubin ♦
    Commented Jan 23, 2022 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.