¿Se pueden utilizar las técnicas de optimización basadas en gradientes para resolver el problema del vendedor ambulante?

¿Se pueden utilizar técnicas de optimización basadas en gradientes para resolver el problema del vendedor ambulante?

El problema del vendedor ambulante es un famoso problema de optimización en el que un vendedor tiene que averiguar en qué orden viajar a través de "n" ciudades, de modo que la distancia total recorrida sea mínima y cada ciudad se visite una vez.

La "función objetivo" en este problema es una función que asigna "diferentes órdenes de ciudades" a la "distancia total correspondiente a ese orden de ciudades". Como ejemplo, la función objetivo podría verse así:

ingrese la descripción de la imagen aquí

Mi pregunta: En el caso del problema del viajante de comercio, ¿es la función objetiva "diferenciable" en el mismo sentido que la ecuación de una parábola (y = x^2) es diferenciable?

A primera vista, la respuesta obviamente parece ser "no". Después de todo, ¿cómo podemos tomar la derivada de la función anterior? ¡La función anterior no está definida sobre un dominio continuo!

Entonces, ¿podemos decir que en el caso del problema del viajante de comercio (es decir, problemas de optimización combinatoria discreta), las funciones objetivo son "no diferenciables"? Si esto es cierto, ¿es entonces "imposible usar la optimización basada en gradientes en el vendedor ambulante"?

¿O incluso en tales casos, se puede decir que las funciones objetivas son diferenciables?

¿Puede alguien comentar sobre esto?

¡Gracias!

Es posible que desee consultar los "Algoritmos para la optimización convexa" de Vishnoi. Cubre algoritmos de optimización continua para problemas discretos/combinatorios.
@VSeH: ¡muchas gracias por tu respuesta! Tengo dificultades para comprender el siguiente punto: si la función objetivo es discreta y no está definida en un dominio continuo, ¿la función objetivo se llama "no diferenciable"? ¿Podemos usar técnicas de optimización basadas en gradientes en "funciones objetivas no diferenciables"?
Generalmente, un gradiente simple no será suficiente para resolver un problema discreto (pero puede, en algunos casos particulares, ver la unimodularidad total). Lo que se hace a menudo es relajar las variables en la formulación a valores reales, luego resolver la formulación relajada (en el caso de la programación lineal, esto se puede hacer de manera eficiente a través del algoritmo simplex, este es un algoritmo basado en gradientes), luego usar una rama & algoritmo enlazado para fijar las variables a números enteros. Esto generalmente da un algoritmo exponencial, pero puede proporcionar muy buenos límites duales y, en la práctica, puede funcionar muy bien.
Por favor, no grites tanto.
Ser no derivable significa que la derivada no existe en el dominio del objetivo, lo que no tiene por qué ser el caso de los problemas discretos, pero sucede con bastante frecuencia. Vishnoi lo explica con bastante claridad en su libro y señala algunos desarrollos nuevos con respecto al TSP utilizando la optimización convexa. El problema de flujo máximo es una instancia de un problema combinatorio resuelto con métodos de gradiente y, de hecho, de manera más eficiente.

Respuestas (2)

Ciertamente no.

La función objetivo del TSP no es más que un campo de mínimos locales en el que quedaría atrapado cualquier método continuo (digamos obtenido por interpolación). Y sería una tontería probar coordenadas intermedias cuando sabes que la solución ocurre en los puntos de datos dados.

TSP es un problema combinatorio, punto final.

Para una analogía, considere la minimización de

pecado ⁡ X + ( X 1000 − 1 ) 2

ingrese la descripción de la imagen aquí

Un caso particular de optimización continua es la programación lineal (LP), donde tenemos una función objetivo lineal y un conjunto de restricciones lineales sobre las variables (restringidas a ser reales). Los LP son convexos y se pueden resolver de manera eficiente a través de algoritmos basados ​​en gradientes, como el algoritmo simplex.
Un problema relacionado es la programación lineal de enteros mixtos (MILP), donde también tenemos una función objetivo lineal y un conjunto de restricciones lineales, pero esta vez, las variables se pueden restringir para que sean enteras. Esto ofrece mucha más expresividad, y podemos mostrar fácilmente que cada norte PAG -El problema se puede expresar como un problema MILP (polinomialmente pequeño). Sin embargo, ya no se garantiza que los métodos de gradiente converjan a la optimización ya que el problema ahora es discreto. Pero si relajamos las restricciones de integralidad de las variables, el óptimo a menudo da un fuerte límite dual a nuestro problema. Combinado con la búsqueda en árbol (a través de una rama y un límite), esto puede acelerar drásticamente la resolución (aunque la complejidad sigue siendo exponencial).

Todavía es posible expresar problemas combinatorios con funciones convexas. Usando un conjunto exponencial de restricciones, podemos expresar el problema del viajante de comercio como un problema lineal. Esto se puede lograr expresando el problema como una instancia de SAT. El conjunto de puntos formado por los vectores binarios correspondientes siempre será convexo, por lo que podemos tomar como restricciones todas las facetas de la envolvente convexa. Desafortunadamente, se sabe que siempre terminaremos con un número exponencial de facetas, sin importar cómo modelemos el problema del viajante de comercio. De hecho, todavía no conocemos ningún algoritmo de tiempo polinomial para norte PAG -problemas duros.

El algoritmo simplex no está basado en gradientes, es combinatorio. Los métodos de puntos interiores se basan en gradientes (y, de hecho, en segundo orden). Además, que un problema no sea convexo no significa necesariamente que los métodos basados ​​en gradientes no funcionen. Prácticamente todo el entrenamiento de NN no es convexo y se realiza con SGD.
Wikipedia define un método de gradiente como un algoritmo donde las direcciones de búsqueda están definidas por el gradiente de la función en el punto actual. En el algoritmo simplex, el siguiente pivote se decide analizando el gradiente. Pero estoy de acuerdo en que los métodos de puntos interiores son más como gradientes. En general, para una función no convexa, el gradiente solo se garantiza para encontrar un óptimo local, por lo que no "resuelve" el problema estrictamente hablando.
No sé de dónde obtiene su información sobre los LP, pero el método simplex no elige un pivote al analizar el gradiente (y para ser pedante, no se menciona "gradiente" en el artículo wiki sobre LP). Sin embargo, indique la referencia adecuada en caso contrario. No poder "resolver" el problema, como encontrar el optimizador global, no es lo mismo que "los métodos de gradiente ya no funcionarán", como se indica en su respuesta.
Los pivotes se eligen a lo largo de las variables para las cuales la derivada del objetivo con respecto a esa variable es negativa (y a menudo se elige como la más inclinada). El simplex es bastante similar a un descenso de gradiente, excepto que está restringido a moverse en los bordes en lugar de en cualquier parte del politopo. Editaré el "ya no funciona" con algo más preciso.
De hecho, este no es un problema de convexidad, sino más bien que el problema ya no es continuo.
Estoy de acuerdo, y tienes toda la razón, pero todavía no usaría el algoritmo simplex como un ejemplo de "basado en gradiente", porque el gradiente no define la dirección de búsqueda, según la definición de wiki, sino que "guía" el buscar. Además, el método símplex es exacto y combinatorio, a diferencia de, por ejemplo, el descenso de gradiente. Pero yo divago.
¿Se pueden utilizar las técnicas de optimización basadas en gradientes para resolver el problema del vendedor ambulante?
RespuestasAquíPolítica de privacidad1y, 0v