Minimización de f (x, y) donde xey son números enteros

Question

Me preguntaba si alguien tenía alguna sugerencia para minimizar una función, f (x, y), donde xey son enteros. Investigué muchas técnicas de minimización y optimización, como BFGS y otras de GSL, y cosas de Recetas Numéricas. Hasta ahora, he intentado implementar un par de esquemas diferentes. La primera funciona al elegir la dirección de mayor descenso f (x + 1, y), f (x-1, y), f (x, y + 1), f (x, y-1), y seguir esa dirección con minimización de línea. También he intentado usar un método simplex (Nelder-Mead). Ambos métodos se quedan muy lejos de un mínimo. Ambos parecen trabajar en funciones más simples, como encontrar el mínimo de un paraboloide, pero creo que ambos, y especialmente el primero, están diseñados para funciones donde xey son valores reales (dobles). Un problema más es que necesito llamar a f (x, y) tan pocas veces como sea posible. Habla con hardware externo y toma un par de segundos para cada llamada. Cualquier idea para esto sería muy apreciada.

Aquí hay un ejemplo de la función de error. Lo siento, no publiqué esto antes. Esta función toma un par de segundos para evaluar. Además, la información que consulta desde el dispositivo no añade al error si está por debajo de nuestro valor deseado, sólo si está por encima de

double Error(x,y) 
{ 
    SetDeviceParams(x,y); 
    double a = QueryParamA(); 
    double b = QueryParamB(); 
    double c = QueryParamC(); 
    double _fReturnable = 0; 
    if(a>=A_desired) 
    { 
    _fReturnable+=(A_desired-a)*(A_desired-a); 
    } 
    if(b>=B_desired) 
    { 
    _fReturnable+=(B_desired-b)*(B_desired-b); 
    } 
    if(c>=C_desired) 
    { 
    _fReturnable+=(C_desired-c)*(C_desired-c); 
    } 
    return Math.sqrt(_fReturnable) 
} 

Answer 1

¿Cómo se define f (x, y)? La minimización es un problema difícil, según la complejidad de su función.

Algoritmos genéticos podrían ser un buen candidato.

Recursos:

Genetic Algorithms in Search, Optimization, and Machine Learning

Implementing a Genetic Algorithms in C#

Simple C# GA

Answer 2

¿Has mirado en algoritmos genéticos? Son muy, muy buenos para encontrar mínimos y máximos, al tiempo que evitan los mínimos/máximos locales.

Answer 3

Si se trata de una función arbitraria, no hay una forma clara de hacerlo.

Supongamos que tenemos una función definida como:

f(x, y) = 0 for x==100, y==100 
      100 otherwise 

¿Cómo podría encontrar cualquier algoritmo realista (100, 100) como el mínimo? Podría ser cualquier combinación posible de valores.

¿Conoces cualquier cosa acerca de la función que estás probando?

Answer 4

Hay muchas, muchas soluciones aquí. De hecho, hay libros enteros y disciplinas académicas basadas en el tema. Estoy leyendo una excelente en este momento: How to Solve It: Modern Heuristics.

No existe una solución única que sea correcta: las diferentes soluciones tienen diferentes ventajas basadas en el conocimiento específico de su función. Incluso se ha demostrado que no existe una única heurística que realice las mejores tareas de optimización.

Si sabe que su función es cuadrática, puede usar Newton-Gauss para encontrar el mínimo en un solo paso. Un algoritmo genético puede ser una gran herramienta de propósito general, o puede probar el recocido simulado, que es menos complicado.

Answer 5

Lo que generalmente está buscando se llama optimisation technique en matemáticas.En general, se aplican a funciones con valores reales, pero muchas se pueden adaptar para funciones con valores integrales.

En particular, recomendaría buscar en non-linear programming y gradient descent. Ambos parecen bastante adecuados para su aplicación.

Si pudiera proporcionar más detalles, podría sugerir algo un poco más específico.

Answer 6

La respuesta de Jon Skeet es correcta. Realmente necesita información sobre fy sus derivados, incluso si f está en todas partes continuo.

La manera más fácil de apreciar las dificultades de lo que pregunta (minimización de f en valores enteros solamente) es solo pensar en f: R-> R (f es una función real valorada de los reales) de una variable eso hace grandes excursiones entre enteros individuales. Puede construir fácilmente tal función para que NO haya correlación entre los mínimos locales en la línea real y los mínimos en los enteros, así como tampoco tener relación con la primera derivada.

Para una función arbitraria, no veo otra salida que la fuerza bruta.

Answer 7

Lo siento, el formato era tan malo anteriormente. Aquí hay un ejemplo de la función de error

double Error(x,y) 
{ 
SetDeviceParams(x,y); 
double a = QueryParamA(); 
double b = QueryParamB(); 
double c = QueryParamC(); 
double _fReturnable = 0; 
if(a>=A_desired) 
{ 
    _fReturnable+=(A_desired-a)*(A_desired-a); 
} 
if(b>=B_desired) 
{ 
_fReturnable+=(B_desired-b)*(B_desired-b); 
} 
if(c>=C_desired) 
{ 
    _fReturnable+=(C_desired-c)*(C_desired-c); 
} 
return Math.sqrt(_fReturnable) 
} 

Answer 8

Así que veamos su problema en el lenguaje matemático. Todo esto es asumiendo que entiendo completamente el problema . No dudes en corregirme si me equivoco.

queremos minimizar el siguiente:

\ sqrt ((a-a_desired)^2 + (b-b_desired)^2 + (c-c_desired)^2)

o en otra notación || Pos (x - x_desired) || _2

donde x = (a, b, c) y Pos (y) = max (y, 0) significa que queremos la "parte positiva" (esto explica para sus declaraciones if). Finalmente, deseamos restringirnos a soluciones donde x es un valor entero.

A diferencia de los carteles anteriores, no creo que los algoritmos genéticos sean lo que usted desea en absoluto.
De hecho, creo que la solución es mucho más fácil (suponiendo que entiendo su problema).

1) Ejecute cualquier rutina de optimización en la función anterior. Esto le dará la solución x^* = (a^*, b^*, c^*). Como esta función aumenta con respecto a las variables, la mejor solución de enteros que puede esperar es (ceil (a^*), ceil (b^*), ceil (c^*)).

Ahora dice que su función es posiblemente difícil de evaluar. Existen herramientas para esto que no se basan en heurística. Vaya bajo el nombre Derivative-Free Optimización. La gente utiliza estas herramientas para optimizar el objetivo basado en simulaciones (He oído hablar de un caso en el que la función objetivo se basa en los rendimientos cacareando cosecha!)

Cada uno de estos métodos tienen diferentes propiedades, pero en general su intento de minimizar no solo el objetivo, sino el número de evaluaciones de funciones objetivas.