NUMAL Section 5.1.2.2.2

BEGIN SECTION : 5.1.2.2.2 (December, 1979)

AUTHOR: J.C.P. BUS.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED:  741101.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS THE PROCEDURE PRAXIS;
    PRAXIS MINIMIZES A FUNCTION OF SEVERAL VARIABLES.

KEYWORDS:

    MINIMIZATION,
    FUNCTION OF SEVERAL VARIABLES.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "PROCEDURE" PRAXIS(N, X, FUNCT, IN, OUT); "VALUE" N;
    "INTEGER" N; "ARRAY" X, IN, OUT; "REAL" "PROCEDURE" FUNCT;
    "CODE" 34432;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            THE NUMBER OF VARIABLES OF THE FUNCTION TO BE MINIMIZED;
    X:      <ARRAY IDENTIFIER>;
            "ARRAY" X[1 : N];
            THE VARIABLES OF THE FUNCTION;
            ENTRY: AN APPROXIMATION OF THE POSITION OF THE MINIMUM;
            EXIT:  THE CALCULATED POSITION OF THE MINIMUM;
    FUNCT:  <PROCEDURE IDENTIFIER>;
            THE HEADING OF THIS PROCEDURE SHOULD BE:
            "REAL" "PROCEDURE" FUNCT(N, X); "VALUE" N;
            "INTEGER" N; "ARRAY" X;

            FUNCT SHOULD DELIVER THE VALUE OF THE FUNCTION TO BE
                   MINIMIZED, AT THE POINT GIVEN BY X[1:N];

            THE MEANING OF THE FORMAL PARAMETERS IS:
            N:  <ARITHMETIC EXPRESSION>;
                THE NUMBER OF VARIABLES;
            X:  <ARRAY IDENTIFIER>; "ARRAY" X[1:N];
                THE VALUES OF THE VARIABLES FOR WHICH THE FUNCTION HAS
                TO BE EVALUATED;
    IN:     <ARRAY IDENTIFIER>;
            "ARRAY" IN[0:9];
            ENTRY:
                IN[0]:  THE MACHINE PRECISION; FOR THE CYBER 73  A
                        SUITABLE VALUE IS "-14;

                IN[1], IN[2]: RELATIVE AND ABSOLUTE TOLERANCE,
                        RESPECTIVELY, FOR THE STEPVECTOR
                        (RELATIVE TO THE CURRENT ESTIMATES OF
                        THE VARIABLES); THE PROCESS IS TERMINATED WHEN
                        IN IN[8] + 1 SUCCESSIVE ITERATION STEPS THE
                        EUCLIDEAN NORM OF THE STEP VECTOR IS LESS THAN
                        (IN[1] * NORM(X) + IN[2]) * 0.5;
                        IN[1] SHOULD BE CHOSEN IN AGREEMENT WITH THE
                        PRECISION IN WHICH THE FUNCTION IS CALCULATED;
                        USUALLY IN[1] SHOULD BE CHOSEN SUCH THAT
                        IN[1] >= SQRT(IN[0]); IN[0] SHOULD BE CHOSEN
                        DIFFERENT FROM ZERO.
                IN[3], IN[4] ARE NEITHER USED NOR CHANGED;
                IN[5]:  THE MAXIMUM NUMBER OF FUNCTION EVALUATIONS
                        ALLOWED (I.E. CALLS OF FUNCT);
                IN[6]:  THE MAXIMUM STEP SIZE; IN[6] SHOULD BE EQUAL TO
                        THE MAXIMUM EXPECTED DISTANCE BETWEEN THE GUESS
                        AND THE MINIMUM; IF IN[6] IS TOO SMALL OR TOO
                        LARGE, THEN THE INITIAL RATE OF CONVERGENCE
                        WILL BE SLOW;
                IN[7]:  THE MAXIMUM SCALING FACTOR; THE VALUE OF IN[7]
                        MAY BE USED TO OBTAIN AUTOMATIC SCALING OF THE
                        VARIABLES; HOWEVER, THIS SCALING IS WORTHWHILE
                        BUT MAY BE UNRELIABLE; THEREFORE, THE USER
                        SHOULD TRY TO SCALE HIS PROBLEM HIMSELF AS WELL
                        AS POSSIBLE AND SET IN[7]:= 1; IN EITHER CASE,
                        IN[7] SHOULD NOT BE CHOSEN GREATER THAN 10;
                IN[8]:  THE PROCESS TERMINATES IF NO SUBSTANTIAL
                        IMPROVEMENT OF THE VALUES OF THE VARIABLES IS
                        OBTAINED IN IN[8] + 1 SUCCESSIVE ITERATION
                        STEPS (SEE IN[1], IN[2]); IN[8] = 4  IS VERY
                        CAUTIOUS; USUALLY, IN[8] = 1 IS SATISFACTORY;
                IN[9]:  IF THE PROBLEM IS KNOWN TO BE ILL-CONDITIONED
                        (SEE [1]), THEN THE VALUE OF IN[9] SHOULD BE
                        NEGATIVE, OTHERWISE IN[9] >= 0;
    OUT:    <ARRAY IDENTIFIER>;
            "ARRAY" OUT[1:6];
            EXIT:
                OUT[1]: THIS VALUE GIVES INFORMATION ABOUT THE
                        TERMINATION OF THE PROCESS;
                        OUT[1] = 0: NORMAL TERMINATION;
                        OUT[1] = 1: THE PROCESS IS BROKEN OFF, BECAUSE,
                                    AT THE END OF AN ITERATION STEP,
                                    THE NUMBER OF CALLS OF FUNCT
                                    EXCEEDED THE VALUE GIVEN IN IN[5];
                        OUT[1] = 2: THE PROCESS IS BROKEN OFF, BECAUSE
                                    THE CONDITION OF THE PROBLEM IS TOO
                                    BAD;
                OUT[2]: THE CALCULATED MINIMUM OF THE FUNCTION;
                OUT[3]: THE VALUE OF THE FUNCTION AT THE INITIAL GUESS;
                OUT[4]: THE NUMBER OF FUNCTION EVALUATIONS NEEDED TO
                        OBTAIN THIS RESULT;
                OUT[5]: THE NUMBER OF LINE SEARCHES (SEE [1]);
                OUT[6]: THE STEP SIZE IN THE LAST ITERATION STEP.

PROCEDURES USED:

    INIVEC       = CP31010,
    INIMAT       = CP31011,
    DUPVEC       = CP31030,
    DUPMAT       = CP31035,
    DUPCOLVEC    = CP31034,
    MULROW       = CP31021,
    MULCOL       = CP31022,
    VECVEC       = CP34010,
    TAMMAT       = CP34014,
    MATTAM       = CP34015,
    ICHROWCOL    = CP34033,
    ELMVECCOL    = CP34021,
    QRISNGVALDEC = CP34273,
    SETRANDOM    = CP11014,
    RANDOM       = CP11015,
    DWARF        = CP30003.

REQUIRED CENTRAL MEMORY:

    EXECUTION FIELD LENGTH: ONE ARRAY OF LENGTH  N SQUARED AND FIVE
                            ARRAYS OF LENGTH  N  ARE DECLARED;

RUNNING TIME:

    THE NUMBER OF ITERATION STEPS DEPENDS STRONGLY ON THE PROBLEM TO BE
    SOLVED.

METHOD AND PERFORMANCE:

    THIS PROCEDURE IS ADOPTED FROM [1].

REFERENCES:

    [1] R. P. BRENT,
        ALGORITHMS FOR MINIMIZATION WITHOUT DERIVATIVES, CH. 7.
        PRENTICE HALL, 1973.

EXAMPLE OF USE:

    THE FOLLOWING PROGRAM MAY BE USED TO CALCULATE THE MINIMUM OF THE
    FUNCTION F(X) = 100 * (X[2] - X[1] ** 2) ** 2 + (1 - X[1]) ** 2,
    USING (-1.2, 1) AS AN INITIAL ESTIMATE.

    "BEGIN"

       "ARRAY" X[1:2], IN[0:9], OUT[1:6];

       "REAL" "PROCEDURE" F(N, X); "VALUE" N; "INTEGER" N; "ARRAY" X;
       F:= (X[2] - X[1] ** 2) ** 2 * 100 + (1 - X[1]) ** 2;

       IN[0]:= "-14; IN[1]:= IN[2]:= "-6; IN[5]:= 250;
       IN[6]:= 1; IN[7]:= 1; IN[8]:= 1; IN[9]:= 1;

       X[1]:= -1.2; X[2]:= 1;
       PRAXIS(2, X, F, IN, OUT);
       "IF" OUT[1] = 0 "THEN" OUTPUT(61,"(""("    NORMAL TERMINATION")"
       ,//")");
       OUTPUT(61, "("4B,"("MINIMUM IS ")",N,/,4B,
       "("FOR X IS ")", 2(N),/,4B,
       "("THE INITIAL FUNCTION VALUE WAS ")" ,N,/,4B,
       "("THE NUMBER OF FUNCTION EVALUATIONS NEEDED WAS ")",3ZD,/,4B,
       "("THE NUMBER OF LINE SEARCHES WAS ")",3ZD,/,4B,
       "("THE STEP SIZE IN THE LAST ITERATION STEP WAS ")", N,/")",
       OUT[2], X[1], X[2], OUT[3], OUT[4], OUT[5], OUT[6])
    "END"

    RESULTS:

    NORMAL TERMINATION

    MINIMUM IS +1.5694986738789"-021
    FOR X IS +1.0000000000389"+000  +1.0000000000785"+000
    THE INITIAL FUNCTION VALUE WAS +2.4200000000001"+001
    THE NUMBER OF FUNCTION EVALUATIONS NEEDED WAS  189
    THE NUMBER OF LINE SEARCHES WAS   72
    THE STEP SIZE IN THE LAST ITERATION STEP WAS +5.3830998470105"-009

SOURCE TEXT(S):

"CODE" 34432;