Timeline for Is the Travelling Salesman Problem Considered as "Gradient Free Optimization"?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 24, 2022 at 6:32 | comment | added | stats_noob | Let us continue this discussion in chat. | |
| Jan 23, 2022 at 20:09 | comment | added | prubin♦ | I'm moving this to a chat session. You should get the invitation from Stack Exchange. | |
| Jan 23, 2022 at 19:45 | comment | added | stats_noob | @ prubin: thank you for your reply! sorry to ask so many questions - if you have time, could you please help me understand this? In the case of the Travelling Salesman Problem - how could we take the "gradient of the objection function"? This seems impossible, no? Could you please expand on this? I can not thank you enough for your help! Thanks! | |
| Jan 23, 2022 at 19:42 | comment | added | prubin♦ | 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. | |
| Jan 23, 2022 at 17:12 | comment | added | stats_noob | 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? | |
| Jan 23, 2022 at 17:10 | vote | accept | stats_noob | ||
| Jan 23, 2022 at 17:00 | comment | added | prubin♦ | 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. | |
| Jan 23, 2022 at 16:32 | comment | added | stats_noob | I would have thought that for all discrete combinatorial optimization problems, the objective function will not have a gradient? | |
| Jan 23, 2022 at 16:25 | comment | added | stats_noob | thank you for your answer! Just to clarify: the objective function for tsp has no gradient? Thank you so much! | |
| Jan 23, 2022 at 16:20 | history | answered | prubin♦ | CC BY-SA 4.0 |