NUMAL Section 5.1.2.1.2

BEGIN SECTION : 5.1.2.1.2 (October, 1975)

AUTHOR: J. C. P. BUS.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 741101.

BRIEF DESCRIPTION:
    THIS SECTION  CONTAINS  THE PROCEDURE  MININDER,  FOR  MINIMIZING A
    FUNCTION OF ONE VARIABLE IN A GIVEN INTERVAL,  WHEN  THE ANALYTICAL
    DERIVATIVE OF THE FUNCTION IS AVAILABLE.

KEYWORDS :
    MINIMIZATION,
    FUNCTIONS OF ONE VARIABLE.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "REAL" "PROCEDURE" MININDER(X, Y, FX, DFX, TOLX);
    "REAL" X, Y, FX, DFX, TOLX;
    "CODE" 34435;

    MININDER DELIVERS  THE CALCULATED  MINIMUM VALUE  OF  THE FUNCTION,
            DEFINED BY FX, ON THE INTERVAL WITH END POINTS A AND B.

    THE MEANING OF THE FORMAL PARAMETERS IS:
    X:      <REAL VARIABLE>;
            A JENSEN VARIABLE; THE ACTUAL PARAMETERS FOR FX, DFX AND
            TOLX DEPEND ON X;
            ENTRY:  ONE OF THE END POINTS OF THE INTERVAL ON WHICH THE
                    FUNCTION HAS TO BE MINIMIZED;
            EXIT:   THE CALCULATED APPROXIMATION OF THE POSITION OF THE
                    MINIMUM;
    Y:      <REAL VARIABLE>;
            ENTRY:  THE OTHER END POINT OF THE INTERVAL ON WHICH THE
                    FUNCTION HAS TO BE MINIMIZED;
            EXIT:   A VALUE SUCH THAT ABS(X - Y) <= TOL(X) * 3;
    FX:     <ARITHMETIC EXPRESSION>;
            THE FUNCTION IS GIVEN BY THE ACTUAL PARAMETER FX WHICH
            DEPENDS ON X;
    DFX:    <ARITHMETIC EXPRESSION>;
            THE DERIVATIVE OF THE FUNCTION IS GIVEN BY THE ACTUAL
            PARAMETER DFX WHICH DEPENDS ON X; FX AND DFX ARE  EVALUATED
            SUCCESSIVELY FOR A CERTAIN VALUE OF X;
    TOLX:   <ARITHMETIC EXPRESSION>;
            THE TOLERANCE IS GIVEN BY THE ACTUAL PARAMETER TOLX,  WHICH
            MAY  DEPEND   ON  X;  A  SUITABLE  TOLERANCE  FUNCTION  IS:
            ABS(X) * RE + AE,   WHERE  RE  IS  THE  RELATIVE  PRECISION
            DESIRED AND  AE  IS AN ABSOLUTE PRECISION  WHICH SHOULD NOT
            BE CHOSEN EQUAL TO ZERO.

DATA AND RESULTS:

    THE  USER  SHOULD  BE  AWARE OF THE FACT  THAT THE  CHOICE OF  TOLX
    MAY  HIGHLY   AFFECT  THE  BEHAVIOUR  OF  THE  ALGORITHM,  ALTHOUGH
    CONVERGENCE  TO  A  POINT  FOR  WHICH  THE  GIVEN  FUNCTION  IS
    MINIMAL ON THE  GIVEN  INTERVAL  IS  ASSURED;  THE  ASYMPTOTIC
    BEHAVIOUR WILL USUALLY BE FINE AS LONG AS THE NUMERICAL FUNCTION IS
    STRICTLY DELTA-UNIMODAL ON THE GIVEN INTERVAL (SEE [1]) AND THE
    TOLERANCE FUNCTION SATISFIES TOL(X) >= DELTA, FOR ALL X IN THE
    GIVEN INTERVAL; LET THE VALUE OF DFX AT THE BEGIN AND END POINT OF
    THE INITIAL INTERVAL BE DENOTED BY DFA AND DFB, RESPECTIVELY, THEN,
    FINDING A GLOBAL MINIMUM IS ONLY GUARANTEED IF THE FUNCTION IS
    CONVEX AND DFA <= 0 AND DFB >= 0; IF THESE CONDITIONS ARE NOT
    SATISFIED, THEN A LOCAL MINIMUM OR A MINIMUM AT ONE OF THE END
    POINTS MIGHT BE FOUND.

PROCEDURES USED: NONE.

REQUIRED CENTRAL MEMORY: NO AUXILIARY ARRAYS ARE DECLARED IN MININDER.

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    MININDER HAS ALMOST THE SAME STRUCTURE AS THE PROCEDURE GIVEN IN
    [1]; HOWEVER, CUBIC INTERPOLATION (SEE [2]) IS USED INSTEAD OF
    QUADRATIC INTERPOLATION TO APPROXIMATE THE MINIMIUM.

REFERENCES:

    [1]: BRENT, R.P.
         ALGORITHMS FOR MINIMIZATION WITHOUT DERIVATIVES. CH.5.
         PRENTICE HALL, 1973.
    [2]: DAVIDON, W.C.
         VARIABLE METRIC METHODS FOR MINIMIZATION.
         REP. A.N.L. 5990, 1959.

EXAMPLE OF USE:

    THE FOLLOWING PROGRAM MAY BE USED TO CALCULATE THE MINIMUM OF THE
    FUNCTION F(X) = SUM(((I * 2 - 5)/(X - I ** 2)) ** 2; I = 1 (1) 20)
    ON THE INTERVAL [1.01,3.99] (SEE [1]).

    "BEGIN"
        "REAL" M, X, Y; "INTEGER" CNT;

        "REAL" "PROCEDURE" F(X); "VALUE" X; "REAL" X;
        "BEGIN" "INTEGER" I; "REAL" S;
            S:= 0; "FOR" I:= 1 "STEP" 1 "UNTIL" 20 "DO"
            S:= S + ((I * 2 - 5) / (X - I ** 2)) ** 2;
            CNT:= CNT + 1; F:= S
        "END" F;

        "REAL" "PROCEDURE" DF(X); "VALUE" X; "REAL" X;
        "BEGIN" "INTEGER" I; "REAL" S;
            S:= 0; "FOR" I:= 1 "STEP" 1 "UNTIL" 20 "DO"
            S:= S + (I * 2 - 5) ** 2 / (X - I ** 2) ** 3;
            DF:= -S * 2
        "END" DF;

        "REAL" "PROCEDURE" TOL(X); "VALUE" X; "REAL" X;
        TOL:= ABS(X) * "-7 + "-7;

        X:= 1.01; Y:= 3.99; CNT:= 0;
        M:= MININDER(X, Y, F(X), DF(X),TOL(X));
        OUTPUT(61 ,"("4B,"("MINIMUM IS ")",N,/4B,
        "("FOR X IS ")",N,/4B,
        "("AND Y IS ")",N,/4B,
        "("THE NUMBER OF FUNCTION EVALUATIONS NEEDED IS ")",2ZD,/")",
        M, X, Y, CNT)
    "END"

    RESULTS:

    MINIMUM IS +3.6766990169021"+000
    FOR X IS +3.0229155250302"+000
    AND Y IS +3.0229151227386"+000
    THE NUMBER OF FUNCTION EVALUATIONS NEEDED IS   9

SOURCE TEXT(S):

"CODE" 34435;