Convergence criteria

Topics covered in this chapter:

Convergence criteria

In Xpress-SLP there are two levels of convergence criteria. On the higher level, convergence is driven by the target relative feasibility / validation control XSLP_VALIDATIONTARGET_R, and the target first order validation tolerance XSLP_VALIDATIONTARGET_K. These high level targets drive the traditional SLP convergence measures, of which there are three types for testing convergence:

Strict convergence tests on variables
Extended convergence tests on variables
Convergence tests on the solution overall

Convergence overview

Strict Convergence

Three tolerances in XSLP are used to determine whether an individual variable has strictly converged, that is they describe the numerical behavior of convergence in the formal, mathematical sense.

XSLP_CTOL: The closure tolerance is compared against the movement of a variable relative to its initial step bound.
XSLP_ATOL_A: The absolute delta tolerance is compared against the absolute movement of a variable.
XSLP_ATOL_R: The relative delta tolerance is compared against the movement of a variable relative to its initial value.

Extended Convergence

There are six tolerances in XSLP used to determine whether an individual variable has converged according to the extended definition. These tests essentially measure the quality of the linearization, including the effect of changes to the nonlinear terms that contribute to a variable in the linearization. In order to be deemed to have converged in the extended sense, all terms in which it appears must satisfy at least one of the following:

XSLP_MTOL_A: The absolute matrix tolerance is compared against the approximation error relative only to the absolute value of the variable.
XSLP_MTOL_R: The relative matrix tolerance is compared against the approximation error relative to the size of the nonlinear term before any step is taken.
XSLP_ITOL_A: The absolute impact tolerance is compared against the approximation error of the nonlinear term.
XSLP_ITOL_R: The relative impact tolerance is compared against the approximation error relative to the positive and negative contributions to each constraint.
XSLP_STOL_A: The absolute slack impact tolerance is compared against the approximation error, but only for non-binding constraints, which is to say those for which the marginal value is small (as defined by XSLP_MVTOL).
XSLP_STOL_R: The relative slack impact tolerance is compared against the approximation error relative to the term's contribution to its constraints, but only for non-binding constraints, which is to say those for which the marginal value is small (as defined by XSLP_MVTOL).

Stopping Criterion

The stopping criterion requires that all variables in the problem have converged in one of the three senses. Detailed information regarding the conditions under which XSLP has terminated can be obtained from the XSLP_STATUS solver attribute. Note that a solution is deemed to have fully converged if all variables have converged in the strict sense. If all variables have converged either in the strict or extended sense, and there are no active step bounds, then the solution is called a practical solution. In contrast, the solution may be called converged if it is feasible and the objective is no longer improving. The following four control sets can be applied by XSLP to determine whether the objective is stationary, depending on the convergence control parameter XSLP_CONVERGENCEOPS:

VTOL: This is the baseline static objective function tolerance, which is compared against the change in the objective over a given number of iterations, relative to the average objective value. Satisfaction of VTOL does not imply convergence of the variables.
OTOL: This static objective function tolerance is applied when there are no unconverged variables in active constraints, although some variables with active step bounds might remain. It is compared to the change in the objective over a given number of iterations, relative to the average objective value.
XTOL: This static objective function tolerance is applied when a practical solution has been found. It is compared against the change in the objective over a given number of iterations, relative to the average objective value.
WTOL: The extended convergence continuation tolerance is applied when a practical solution has been found. It is compared to the change in the objective during the previous iteration.

Step Bounding

Step bounding in XSLP can be activated in two cases. It may be enabled adaptively in response to variable oscillation, or it may be enabled by after XSLP_SBSTART iterations, by setting XSLP_ALGORITHM appropriately. Two major controls define the behaviour of step bounds:

XSLP_SBSTART: This defines the number of iterations which must occur before XSLP may apply non-essential step bounding. When a linearization is unbounded, XSLP will introduce step bounding regardless of the value of this control.
XSLP_DEFAULTSTEPBOUND: This is the initial size of the step bounds introduced. Depending upon the value of XSLP_ALGORITHM, XSLP may use the iterations before XSLP_SBSTART to refine this initial value on a per variable basis.

Convergence: technical details

In the following sections we shall use the subscript 0 to refer to values used to build the linear approximation (the assumed value) and the subscript 1 to refer to values in the solution to the linear approximation (the actual value). We shall also use δ to indicate the change between the assumed and the actual values, so that for example:
δX = X₁ - X₀.

The tests are described in detail later in this section. Tests are first carried out on each variable in turn, according to the following sequence:

Strict convergence criteria:

Closure tolerance (CTOL).
This tests δX against the initial step bound of X.
Delta tolerance (ATOL)
This tests δX against X₀.

If the strict convergence tests fail for a variable, it is tested against the extended convergence criteria:

Matrix tolerance (MTOL)
This tests whether the effect of a matrix coefficient is adequately approximated by the linearization. It tests the error against the magnitude of the effect.
Impact tolerance (ITOL)
This tests whether the effect of a matrix coefficient is adequately approximated by the linearization. It tests the error against the magnitude of the contributions to the constraint.
Slack impact tolerance (STOL)
This tests whether the effect of a matrix coefficient is adequately approximated by the linearization and is applied only if the constraint has a negligible marginal value (that is, it is regarded as "not constraining"). The test is the same as for the impact tolerance, but the tolerance values may be different.

The three extended convergence tests are applied simultaneously to all coefficients involving the variable, and each coefficient must pass at least one of the tests if the variable is to be regarded as converged. If any coefficient fails the test, the variable has not converged.

Regardless of whether the variable has passed the system convergence tests or not, if a convergence callback function has been set using XSLPsetcbitervar then it is called to allow the user to determine the convergence status of the variable.

User convergence test
This test is entirely in the hands of the user and can return one of three conditions: the variable has converged on user criteria; the variable has not converged; or the convergence status of the variable is unchanged from that determined by the system.

Once the tests have been completed for all the variables, there are several possibilities for the convergence status of the solution:

All variables have converged on strict criteria or user criteria.
All variables have converged, some on extended criteria, and there are no active step bounds (that is, there is no delta vector which is at its bound and has a significant reduced cost).
All variables have converged, some on extended criteria, and there are active step bounds (that is, there is at least one delta vector which is at its bound and has a significant reduced cost).
Some variables have not converged, but these have non-constant coefficients only in constraints which are not active (that is, the constraints do not have a significant marginal value);
Some variables have not converged, and at least one has a non-constant coefficient in an active constraint (that is, the constraint has a significant marginal value);

If (a) is true, then the solution has converged on strict convergence criteria.

If (b) is true, then the solution has converged on extended convergence criteria.

If (c) is true, then the solution is a practical solution. That is, the solution is an optimal solution to the linearization and, within the defined tolerances, it is a solution to the original nonlinear problem. It is possible to accept this as the solution to the nonlinear problem, or to continue optimizing to see if a better solution can be obtained.

If (d) or (e) is true, then the solution has not converged. Nevertheless, there are tests which can be applied to establish whether the solution can be regarded as converged, or at least whether there is benefit in continuing with more iterations.

The first convergence test on the solution simply tests the variation in the value of the objective function over a number of SLP iterations:

Objective function convergence test 1 (VTOL)
This test measures the range of the objective function (the difference between the maximum and minimum values) over a number of SLP iterations, and compares this against the magnitude of the average objective function value. If the range is small, then the solution is deemed to have converged.

Notice that this test says nothing about the convergence of the variables. Indeed, it is almost certain that the solution is not in any sense a practical solution to the original nonlinear problem. However, experience with a particular type of problem may show that the objective function does settle into a narrow range quickly, and is a good indicator of the ultimate value obtained. This test can therefore be used in circumstances where only an estimate of the solution value is required, not how it is made up. One example of this is where a set of schedules is being evaluated. If a quick estimate of the value of each schedule can be obtained, then only the most profitable or economical ones need be examined further.

If the convergence status of the variables is as in (d) above, then it may be that the solution is practical and can be regarded as converged:

Objective function convergence test 2 (XTOL)
If there are no unconverged values in active constraints, then the inaccuracies in the linearization (at least for small errors) are not important. If a constraint is not active, then deleting the constraint does not change the feasibility or optimality of the solution. The convergence test measures the range of the objective function (the difference between the maximum and minimum values) over a number of SLP iterations, and compares this against the magnitude of the average objective function value. If the range is small, then the solution is deemed to have converged.

The difference between this test and the previous one is the requirement for the convergence status of the variables to be (d).

Unless test 7 (VTOL) is being applied, if the convergence status of the variables is (e) then the solution has not converged and another SLP iteration will be carried out.

If the convergence status is (c), then the solution is practical. Because there are active step bounds in the solution, a "better" solution would be obtained to the linearization if the step bounds were relaxed. However, the linearization becomes less accurate the larger the step bounds become, so it might not be the case that a better solution would also be achieved for the nonlinear problem. There are two convergence tests which can be applied to decide whether it is worth continuing with more SLP iterations in the hope of improving the solution:

Objective function convergence test 3 (OTOL)
If all variables have converged (even if some are converged on extended criteria only, and some of those have active step bounds), the solution is a practical one. If the objective function has not changed significantly over the last few iterations, then it is reasonable to suppose that the solution will not be significantly improved by continuing with more SLP iterations. The convergence test measures the range of the objective function (the difference between the maximum and minimum values) over a number of SLP iterations, and compares this against the magnitude of the average objective function value. If the range is small, then the solution is deemed to have converged.
Extended convergence continuation test (WTOL)
Once a solution satisfying (c) has been found, we have a practical solution against which to compare solution values from later SLP iterations. As long as there has been a significant improvement in the objective function, then it is worth continuing. If the objective function over the last few iterations has failed to improve over the practical solution, then the practical solution is restored and the solution is deemed to have converged.

The difference between tests 9 and 10 is that 9 (OTOL) tests for the objective function being stable, whereas 10 (WTOL) tests whether it is actually improving. In either case, if the solution is deemed to have converged, then it has converged to a practical solution.

Closure tolerance (CTOL)

If an initial step bound is provided for a variable, then the closure test measures the significance of the magnitude of the delta compared to the magnitude of the initial step bound. More precisely:

Closure test:

ABS(δX) ≤ B * XSLP_CTOL

where B is the initial step bound for X. If no initial step bound is given for a particular variable, the closure test is not applied to that variable, even if automatic step bounds are applied to it during the solution process.

If a variable passes the closure test, then it is deemed to have converged.

Delta tolerance (ATOL)

The simplest tests for convergence measure whether the actual value of a variable in the solution is significantly different from the assumed value used to build the linear approximation.

The absolute test measures the significance of the magnitude of the delta; the relative test measures the significance of the magnitude of the delta compared to the magnitude of the assumed value. More precisely:

Absolute delta test:

ABS(δX) ≤ XSLP_ATOL_A

Relative delta test:

ABS(δX) ≤ X₀ * XSLP_ATOL_R

If a variable passes the absolute or relative delta tests, then it is deemed to have converged.

Matrix tolerance (MTOL)

The matrix tests for convergence measure the linearization error in the effect of a coefficient. The effect of a coefficient is its value multiplied by the activity of the column in which it appears.

E = V * C

where V is the activity of the matrix column in which the coefficient appears, and C is the value of the coefficient. The linearization approximates the effect of the coefficient as

E = V * C₀ + δX * C'₀

where V is as before, C₀ is the value of the coefficient C calculated using the assumed values for the variables and C'₀ is the value of

∂C

∂X

calculated using the assumed values for the variables.

The error in the effect of the coefficient is given by

δE = V₁ * C₁ - (V₁ * C₀ + δX * C'₀)

Absolute matrix test:

ABS(δE) ≤ XSLP_MTOL_A

Relative matrix test:

ABS(δE) ≤ V₀*X₀ * XSLP_MTOL_R

If all the coefficients which involve a given variable pass the absolute or relative matrix tests, then the variable is deemed to have converged.

Impact tolerance (ITOL)

The impact tests for convergence also measure the linearization error in the effect of a coefficient. The effect of a coefficient was described in the previous section. Whereas the matrix test compares the error against the magnitude of the coefficient itself, the impact test compares the error against a measure of the magnitude of the constraint in which it appears. All the elements of the constraint are examined: for each, the contribution to the constraint is evaluated as the element multiplied by the activity of the vector in which it appears; it is then included in a total positive contribution or total negative contribution depending on the sign of the contribution. If the predicted effect of the coefficient is positive, it is tested against the total positive contribution; if the effect of the coefficient is negative, it is tested against the total negative contribution.

As in the matrix tests, the predicted effect of the coefficient is

V * C₀ + δX * C'₀

and the error is

δE = V₁ * C₁ - (V₁ * C₀ + δX * C'₀)

Absolute impact test:

ABS(δE) ≤ XSLP_ITOL_A

Relative impact test:

ABS(δE) ≤ T₀ * XSLP_ITOL_R

where

T₀ = ABS(∑_v∈V v₀ * c₀)

c is the value of the constraint coefficient in the vector v; V is the set of vectors such that v₀*c₀ >0 if E is positive, or the set of vectors such that v₀*c₀ <0 if E is negative.

If a coefficient passes the matrix test, then it is deemed to have passed the impact test as well. If all the coefficients which involve a given variable pass the absolute or relative impact tests, then the variable is deemed to have converged.

Slack impact tolerance (STOL)

This test is identical in form to the impact test described in the previous section, but is applied only to constraints whose marginal value is less than XSLP_MVTOL. This allows a weaker test to be applied where the constraint is not, or is almost not, binding.

Absolute slack impact test:

ABS(δE) ≤ XSLP_STOL_A

Relative slack impact test:

ABS(δE) ≤ T₀ * XSLP_STOL_R

where the items in the expressions are as described in the previous section, and the tests are applied only when

ABS(π_i) < XSLP_MVTOL

where π_i is the marginal value of the constraint.

If all the coefficients which involve a given variable pass the absolute or relative matrix, impact or slack impact tests, then the variable is deemed to have converged.

Fixed variables due to determining columns smaller than threshold (FX)

Variables having a determining column, that are temporarily fixed due to the absolute value of the determining column being smaller than the threshold XSLP_DRCOLTOL are regarded as converged.

User-defined convergence

Regardless of what the Xpress-SLP convergence tests have said about the status of an individual variable, it is possible for the user to set the convergence status for a variable by using a function defined through the XSLPsetcbitervar callback registration procedure. The callback function returns an integer result S which is interpreted as follows:

S<0: mark variable as unconverged
S=0: leave convergence status of variable unchanged
S≥11: mark variable as converged with status S

Values of S in the range 1 to 10 are interpreted as meaning convergence on the standard system-defined criteria.

If a variable is marked by the user as converged, it is treated as if it has converged on strict criteria.

Static objective function (1) tolerance (VTOL)

This test does not measure convergence of individual variables, and in fact does not in any way imply that the solution has converged. However, it is sometimes useful to be able to terminate an optimization once the objective function appears to have stabilized. One example is where a set of possible schedules are being evaluated and initially only a good estimate of the likely objective function value is required, to eliminate the worst candidates.

The variation in the objective function is defined as

δObj = MAX_Iter(Obj) - MIN_Iter(Obj)

where Iter is the XSLP_VCOUNT most recent SLP iterations and Obj is the corresponding objective function value.

Absolute static objective function (3) test:

ABS(δObj) ≤ XSLP_VTOL_A

Relative static objective function (3) test:

ABS(δObj) ≤ AVG_Iter(Obj) * XSLP_VTOL_R

The static objective function (3) test is applied only after at least XSLP_VLIMIT + XSLP_SBSTART SLP iterations have taken place. Where step bounding is being applied, this ensures that the test is not applied until after step bounding has been introduced.

If the objective function passes the relative or absolute static objective function (3) test then the solution will be deemed to have converged.

Static objective function (2) tolerance (OTOL)

This test does not measure convergence of individual variables. Instead, it measures the significance of the changes in the objective function over recent SLP iterations. It is applied when all the variables interacting with active constraints (those that have a marginal value of at least XSLP_MVTOL) have converged. The rationale is that if the remaining unconverged variables are not involved in active constraints and if the objective function is not changing significantly between iterations, then the solution is more-or-less practical.

The variation in the objective function is defined as

δObj = MAX_Iter(Obj) - MIN_Iter(Obj)

where Iter is the XSLP_OCOUNT most recent SLP iterations and Obj is the corresponding objective function value.

Absolute static objective function (2) test:

ABS(δObj) ≤ XSLP_OTOL_A

Relative static objective function (2) test:

ABS(δObj) ≤ AVG_Iter(Obj) * XSLP_OTOL_R

If the objective function passes the relative or absolute static objective function (2) test then the solution is deemed to have converged.

Static objective function (3) tolerance (XTOL)

It may happen that all the variables have converged, but some have converged on extended criteria (MTOL, ITOL or STOL) and at least one of these is at its step bound. It is therefore possible that an improved result could be obtained by taking another SLP iteration. However, if the objective function has already been stable for several SLP iterations, then there is less likelihood of an improved result, and the converged solution can be accepted.

The static objective function (1) test measures the significance of the changes in the objective function over recent SLP iterations. It is applied when all the variables have converged, but some have converged on extended criteria (MTOL, ITOL or STOL) and at least one of these is at its step bound. Because all the variables have converged, the solution is already converged but the fact that some variables are at their step bound limit suggests that the objective function could be improved by going further.

The variation in the objective function is defined as

δObj = MAX_Iter(Obj) - MIN_Iter(Obj)

where Iter is the XSLP_XCOUNT most recent SLP iterations and Obj is the corresponding objective function value.

Absolute static objective function (1) test:

ABS(δObj) ≤ XSLP_XTOL_A

Relative static objective function (1) test:

ABS(δObj) ≤ AVG_Iter(Obj) * XSLP_XTOL_R

The static objective function (1) test is applied only until XSLP_XLIMIT SLP iterations have taken place. After that, if all the variables have converged on strict or extended criteria, the solution is deemed to have converged.

If the objective function passes the relative or absolute static objective function (1) test then the solution is deemed to have converged.

Extended convergence continuation tolerance (WTOL)

This test is applied after a converged solution has been found where at least one variable has converged on extended criteria and is at its step bound limit. As described under XTOL above, it is possible that by continuing with additional SLP iterations, the objective function might improve. The extended convergence continuation test measures whether any improvement is being achieved. If not, then the last converged solution will be restored and the optimization will stop.

For a maximization problem, the improvement in the objective function at the current iteration compared to the objective function at the last converged solution is given by:

δObj = Obj - ConvergedObj

(for a minimization problem, the sign is reversed).

Absolute extended convergence continuation test:

δObj > XSLP_WTOL_A

Relative extended convergence continuation test:

δObj > ABS(ConvergedObj) * XSLP_WTOL_R

A solution is deemed to have a significantly better objective function value than the converged solution if δObj passes the relative and absolute extended convergence continuation tests.

When a solution is found which converges on extended criteria and with active step bounds, the solution is saved and SLP optimization continues until one of the following:

a new solution is found which converges on some other criterion, in which case the SLP optimization stops with this new solution
a new solution is found which converges on extended criteria and with active step bounds, and which has a significantly better objective function, in which case this is taken as the new saved solution
none of the XSLP_WCOUNT most recent SLP iterations has a significantly better objective function than the saved solution, in which case the saved solution is restored and the SLP optimization stops

© 2001-2024 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.

Contents

Index

Glossary

Search Results

Convergence criteria