Matlab优化求解器中的Tolerances and Stopping Criteria

文章目录

何为tolerance

The number of iterations in an optimization depends on a solver’s stopping criteria. These criteria include several tolerances you can set. Generally, a tolerance is a threshold which, if crossed, stops the iterations of a solver.
optimoptions displays tolerances. For example,

options = optimoptions('fmincon');

options=
fmincon options:

   Options used by current Algorithm ('interior-point'):
   (Other available algorithms: 'active-set', 'sqp', 'sqp-legacy', 'trust-region-reflective')

   Set properties:
     No options set.

   Default properties:
                    Algorithm: 'interior-point'
               CheckGradients: 0
          ConstraintTolerance: 1.0000e-06
                      Display: 'final'
     FiniteDifferenceStepSize: 'sqrt(eps)'
         FiniteDifferenceType: 'forward'
         HessianApproximation: 'bfgs'
                   HessianFcn: []
           HessianMultiplyFcn: []
                  HonorBounds: 1
       MaxFunctionEvaluations: 3000
                MaxIterations: 1000
               ObjectiveLimit: -1.0000e+20
          OptimalityTolerance: 1.0000e-06
                    OutputFcn: []
                      PlotFcn: []
                 ScaleProblem: 0
    SpecifyConstraintGradient: 0
     SpecifyObjectiveGradient: 0
                StepTolerance: 1.0000e-10
          SubproblemAlgorithm: 'factorization'
                     TypicalX: 'ones(numberOfVariables,1)'
                  UseParallel: 0
   Show options not used by current Algorithm ('interior-point')
   =================
[options.OptimalityTolerance,options.FunctionTolerance,options.StepTolerance]
ans =

   1.0e-06 *

    1.0000    1.0000    0.0001

主要的tolerance

1. StepTolerance
   StepTolerance is a lower bound on the size of a step, meaning the norm of (xi – xi+1). If the solver attempts to take a step that is smaller than StepTolerance, the iterations end. StepTolerance is sometimes used as a relative bound, meaning iterations end when |(xi – xi+1)| < StepTolerance*(1 + |xi|), or a similar relative measure.
2. FunctionTolerance
   For some algorithms, FunctionTolerance is a lower bound on the change in the value of the objective function during a step. For those algorithms, if |f(xi) – f(xi+1)| < FunctionTolerance, the iterations end. FunctionTolerance is sometimes used as a relative bound, meaning iterations end when |f(xi) – f(xi+1)| < FunctionTolerance*(1 + |f(xi)|), or a similar relative measure
   
3. OptimalityTolerance
   OptimalityTolerance is a tolerance for the first-order optimality measure. If the optimality measure is less than OptimalityTolerance, the iterations end. OptimalityTolerance can also be a relative bound on the first-order optimality measure. First-order optimality measure is defined in First-Order Optimality Measure.
   何为first-order optimality measure？
   一阶最优性用于度量点 x 与最优点的接近程度。大多数 Optimization Toolbox™ 求解器都使用此度量，尽管它对不同算法有不同定义。一阶最优性是必要条件，但不是充分条件。换言之：
   一阶最优性度量必须至少为零。
   一阶最优性等于零的点不一定是最小值。

一阶度量的停止规则
OptimalityTolerance 容差与一阶最优性度量相关。通常，如果一阶最优性度量小于 OptimalityTolerance，则求解器迭代结束。

一些求解器或算法使用相对一阶最优性作为停止条件。如果一阶最优性度量小于 μ 乘以 OptimalityTolerance，则求解器迭代结束；其中 μ 为：

目标函数在 x0 处的梯度的无穷范数（最大值）

求解器的输入的无穷范数（最大值），例如 linprog 中的 f 或 b 或者 quadprog 中的 H

相对度量尝试解释问题的规模。如果采用相对停止标准，将目标函数乘以很大或很小的数不会改变停止条件，如果采用未经缩放的标准，则会改变停止条件。

具有增强版退出消息的求解器会在停止标准详细信息中指出它们何时使用相对一阶最优性。
4. ConstraintTolerance
ConstraintTolerance is an upper bound on the magnitude of any constraint functions. If a solver returns a point x with c(x) > ConstraintTolerance or |ceq(x)| > ConstraintTolerance, the solver reports that the constraints are violated at x. ConstraintTolerance can also be a relative bound.