Main Content

Seleccionar el algoritmo

Algoritmos fmincon

fmincon tiene cinco opciones de algoritmo:

  • 'interior-point' (valor predeterminado)

  • 'trust-region-reflective'

  • 'sqp'

  • 'sqp-legacy'

  • 'active-set'

Utilice optimoptions para establecer la opción Algorithm en la línea de comandos.

Recomendaciones
  • Utilice el algoritmo 'interior-point' en primer lugar.

    Para obtener ayuda si falla la minimización, consulte Cuando el solver falla o Cuando es posible que el solver haya tenido éxito.

  • Para ejecutar una optimización de nuevo para obtener más velocidad en problemas de tamaño pequeño o mediano, pruebe 'sqp' a continuación y 'active-set' en último lugar.

  • Utilice 'trust-region-reflective' cuando proceda. Se requiere que, en el problema, la función objetivo incluya gradiente y, o bien restricciones de límites, o bien restricciones de igualdad lineales (pero no ambas).

Consulte Posible imprecisión con algoritmos interior-point.

Razonamiento subyacente a las recomendaciones

  • 'interior-point' resuelve problemas dispersos grandes, así como problemas densos pequeños. El algoritmo satisface límites en todas las iteraciones y no se ve impedido por resultados NaN o Inf. Es un algoritmo a gran escala; consulte Algoritmos a gran escala frente a algoritmos a media escala. El algoritmo puede utilizar técnicas especiales para problemas a gran escala. Para obtener más detalles, consulte Algoritmo interior-point en fmincon options.

  • 'sqp' satisface límites en todas las iteraciones. El algoritmo no se ve impedido por resultados NaN o Inf. No es un algoritmo a gran escala; consulte Algoritmos a gran escala frente a algoritmos a media escala.

  • 'sqp-legacy' es similar a 'sqp', pero suele ser más lento y utiliza más memoria.

  • 'active-set' puede dar pasos grandes, lo que añade velocidad. El algoritmo es efectivo en algunos problemas con restricciones no suaves. No es un algoritmo a gran escala; consulte Algoritmos a gran escala frente a algoritmos a media escala.

  • 'trust-region-reflective' necesita que proporcione un gradiente y permite restricciones de límites o restricciones de igualdad lineales, pero no ambas. Dentro de estas limitaciones, el algoritmo resuelve con eficiencia tanto problemas dispersos grandes como problemas densos pequeños. Es un algoritmo a gran escala; consulte Algoritmos a gran escala frente a algoritmos a media escala. El algoritmo puede utilizar técnicas especiales para ahorrar uso de memoria, como una función de multiplicación de matriz hessiana. Para obtener más detalles, consulte Algoritmo trust-region-reflective en fmincon options.

Para ver descripciones de los algoritmos, consulte Algoritmos de optimización no lineal con restricciones.

Algoritmos de fsolve

fsolve tiene tres algoritmos:

  • 'trust-region-dogleg' (valor predeterminado)

  • 'trust-region'

  • 'levenberg-marquardt'

Utilice optimoptions para establecer la opción Algorithm en la línea de comandos.

Recomendaciones
  • Utilice el algoritmo 'trust-region-dogleg' en primer lugar.

    Para obtener ayuda si falla fsolve, consulte Cuando el solver falla o Cuando es posible que el solver haya tenido éxito.

  • Para resolver ecuaciones de nuevo si tiene una función de multiplicación de matriz jacobiana o si desea ajustar el algoritmo interno (consulte Algoritmo trust-region en fsolve options), pruebe 'trust-region'.

  • Pruebe a cronometrar todos los algoritmos, incluido 'levenberg-marquardt', para encontrar el algoritmo que mejor funciona con su problema.

Razonamiento subyacente a las recomendaciones

  • 'trust-region-dogleg' es el único algoritmo que está diseñado especialmente para resolver ecuaciones no lineales. Los otros intentan minimizar la suma de los cuadrados de la función.

  • El algoritmo 'trust-region' es efectivo en problemas dispersos. Puede utilizar técnicas especiales, como una función de multiplicación de matriz jacobiana para problemas a gran escala.

Para ver descripciones de los algoritmos, consulte Algoritmos de resolución de ecuaciones.

Algoritmos de fminunc

fminunc tiene dos algoritmos:

  • 'quasi-newton' (valor predeterminado)

  • 'trust-region'

Utilice optimoptions para establecer la opción Algorithm en la línea de comandos.

Recomendaciones
  • Si la función objetivo incluye un gradiente, utilice 'Algorithm' = 'trust-region' y establezca la opción SpecifyObjectiveGradient en true.

  • De lo contrario, utilice 'Algorithm' = 'quasi-newton'.

Para obtener ayuda si falla la minimización, consulte Cuando el solver falla o Cuando es posible que el solver haya tenido éxito.

Para ver descripciones de los algoritmos, consulte Algoritmos de optimización no lineal sin restricciones.

Algoritmos de mínimos cuadrados

lsqlin

lsqlin tiene tres algoritmos:

  • 'interior-point', la opción predeterminada

  • 'trust-region-reflective'

  • 'active-set'

Utilice optimoptions para establecer la opción Algorithm en la línea de comandos.

Recomendaciones
  • Pruebe 'interior-point' en primer lugar.

    Sugerencia

    Para lograr un mejor rendimiento cuando la matriz de entrada C tiene una proporción grande de entradas distintas de cero, especifique C como una matriz doble ordinaria. De forma similar, para lograr un mejor rendimiento cuando C tiene relativamente pocas entradas distintas de cero, especifique C como dispersa. Para obtener más detalles de los tipos de datos, consulte Matrices dispersas. También puede establecer el tipo de álgebra lineal interno utilizando la opción 'LinearSolver'.

  • Si no tiene restricciones o si solo tiene restricciones de límites y desea una mayor precisión, más velocidad o si desea utilizar una Jacobian Multiply Function with Linear Least Squares, pruebe 'trust-region-reflective'.

  • Si tiene un número elevado de restricciones lineales y un número no elevado de variables, pruebe 'active-set'.

Para obtener ayuda si falla la minimización, consulte Cuando el solver falla o Cuando es posible que el solver haya tenido éxito.

Consulte Posible imprecisión con algoritmos interior-point.

Para ver descripciones de los algoritmos, consulte Algoritmos de mínimos cuadrados (ajuste de modelos).

lsqcurvefit y lsqnonlin

lsqcurvefit y lsqnonlin tienen tres algoritmos:

  • 'trust-region-reflective' (valor predeterminado para problemas sin restricciones o con límites de restricción)

  • 'levenberg-marquardt'

  • 'interior-point' (valor predeterminado para problemas con restricciones lineales o no lineales)

Utilice optimoptions para establecer la opción Algorithm en la línea de comandos.

Recomendaciones
  • Para problemas con límites de restricción, pruebe primero con 'trust-region-reflective' o 'levenberg-marquardt'.

  • Si el problema con límites de restricción es subdeterminado (menos ecuaciones que dimensiones), pruebe primero 'levenberg-marquardt'.

  • Si su problema tiene restricciones lineales o no lineales, utilice 'interior-point'.

Para obtener ayuda si falla la minimización, consulte Cuando el solver falla o Cuando es posible que el solver haya tenido éxito.

Para ver descripciones de los algoritmos, consulte Algoritmos de mínimos cuadrados (ajuste de modelos).

Algoritmos de programación lineal

linprog tiene tres algoritmos:

  • 'dual-simplex', la opción predeterminada

  • 'interior-point-legacy'

  • 'interior-point'

Utilice optimoptions para establecer la opción Algorithm en la línea de comandos.

Recomendaciones

Utilice el algoritmo 'dual-simplex' o el algoritmo 'interior-point' en primer lugar.

Para obtener ayuda si falla la minimización, consulte Cuando el solver falla o Cuando es posible que el solver haya tenido éxito.

Consulte Posible imprecisión con algoritmos interior-point.

Razonamiento subyacente a las recomendaciones

  • A menudo, los algoritmos 'dual-simplex' e 'interior-point' son rápidos y son los que menos memoria utilizan.

  • El algoritmo 'interior-point-legacy' es similar al 'interior-point', pero 'interior-point-legacy' puede ser más lento, menos robusto o utilizar más memoria.

Para ver descripciones de los algoritmos, consulte Linear Programming Algorithms.

Algoritmos de programación cuadrática

quadprog tiene tres algoritmos:

  • 'interior-point-convex' (valor predeterminado)

  • 'trust-region-reflective'

  • 'active-set'

Utilice optimoptions para establecer la opción Algorithm en la línea de comandos.

Recomendaciones
  • Si tiene un problema convexo o si desconoce si el problema es convexo, utilice 'interior-point-convex'.

  • Sugerencia

    Para lograr un mejor rendimiento cuando la matriz hessiana H tiene una proporción grande de entradas distintas de cero, especifique H como una matriz doble ordinaria. De forma similar, para lograr un mejor rendimiento cuando H tiene relativamente pocas entradas distintas de cero, especifique H como dispersa. Para obtener más detalles de los tipos de datos, consulte Matrices dispersas. También puede establecer el tipo de álgebra lineal interno utilizando la opción 'LinearSolver'.

  • Si tiene un problema no convexo solo con límites o solo con igualdades lineales, utilice 'trust-region-reflective'.

  • Si tiene un problema semidefinido positivo con un número elevado de restricciones lineales y un número no elevado de variables, pruebe 'active-set'.

Para obtener ayuda si falla la minimización, consulte Cuando el solver falla o Cuando es posible que el solver haya tenido éxito.

Consulte Posible imprecisión con algoritmos interior-point.

Para ver descripciones de los algoritmos, consulte Quadratic Programming Algorithms.

Algoritmos a gran escala frente a algoritmos a media escala

Un algoritmo de optimización es a gran escala cuando utiliza álgebra lineal que no necesita almacenar matrices completas ni operar en ellas. Esto se puede hacer internamente almacenando matrices dispersas y utilizando álgebra lineal dispersa para los cálculos siempre que sea posible. Además, los algoritmos internos pueden mantener la dispersión, como la descomposición dispersa de Cholesky, o no generar matrices, como un método de gradiente conjugado.

En cambio, los métodos a mediana escala crean internamente matrices completas y utilizan álgebra lineal denso. Si un problema es lo suficientemente grande, las matrices completas ocupan una cantidad de memoria considerable y es posible que se necesite mucho tiempo para ejecutar el álgebra lineal denso.

No se deje confundir por el nombre "a gran escala": puede utilizar un algoritmo a gran escala en un problema pequeño. Asimismo, no tiene que especificar ninguna matriz dispersa para utilizar un algoritmo a gran escala. Elija un algoritmo a media escala para acceder a funcionalidades adicionales, como tipos de restricciones adicionales o, tal vez, para un mejor rendimiento.

Posible imprecisión con algoritmos interior-point

Los algoritmos interior-point de fmincon, quadprog, lsqlin y linprog tienen muchas características buenas, como el uso reducido de la memoria y la capacidad de resolver problemas grandes con rapidez. Sin embargo, sus soluciones pueden ser ligeramente menos precisas que las de otros algoritmos. La razón para esta posible imprecisión es que la función de barrera (calculada de forma interna) mantiene las iteraciones lejos de los límites de restricciones de desigualdad.

Para la mayoría de los fines prácticos, esta imprecisión suele ser bastante pequeña.

Para reducir la imprecisión, pruebe a:

  • Volver a ejecutar el solver con tolerancias StepTolerance, OptimalityTolerance y, tal vez, ConstraintTolerance más pequeñas (manteniéndolas dentro de lo razonable). Consulte Tolerancias y criterios de detención.

  • Ejecutar un algoritmo diferente empezando por la solución interior-point. Esto puede fallar, ya que algunos algoritmos pueden utilizar una memoria o un tiempo excesivos, y todos los algoritmos linprog y algunos algoritmos quadprog no aceptan un punto inicial.

Por ejemplo, pruebe a minimizar la función x cuando está acotada debajo en 0. Con el algoritmo interior-point predeterminado de fmincon:

options = optimoptions(@fmincon,'Algorithm','interior-point','Display','off');
x = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x =

   2.0000e-08

Con el algoritmo sqp de fmincon:

options.Algorithm = 'sqp';
x2 = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x2 =

   0

De forma similar, resuelva el mismo problema utilizando el algoritmo interior-point-legacy de linprog:

opts = optimoptions(@linprog,'Display','off','Algorithm','interior-point-legacy');
x = linprog(1,[],[],[],[],0,[],1,opts)
x =

   2.0833e-13

Con el algoritmo dual-simplex de linprog:

opts.Algorithm = 'dual-simplex';
x2 = linprog(1,[],[],[],[],0,[],1,opts)
x2 =

     0

En estos casos, los algoritmos interior-point son menos precisos, pero las respuestas se aproximan bastante a la respuesta correcta.