Main Content

Cuando el solver falla

Demasiadas iteraciones o evaluaciones de función

El solver se ha detenido porque ha alcanzado un límite del número de iteraciones o evaluaciones de función antes de minimizar el objetivo a la tolerancia solicitada. Para continuar, pruebe una o más de las siguientes opciones.

1. Activar la visualización iterativa
2. Relajar las tolerancias
3. Iniciar el solver desde diferentes puntos
4. Comprobar las definiciones de la función objetivo y la función de restricción
5. Centrar y escalar el problema
6. Proporcionar gradiente o matriz jacobiana
7. Proporcionar una matriz hessiana

1. Activar la visualización iterativa

Establezca la opción Display en 'iter'. Este ajuste muestra los resultados de las iteraciones del solver.

Para habilitar la visualización interactiva, en la línea de comandos de MATLAB®, introduzca

options = optimoptions('solvername','Display','iter');

Llame al solver utilizando la estructura options.

Para ver un ejemplo de visualización iterativa, consulte Interpretar el resultado.

Qué buscar en la visualización iterativa

  • Compruebe si la función objetivo (Fval o f(x) o Resnorm) se reduce. La reducción indica progreso.

  • Examine la vulneración de la restricción (Max constraint) para asegurarse de que se reduce hacia 0. La reducción indica progreso.

  • Compruebe si la optimalidad de primer orden se reduce hacia 0. La reducción indica progreso.

  • Compruebe si el Trust-region radius se reduce a un valor pequeño. Esta reducción indica que es posible que el objetivo no sea suave.

Qué hacer

  • Si parecía que el solver progresaba:

    1. Establezca MaxIterations o MaxFunctionEvaluations en valores mayores que los valores predeterminados. Puede consultar los valores predeterminados en la tabla de opciones en las páginas de referencia de la función del solver.

    2. Inicie el solver desde su último punto calculado.

  • Si el solver no está progresando, pruebe el resto de sugerencias enumeradas.

2. Relajar las tolerancias

Si StepTolerance u OptimalityTolerance, por ejemplo, son demasiado pequeñas, es posible que el solver no reconozca cuándo ha alcanzado un mínimo; puede realizar iteraciones innecesarias indefinidamente.

Para cambiar las tolerancias en la línea de comandos, utilice optimoptions tal y como se describe en Establecer y modificar opciones.

La opción FiniteDifferenceStepSize (o las opciones DiffMaxChange y DiffMinChange) pueden afectar al progreso de un solver. Estas opciones controlan el tamaño del paso en diferenciación finita para la estimación de derivada.

3. Iniciar el solver desde diferentes puntos

Consulte Cambiar el punto inicial.

4. Comprobar las definiciones de la función objetivo y la función de restricción

Por ejemplo, compruebe que la función objetivo y la función de restricción no lineal devuelven los valores correctos en algunos puntos. Consulte Comprobar la función objetivo y la función de restricción. Compruebe que un punto no factible no cause ningún error en las funciones; consulte Las iteraciones pueden vulnerar las restricciones.

5. Centrar y escalar el problema

Los solvers se ejecutan con más fiabilidad cuando cada coordenada tiene aproximadamente el mismo efecto en la función objetivo y la función de restricción. Multiplique las direcciones de coordenadas con los escalares adecuados para igualar el efecto de cada coordenada. Agregue valores adecuados a determinadas coordenadas para igualar su tamaño.

Ejemplo: Centrar y escalar.  Considere minimizar 1e6*x(1)^2 + 1e-6*x(2)^2:

f = @(x) 10^6*x(1)^2 + 10^-6*x(2)^2;

Minimice f utilizando el algoritmo 'quasi-newton' de fminunc:

opts = optimoptions('fminunc','Display','none','Algorithm','quasi-newton');
x = fminunc(f,[0.5;0.5],opts)

x =
         0
    0.5000

El resultado es incorrecto; un mal escalado interfirió en la obtención de una buena solución.

Escale el problema. Establezca 

D = diag([1e-3,1e3]);
fr = @(y) f(D*y);
y = fminunc(fr, [0.5;0.5], opts)

y =
     0
     0 % the correct answer

Del mismo modo, un mal centrado puede interferir en una resolución.

fc = @(z)fr([z(1)-1e6;z(2)+1e6]); % poor centering
z = fminunc(fc,[.5 .5],opts)

z =
  1.0e+005 *
   10.0000  -10.0000 % looks good, but...

z - [1e6 -1e6] % checking how close z is to 1e6

ans =

   -0.0071    0.0078 % reveals a distance


fcc = @(w)fc([w(1)+1e6;w(2)-1e6]); % centered

w = fminunc(fcc,[.5 .5],opts)

w =
     0     0 % the correct answer

6. Proporcionar gradiente o matriz jacobiana

Si no proporciona gradientes o matrices jacobianas, los solvers estiman gradientes y matrices jacobianas mediante diferencias finitas. Por tanto, proporcionar estas derivadas puede ahorrar tiempo computacional y puede conducir a un aumento de la precisión. El enfoque basado en problemas puede proporcionar gradientes de manera automática; consulte Automatic Differentiation in Optimization Toolbox.

Para problemas restringidos, proporcionar un gradiente ofrece otra ventaja. Un solver puede alcanzar un punto x de forma que x sea factible, pero las diferencias finitas alrededor de x siempre conduzcan a un punto no factible. En este caso, un solver puede fallar o detenerse prematuramente. Proporcionar un gradiente permite al solver continuar.

Proporcione gradientes o matrices jacobianas en los archivos para la función objetivo y funciones de restricción no lineales. Para obtener detalles de la sintaxis, consulte Escribir funciones objetivo escalares, Escribir funciones objetivo de vector y de matriz y Restricciones no lineales.

Para comprobar que su gradiente o matriz jacobiana es correcta, utilice la opción CheckGradients, tal y como se describe en Checking Validity of Gradients or Jacobians.

Si tiene una licencia de Symbolic Math Toolbox™, puede calcular gradientes y matrices hessianas de forma programática. Para ver un ejemplo, consulte Calculate Gradients and Hessians Using Symbolic Math Toolbox.

Para ejemplos utilizando gradientes y matrices jacobianas, consulte Minimización con gradiente y matriz hessiana, Restricciones no lineales con gradientes, Calculate Gradients and Hessians Using Symbolic Math Toolbox, Resolver un sistema no lineal, sin y con matrices jacobianas y Large Sparse System of Nonlinear Equations with Jacobian. Para la diferenciación automática en el enfoque basado en problemas, consulte Effect of Automatic Differentiation in Problem-Based Optimization.

7. Proporcionar una matriz hessiana

A menudo, los solvers se ejecutan con más fiabilidad y con menos iteraciones cuando proporciona una matriz hessiana.

Los siguientes solvers y algoritmos aceptan matrices hessianas:

Si tiene una licencia de Symbolic Math Toolbox, puede calcular gradientes y matrices hessianas de forma programática. Para ver un ejemplo, consulte Calculate Gradients and Hessians Using Symbolic Math Toolbox. Para proporcionar una matriz hessiana en el enfoque basado en problemas, consulte Supply Derivatives in Problem-Based Workflow.

Ha convergido a un punto no factible

Por lo general, se obtiene este resultado dado que el solver fue incapaz de encontrar un punto que cumpliera todas las restricciones dentro de la tolerancia ConstraintTolerance. No obstante, es posible que el solver haya localizado o se haya iniciado en un punto factible y que haya convergido a un punto no factible. Si el solver ha perdido factibilidad, consulte El solver ha perdido factibilidad. Si quadprog devuelve este resultado, consulte quadprog converge a un punto no factible

Para continuar cuando el solver no haya encontrado ningún punto factible, pruebe una o más de las siguientes opciones.

1. Comprobar restricciones lineales
2. Comprobar restricciones no lineales

1. Comprobar restricciones lineales

Intente encontrar un punto que cumpla los límites y las restricciones lineales resolviendo un problema de programación lineal.

  1. Defina un problema de programación lineal con una función objetivo que siempre es cero:

    f = zeros(size(x0)); % assumes x0 is the initial point

  2. Resuelva el problema de programación lineal para comprobar si hay un punto factible:

    xnew = linprog(f,A,b,Aeq,beq,lb,ub);

  3. Si hay un punto factible xnew, utilice xnew como el punto inicial y vuelva a ejecutar el problema original.

  4. Si no hay punto factible, el problema no está bien formulado. Compruebe las definiciones de los límites y restricciones lineales. Para obtener más detalles sobre cómo comprobar restricciones lineales, consulte Investigate Linear Infeasibilities.

2. Comprobar restricciones no lineales

Después de asegurarse de que los límites y restricciones lineales son factibles (contienen un punto que cumple todas las restricciones), compruebe las restricciones no lineales.

  • Establezca la función objetivo en cero:

    @(x)0

    Ejecute la optimización con todas las restricciones y con el objetivo cero. Si encuentra un punto factible xnew, establezca x0 = xnew y vuelva a ejecutar el problema original.

  • Si no encuentra un punto factible utilizando una función objetivo cero, utilice la función objetivo cero con varios puntos iniciales.

    • Si encuentra un punto factible xnew, establezca x0 = xnew y vuelva a ejecutar el problema original.

    • Si no encuentra un punto factible, intente utilizar fmincon con la opción EnableFeasibilityMode establecida en true y la opción SubproblemAlgorithm establecida en 'cg', como en Obtain Solution Using Feasibility Mode. Pruebe varios puntos iniciales con estas opciones.

    • Si sigue sin encontrar un punto factible, intente relajar las restricciones, que se abordará a continuación.

Intente relajar las restricciones de desigualdad no lineales y ajústelas.

  1. Cambie la función de restricción no lineal c para que devuelva c-Δ, donde Δ es un número positivo. Este cambio hace que resulte más fácil cumplir las restricciones no lineales.

  2. Busque un punto factible para la nueva función de restricción utilizando la función objetivo original o la función objetivo cero.

    1. Si encuentra un punto factible,

      1. reduzca Δ

      2. busque un punto factible para la nueva función de restricción, empezando en el punto encontrado anteriormente.

    2. Si no encuentra un punto factible, intente aumentar Δ y buscar de nuevo.

Si no encuentra un punto factible, es posible que su problema sea verdaderamente no factible, lo que significa que no existe solución. Compruebe todas las definiciones de las restricciones de nuevo.

El solver ha perdido factibilidad

Si el solver se ha iniciado en un punto factible, pero ha convergido a un punto no factible, pruebe las siguientes técnicas.

  • Pruebe un algoritmo diferente. Los algoritmos 'sqp' e 'interior-point' de fmincon suelen ser los más robustos, así que pruebe uno o ambos en primer lugar.

  • Ajuste los límites. Proporcione el vector lb más alto y el vector ub más bajo que pueda. Esto puede ayudar al solver a mantener la factibilidad. Los algoritmos 'sqp' e 'interior-point' de fmincon respetan los límites en cada iteración, de manera que los límites estrictos ayudan durante la optimización.

quadprog converge a un punto no factible

Por lo general, obtiene este mensaje porque las restricciones lineales son inconsistentes o son casi singulares. Para comprobar si existe un punto factible, cree un problema de programación lineal con las mismas restricciones y con un vector de función objetivo cero f. Resuelva utilizando el algoritmo 'dual-simplex' de linprog:

options = optimoptions('linprog','Algorithm','dual-simplex');
x = linprog(f,A,b,Aeq,beq,lb,ub,options)

Si linprog no encuentra un punto factible, el problema es verdaderamente no factible.

Si linprog encuentra un punto factible, pruebe un algoritmo quadprog diferente. También puede cambiar algunas tolerancias como StepTolerance o ConstraintTolerance y resolver de nuevo el problema.

Problema desacotado

El solver ha alcanzado un punto cuya función objetivo era menor que la tolerancia del límite del objetivo.

  • Puede que su problema esté verdaderamente desacotado. En otras palabras, hay una secuencia de puntos xi con

    lim f(xi) = –∞.

    y de forma que todas las xi cumplen las restricciones de problema.

  • Compruebe que el problema está formulado correctamente. Los solvers intentan minimizar funciones objetivo; si desea un máximo, cambie su función objetivo a su función negativa. Para ver un ejemplo, consulte Maximizar un objetivo.

  • Intente escalar o centrar el problema. Consulte Centrar y escalar el problema.

  • Relaje la tolerancia del límite del objetivo utilizando optimoptions para reducir el valor de la tolerancia ObjectiveLimit.

fsolve no ha podido resolver la ecuación

fsolve puede fallar al resolver una ecuación por varias razones. Estas son algunas sugerencias sobre cómo proceder:

  1. Intente Cambiar el punto inicial. fsolve se basa en un punto inicial. Proporcionando diferentes puntos iniciales, aumenta las posibilidades de éxito.

  2. Compruebe la definición de la ecuación para asegurarse de que es suave. Puede que fsolve falle al converger ecuaciones con gradientes discontinuos, como valor absoluto. fsolve puede fallar al converger funciones con discontinuidades.

  3. Compruebe que la ecuación es "cuadrada", lo que significa que tiene las mismas dimensiones para la entrada y la salida (tiene el mismo número de incógnitas como valores de la ecuación).

  4. Cambie las tolerancias, especialmente OptimalityTolerance y StepTolerance. Si intenta conseguir una gran precisión estableciendo las tolerancias en valores muy pequeños, fsolve puede fallar al converger. Si establece tolerancias muy altas, fsolve puede fallar al resolver una ecuación con precisión.

  5. Compruebe la definición del problema. Algunos problemas no tienen solución real, como x^2 + 1 = 0. Si puede aceptar una solución compleja, intente establecer el punto inicial en un valor complejo. fsolve no intenta encontrar una solución compleja cuando el punto inicial es real.

Temas relacionados