Algoritmo para calcula el mínimo de una función convexa

Dada una función convexa de una variable y=f(x) queremos calcular el mínimo de la función en un intervalo continuo mediante un algoritmo en Python que hemos denominado algoritmo de las secantes descendentes.

La función elegida para el ejemplo es y=(x-4)^2+10 que tiene un mínimo en x=4. Veamos su gráfica.

• https://repl.it/@valoro/minimiza

#algoritmo de las secantes descendentes
#busca el mínimo de una función convexa de una variable
#dada la función y=(x-4)^2+10
#tenemos que calcular el mínimo, que está en x=4

def f(x):
  return (x-4)**2+10 #definimos la función

l=-1.0 #valor izquierdo
r=18.0 #valor derecho
e=10**-12 #error admitido, tolerancia
while True: #bucle infinito
  c=(r+l)/2 #punto central entre l y r
  if (abs(f(l)-f(c)) or abs(f(r)-f(c))) < e:
    #si la diferencia de alturas en valor absoluto por un
    #lado o por el otro es menor que la tolerancia
    break #salir del bucle si se cumeple la condición
  else: #si no se cumple la condición
    if f(l)<f(r): #si la altura por la izquierda es menor
      r=c
    else: #si la altura por la derecha es menor
      l=c

print(round(c,5)) #imprimimos el mínimo

La idea del algoritmo es la siguiente.

Se requiere que la función a calcular sea continua en el intervalo de cálculo, y que sea convexa en ese intervalo. Entonces tendrá un mínimo que podremos calcular.

Paso 1

Establecemos el punto inferior del intervalo, en nuestro ejemplo usamos la letra l, por ser la inicial de left y le damos el valor -1.
Establecemos el punto superior del intervalo, en nuestro ejemplo usamos la letra r, por se la inicial de right y le damos el valor 18.
Establecemos el error admisible (e) o tolerancia. En nuestro caso e=10^-12 que en Python podemos ee expresar como e=10**-12.

Paso 2

Nos metemos en un bucle infinito, de donde únicamente saldremos si encontramos una instrucción break.
Calculamos el valor central (c) o valor medio entre l y r. Siendo, c=(l+r)/2.

Paso 3

Imaginemos la recta que une los puntos (l, f(l)) y (r, f(r)). Se tratará de una recta que tiene una cierta inclinación. Puede tener pendiente positiva (recta creciente), pendiente negativa (recta decreciente), o pendiente cero (recta horizontal).

En nuestro ejemplo, los puntos son, por la izquierda (-1,f(-1)) y por la derecha (18, f(18)).
f(-1)=35
f(18)=206

Mostramos los cálculos del algoritmo realizados en una hoja de Excel.

https://1drv.ms/x/s!Au6UujMZy_j5nyRSOpb7e9enoNee

Calculamos el punto central c=(-1+18)/2=8,5 y el valor de la función en él f(8,5)=30,25.

Paso 4

Calculamos la diferencias de alturas por la izquierda f(l)-f(c)=35-30,25=4,75.
Calculamos la diferencias de alturas por la derecha f(r)-f(c)=206-30,25=175,75.

Ahora analizamos que diferencias de altura es mayor. Vemos que la diferencias de alturas de la derecha es mayor que la que existe por la izquierda.
Como 175,75>4,75 entonces convertimos la altura mayor en la central, para ello hacemos que r sea igual a c.

r antiguo = 18
c =8,5
r nuevo =8,5

Paso 5

Esto se repite hasta que consigamos que la diferencia de alturas sea menor que el error admitido.

Nota

Estudiar si f(l)-f(c) < f(r)-f(c) equivale a estudiar que f(l) < f(r). En Excel hemos usado la primera expresión en la celda C4, y en el código de Python hemos usado la segunda expresión puesto que son equivalentes.

Existen otros algoritmos más eficientes en cuanto que necesitan un número menor de iteraciones para llegar a calcular el mínimo. La ventaja de este algoritmo es que no se necesita calcular la derivada de la función.