5 TERMINATION CRITERIA USED

donlp2 has a lot of termination criteria built in, many of which can be controlled by the user. However, an unexperienced user is warned to use too sloppy criteria, since often for nonconvex problems progress in the iteration may be quite irregular. There may occur many steps with seemingly small progress followed by a sudden improvement. The following termination messages may occur, which are explained here in detail:

  1. 'CONSTRAINT EVALUATION RETURNS ERROR WITH CURRENT POINT'
    The user evaluation routines EH/EGRADH or EG/EGRADG did set an error indicator then asked for a new value and reduction of the trial stepsize down to its minimum did not remove the situation. Usually this means that an inadequate starting point has been provided. Also box constraints may have not been used adequately in order to prevent boundary points of the feasible set there some function is undefined.

  2. 'OBJECTIVE EVALUATION RETURNS ERROR WITH CURRENT POINT'
    Same reason as above with respect to the objective function.

  3. 'QPSOLVER: EXTENDED QP-PROBLEM SEEMINGLY INFEASIBLE '
    Theoretically, this is impossible, since the QP problem is constructed such that a feasible solution always exists. Hence this message means that the solution process is severely corrupted by roundoff, most probably a problem of bad scaling which was not overcome by the internal scaling techniques.

  4. 'QPSOLVER: NO DESCENT FOR INFEAS FROM QP FOR TAU=TAU MAX'
    This means that a stationary point of the penalty function has been located which is not feasible. From the theory of the method it follows that the problem is not penalizable, at least in the region of the current point, since the Mangasarian Fromowitz condition, under which global convergence is proved, is the weakest possible for this purpose. Incresing TAUMAX may sometimes remove the situation. (TAUMAX represents a "very big" penalty).

  5. 'QPSOLVER: ON EXIT CORRECTION SMALL, INFEASIBLE POINT'
    Same reason as above

  6. 'STEPSIZESELECTION: COMPUTED D FROM QP NOT A DIR. OF DESCENT'
    Same as above or limiting accuracy reached for a singular problem, with termination criteria being too strong. (The method usually tries the outcome d of the QP-solver in spite of problems signaled from the solver as a direction of descent. The final check is done in the stepsize selection subprogram.)

  7. 'MORE THAN MAXIT ITERATION STEPS'
    Progress is too slow to meet the termination criteria within the given iteration limit (either MAXIT or the user defined ITERMA number of steps)

  8. 'STEPSIZESELECTION: NO ACCEPTABLE STEPSIZE IN [SIGSM,SIGLA]'
    This may have a lot of different reasons. The most usual one is simply a programming error in the user supplied (analytical) gradients. It may also be due to termination criteria which are too stringent for the problem at hand, because of evaluation unpreciseness of functions and/or gradients or because of illconditioning of the (projected) Hessian matrix. Often the results are acceptable nevertheless, but the user should check that (e.g. by supplying an appropriate routine SOLCHK)

  9. 'SMALL CORRECTION FROM QP, INFEASIBLE POINT'
    A stationary point of the penalty function which is not feasible for the original problem has been located. Surely the problem is incompatible locally at least. Try some other initial guess.

  10. 'KT-CONDITIONS SATISFIED, NO FURTHER CORRECTION COMPUTED'
    means
                      ||h(x)||1 + ||g(x)- ||1  £   DELMIN
                                        || l- ||¥  £   SMALLW
                               || ÑL(x,m,l)|| £   EPSX(1 + || Ñf(x)||)
                                  | lT || g(x) | £   DELMIN*SMALLW*(NH+NG)


  11. 'COMPUTED CORRECTION SMALL, REGULAR CASE '
    means
                                             ||d||    £   (||x|| + EPSX)EPSX
                               ||ÑL(x,m,l)|| £   EPSX(1 + || Ñf(x)||)
                       | h(x)||1 + |g(x)-||1  £   DELMIN
                                       || l- ||¥ £   SMALLW


    where d is the computed correction for the current solution x. 

  12. 'STEPSIZESELECTION: X ALMOST FEASIBLE, DIR. DERIV. VERY SMALL'

    means that the directional derivative has become so small that progress cannot be expected. More precisely

                                     D F(x; d) ³ -100(|F (x)| + 1) * EPSMAC

    where F is the current penalty function. This occurs as a termination reason for illconditioned problems usually.

  13. 'KT-CONDITIONS (RELAXED) SATISFIED, SINGULAR POINT'

    means that we are at a point x where the matrix the constraint normals is illconditioned or singular and the following conditions are met, which describe a relaxed form of the KKT-conditions:

                         ||h(x)||1 +||g(x)-||1  £   DELMIN(NH+NG)
             ||h(x)prev||1+ ||g(xprev)-||1 £   DELMIN(NH+NG)
                                ||ÑL(x,m,l)|| £   100 ´ EPSX(1 + || Ñf(x)||)
                                             ||sl||1 £   DELMIN(NH+NG)


    where sl is the vector of articial slacks introduced to make the QP always consistent. Observe that dual feasibility and complementary slackness hold automatically for the current iterate, because we are solving a full QP subproblem.

  14. 'VERY SLOW PRIMAL PROGRESS, SINGULAR OR ILLCONDITONED PROBLEM'
    means the occurence of the following conditon for at least N consecutive steps:


                       ||h(x)||1 + ||g(x)-||1  £   DELMIN(NH+NG)
          ||h(x)prev||1 + ||g(xprev)- ||1 £   DELMIN(NH+NG)
                                       || l- ||¥ £   SMALLW
                                 | lT || g(x) | £   DELMIN*SMALLW*(NH+NG)
                               ||ÑL(x,m,l)|| £   10*EPSX(1 + ||Ñf(x)||)
                            |f(x) - f(xprev)| £   (|f(x)| + 1)EPS



    where EPS is computed from the machine precision EPSMAC and the variables EPSX and EPSDIF as follows:

            IF ( ANALYT ) THEN
                 EPS=MIN(EPSX,SQRT(EPSMAC))
            ELSE
                 EPS=EPSDIF
                 IF ( EPSX .LT. EPSDIF**2 ) EPSX=EPSDIF**2
            ENDIF
            EPS=MAX(EPSMAC*1000,MIN(1.D-3,EPS))

  15. 'MORE THAN NRESET SMALL CORRECTIONS IN X '

    means that for more than NRESET consecutive steps there were only componentwise small changes in the solution x as given by

                                       |xprev,i - xi| £ (|xi| + 0.01) ´ EPSX, i = 1,...,n

  16. 'CORRECTION FROM QP VERY SMALL, ALMOST FEASIBLE, SINGULAR '
    means that the gradients in the working set are linearly dependent or almost so, such that a full regularized QP is solved, with the outcome of a direction d satisfying

                                         ||d|| £ 0.01(min{1, ||x||} + EPSX) EPSX

    This could effect changes in ||x|| less than 0.01 ´ EPSX (relative) at most, hence we terminate since this may be highly inefficient. It may occur in a problem there the second order sufficiency condition is not satisfied and the matrix of gradients of binding constraints is singular or very illconditioned.

  17. 'NUMSM SMALL DIFFERENCES IN PENALTY FUNCTION,TERMINATE'

    For NUMSM consecutive steps there were only small changes in the penalty function (without the other termination criteria satisfied) as given by

                                      F(xprev) - F(x) £  EPSPHI (s|f(x)| + Y(x))

    where F is the current Penaltyfunction, Y the current penalty term and s the current scaling of the objective function.