Solamente en el caso discreto si la cardinalidad de es pequeña tal que la enumeración (o programación dinámica) es posible, o en el caso continuo si f() tiene propiedades muy particulares (e.g. convexa) y tal que se puede aplicar por ejemplo gradient-search, se puede encontrar un óptimo global relativamente facil.
Sin embargo, en la mayoría de los casos se debe recurrir a métodos iterativos estocásticos que producen una secuencia Xn de aproximaciones sucesivas que convergen (con una cierta probabilidad) en un óptimo global.
Típicamente, las aproximaciones consecutivas difieren poco. Por ejemplo para el problema del Agente Viajero, podrían diferir solamente por el intercambio de dos ciudades (arbitrarias).
Los ejemplos más sencillos son algoritmos multistart: para un grupo grande de estados iniciales tomados de una distribución particular se aplica un algoritmo de búsqueda local (para una estructura de vecindad dada) y se guarda el mejor óptimo local. Estos algoritmos forman la base de diversos métodos de clustering dónde la selección es en función de la calidad y la ubicación en el espacio de búsqueda.
En lo que sigue se presentan dos métodos relativamente recientes. En ambos casos, el componente probabilístico van a servir para explorar el espacio de búsqueda de una manera arbitraria, contrario al componente determinístico que será basado en, por ejemplo, información analítica. Nos restringimos al caso de finito.