En un problema de optimización no convexo, ¿es posible determinar si dos puntos pertenecen al mismo valle o no?

Esto se puede responder fácilmente empíricamente a través del corte. Suponga que los dos puntos son [matemática] x_1 [/ matemática] y [matemática] x_2 [/ matemática]. Entonces, cualquier punto [matemático] x [/ matemático] intermedio es [matemático] c * x_1 + (1-c) * x_2 [/ matemático] donde [matemático] c [/ matemático] varía de 0 a 1. Luego, trace el valores de función en los puntos [matemática] x [/ matemática] muestra aleatoria y uniforme o lineal entre los puntos. A continuación se muestra una implementación rápida y sucia de Python que ilustra el corte en una función cuadrática general:

Descargo de responsabilidad: escribir en el teléfono para que este fragmento de código no se pruebe.

importar numpy como np
importar matplotlib.pyplot como plt

def f (x, A = np.eye (2), b = np.zeros (2), c = 0):
# función cuadrática general
return (xb) .dot (A) .dot (xb) + c

x_1 = np.array ([0, 0])
x_2 = np.array ([5, 10])
N = 100
C = np.linspace (0, 1, N) # muestreo regular
x = [c * x_1 + (1 – c) * x_2 para c en C]
y = mapa (f, x) #

plt.plot (C, y, ‘.’)
plt.show ()

Si el corte se ve convexo, entonces los dos puntos son probablemente “co-vallados”. Aumente N para mejorar su confianza.

La forma útil debe evitar pequeños mínimos locales durante el descenso del gradiente mencionado por Ben Packer, donde el recocido simulado con los puntos respectivos como puntos de partida puede evitar este problema.

De lo contrario, la técnica de corte según lo mencionado por Alfredo Kalaitzis es la mejor en cuanto a costo computacional.

La optimización del enjambre de partículas de dos partículas puede proporcionar las mejores iniciativas.

Puede aplicar el descenso de gradiente (con un tamaño de paso relativamente pequeño para evitar saltar entre valles) inicializado en ambos puntos y ver si termina en el mismo mínimo local, suponiendo que esto es lo que quiere decir con “pertenecer al mismo valle”. debería funcionar a menos que tenga problemas numéricos o superficies muy planas que eviten que el descenso del gradiente converja correctamente.