Stopping Criteria

The INTPOINT Procedure

Stopping Criteria

There are several reasons why PROC INTPOINT stops Interior Point optimization. Optimization stops when:

the number of iteration equals MAXITERB=m
the relative gap (duality gap/(c^T x)) between the primal and dual objectives is smaller than the value of the PDGAPTOL= option, and both the primal and dual problems are feasible. Duality gap is defined in the "Interior Point Algorithmic Details" section.

PROC INTPOINT may stop optimization when it detects that the rate at which the complementarity or duality gap is being reduced is too slow; that is, that there are consecutive iterations when the complementarity or duality gap has stopped getting smaller and the infeasibilities, if nonzero, have also stalled. Sometimes this indicates that the problem is infeasible.

The reasons to stop optimization outlined in the previous paragraph will be termed the usual stopping conditions in the following explanation.

However, when solving some problems, especially if the problems are large, the usual stopping criteria are inappropriate. PROC INTPOINT might stop optimizing prematurely. If it were allowed to perform additional optimization, a better solution would be found. On other occasions, PROC INTPOINT might do too much work. A sufficiently good solution might be reached several iterations before PROC INTPOINT eventually stops.

You can see PROC INTPOINT's progress to the optimum by specifying PRINTLEVEL2=2. PROC INTPOINT will produce a table on the SAS log. A row of the table is generated during each iteration and consists of values of the affine step complementarity, the complementarity of the solution for the next iteration, the total bound infeasibility $\sum_{i=1}^n infeas_{b i}$ (see the infeas_b array in the "Interior Point: Upper Bounds" section), and the total constraint infeasibility $\sum_{i=1}^m infeas_{c i}$ (see the infeas_c array in the "Interior Point Algorithmic Details" section), the total dual infeasibility $\sum_{i=1}^n infeas_{d i}$ (see the infeas_d array in the "Interior Point Algorithmic Details" section). As optimization progresses, the values in all columns should converge to zero.

To tailor stopping criteria to your problem, you can use two sets of parameters: the STOP_x and the KEEPGOING_x parameters. The STOP_x parameters (STOP_C, STOP_DG, STOP_IB, STOP_IC, STOP_ID) are used to test for some condition at the beginning of each iteration and if met, to stop optimizing immediately. The KEEPGOING_x parameters (KEEPGOING_C, KEEPGOING_DG, KEEPGOING_IB, KEEPGOING_IC, KEEPGOING_ID) are used when PROC INTPOINT would ordinarily stop optimizing but does not if some conditions are not met.

For the sake of conciseness, a set of options might be referred to as the part of the option name they have in common followed by the suffix x. For example, STOP_C, STOP_DG, STOP_IB, STOP_IC, and STOP_ID will collectively be referred to as STOP_x.

At the beginning of each iteration, PROC INTPOINT will test whether complementarity is <= STOP_C (provided you specified a STOP_C parameter) and if it is, PROC INTPOINT will stop optimizing. If the duality gap is <= STOP_DG (provided you specified a STOP_DG parameter), PROC INTPOINT will stop optimizing immediately. This is true as well for the other STOP_x parameters that are related to infeasibilities, STOP_IB, STOP_IC, and STOP_ID.

For example, if you want PROC INTPOINT to stop optimizing for the usual stopping conditions, plus the additional condition, complementarity <= 100 or duality gap <= 0.001, then use:

   proc intpoint stop_c=100 stop_dg=0.001

If you want PROC INTPOINT to stop optimizing for the usual stopping conditions, plus the additional condition, complementarity <= 1000 and duality gap <= 0.001 and constraint infeasibility <= 0.0001, then use:

   proc intpoint 
      and_stop_c=1000 and_stop_dg=0.01 and_stop_ic=0.0001

Unlike the STOP_x parameters that cause PROC INTPOINT to stop optimizing when any one of them is satisfied, the corresponding AND_STOP_x parameters (AND_STOP_C, AND_STOP_DG, AND_STOP_IB, AND_STOP_IC, and AND_STOP_ID) cause PROC INTPOINT to stop only if all (more precisely, all that are specified) options are satisfied. For example, if PROC INTPOINT should stop optimizing when

complementarity <= 100 or duality gap <= 0.001 or
complementarity <= 1000 and duality gap <= 0.001 and constraint infeasibility <= 0.000

then use:

   proc intpoint 
      stop_c=100 stop_dg=0.001 
      and_stop_c=1000 and_stop_dg=0.01 and_stop_ic=0.0001

Just as the STOP_x parameters have AND_STOP_x partners, the KEEPGOING_x parameters have AND_KEEPGOING_x partners. The role of the KEEPGOING_x and AND_KEEPGOING_x parameters is to prevent optimization from stopping too early, even though a usual stopping criteria is met.

When PROC INTPOINT detects that it should stop optimizing for a usual stopping condition,

it will test whether complementarity is > KEEPGOING_C (provided you specified a KEEPGOING_C parameter), and if it is, PROC INTPOINT will perform more optimization.
Otherwise, PROC INTPOINT will then test whether the primal-dual gap is > KEEPGOING_DG (provided you specified a KEEPGOING_DG parameter), and if it is, PROC INTPOINT will perform more optimization.
Otherwise, PROC INTPOINT will then test whether the total bound infeasibility $\sum_{i=1}^n infeas_{b i} \gt$ KEEPGOING_IB (provided you specified a KEEPGOING_IB parameter), and if it is, PROC INTPOINT will perform more optimization.
Otherwise, PROC INTPOINT will then test whether the total constraint infeasibility $\sum_{i=1}^m infeas_{c i} \gt$ KEEPGOING_IC (provided you specified a KEEPGOING_IC parameter), and if it is, PROC INTPOINT will perform more optimization.
Otherwise, PROC INTPOINT will then test whether the total dual infeasibility $\sum_{i=1}^n infeas_{d i} \gt$ KEEPGOING_ID (provided you specified a KEEPGOING_ID parameter), and if it is, PROC INTPOINT will perform more optimization.
Otherwise it will test whether complementarity is > AND_KEEPGOING_C (provided you specified a AND_KEEPGOING_C parameter), and the primal-dual gap is > AND_KEEPGOING_DG (provided you specified a AND_KEEPGOING_DG parameter), and the total bound infeasibility $\sum_{i=1}^n infeas_{b i} \gt$ AND_KEEPGOING_IB (provided you specified a AND_KEEPGOING_IB parameter), and the total constraint infeasibility $\sum_{i=1}^m infeas_{c i} \gt$ AND_KEEPGOING_IC (provided you specified a AND_KEEPGOING_IC parameter), and the total dual infeasibility $\sum_{i=1}^n infeas_{d i} \gt$ AND_KEEPGOING_ID (provided you specified a AND_KEEPGOING_ID parameter), and if it is, PROC INTPOINT will perform more optimization.

If all these tests to decide whether more optimization should be performed are false, optimization is stopped.

The following PROC INTPOINT example will be used to illustrate how several stopping criteria options can be used together:

   proc intpoint 
      stop_c=1000 
      and_stop_c=2000 and_stop_dg=0.01 and_stop_ib=1 and_stop_ic=1 and_stop_id=1 
      keepgoing_c=1500 
      and_keepgoing_c=2500 and_keepgoing_dg=0.05 and_keepgoing_ib=1 and_keepgoing_ic=1 and_keepgoing_id=1

At the beginning of each iteration, PROC INTPOINT will stop optimizing if

complementarity <= 1000 or
complementarity <= 2000 and duality gap <= 0.01 and the total bound, constraint, and dual infeasibilities are each <= 1

When PROC INTPOINT determines it should stop optimizing because a usual stopping condition is met, it will stop optimizing only if

complementarity <= 1500 or
complementarity <= 2500 and duality gap <= 0.05 and the total bound, constraint, and dual infeasibilities are each <= 1

Chapter Contents
Previous
Next
Top