NUMAL Section 5.1.2.2.1

BEGIN SECTION : 5.1.2.2.1 (December, 1975)

AUTHOR: J.C.P.BUS.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 730620.

BRIEF DESCRIPTION:
    THIS SECTION CONTAINS FOUR PROCEDURES, LINEMIN, RNK1UPD, DAVUPD AND
    FLEUPD, THAT ARE AUXILIARY PROCEDURES FOR THE PROCEDURES RNK1MIN
    AND FLEMIN (SECTION 5.1.2.2.2).

KEYWORDS:
    AUXILIARY PROCEDURE.


SUBSECTION: LINEMIN.

CALLING SEQUENCE:

    THE HEADING OF THIS AUXILIARY PROCEDURE IS:
    "PROCEDURE" LINEMIN(N, X, D, ND, ALFA, G, FUNCT, F0, F1, DF0, DF1,
    EVLMAX, STRONGSEARCH, IN);
    "VALUE" N, ND, F0, DF0, STRONGSEARCH;
    "INTEGER" N, EVLMAX; "BOOLEAN" STRONGSEARCH;
    "REAL" ND, ALFA, F0, F1, DF0, DF1;
    "ARRAY" X, D, G, IN; "REAL" "PROCEDURE" FUNCT;"CODE" 34210;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            THE NUMBER OF VARIABLES OF THE GIVEN FUNCTION F;
    X:      <ARRAY IDENTIFIER>;
            "ARRAY" X[1 : N];
            ENTRY:  A VECTOR  X0, SUCH THAT  F  IS DECREASING IN X0, IN
                    THE DIRECTION GIVEN BY D;
            EXIT:   THE  CALCULATED  APPROXIMATION  OF  THE  VECTOR FOR
                    WHICH F IS MINIMAL ON THE LINE DEFINED BY:
                    X0 + ALFA * D, (ALFA > 0);
    D:      <ARRAY IDENTIFIER>;
            "ARRAY" D[1 : N];
            ENTRY:  THE DIRECTION  OF THE LINE  ON WHICH  F  HAS  TO BE
                    MINIMIZED;
    ND:     <ARITHMETIC EXPRESSION>;
            ENTRY:  THE EUCLIDEAN NORM OF THE VECTOR GIVEN IN D[1 : N];
    ALFA:   <VARIABLE>;
            THE INDEPENDENT VARIABLE, THAT DEFINES  THE POSITION ON THE
            LINE ON WHICH F HAS TO BE MINIMIZED;
            THIS LINE IS DEFINED BY X0 + ALFA * D, (ALFA > 0);
            ENTRY:  AN ESTIMATE ALFA0 OF THE VALUE FOR WHICH
                    H(ALFA) = F(X0 + ALFA * D), (ALFA > 0), IS MINIMAL;
            EXIT:   THE CALCULATED APPROXIMATION ALFAM OF THE VALUE FOR
                    WHICH H(ALFA) IS MINIMAL;

    G:      <ARRAY IDENTIFIER>;
            "ARRAY" G[1 : N];
            EXIT:   THE GRADIENT OF  F  AT THE CALCULATED APPROXIMATION
                    OF THE MINIMUM;
    FUNCT:  <PROCEDURE IDENTIFIER>;
            THE HEADING OF THIS PROCEDURE SHOULD BE:
            "REAL" "PROCEDURE" FUNCT(N, X, G); "VALUE" N;
            "INTEGER" N; "ARRAY" X, G;
            A CALL OF FUNCT SHOULD EFFECTUATE :
            1:  FUNCT:= F(X);
            2:  THE VALUE OF G[I], (I = 1, ..., N),  BECOMES  THE VALUE
                OF THE I - TH COMPONENT OF THE GRADIENT OF F AT X;
    F0:     <ARITHMETIC EXPRESSION>;
            ENTRY:  THE VALUE OF H(0), (SEE ALFA);
    F1:     <VARIABLE>;
            ENTRY:  THE VALUE OF H(ALFA0);
            EXIT:   THE VALUE OF H(ALFAM), (SEE ALFA);
    DF0:    <ARITHMETIC EXPRESSION>;
            ENTRY:  THE VALUE OF THE DERIVATIVE OF H AT ALFA = 0;
    DF1:    <VARIABLE>;
            ENTRY:  THE VALUE OF THE DERIVATIVE OF H AT ALFA = ALFA0;
            EXIT:   THE VALUE OF THE DERIVATIVE OF H AT ALFA = ALFAM;
    EVLMAX: <VARIABLE>;
            ENTRY:  THE MAXIMUM ALLOWED NUMBER OF CALLS OF FUNCT;
            EXIT:   THE NUMBER OF TIMES FUNCT HAS BEEN CALLED;
    STRONGSEARCH:
            <BOOLEAN EXPRESSION>;
            IF  THE VALUE OF STRONGSEARCH IS  TRUE,  THEN  THE  PROCESS
            MAKES USE OF TWO STOPPING CRITERIA:
            A:  THE NUMBER OF TIMES FUNCT HAS BEEN CALLED EXCEEDS THE
                GIVEN VALUE OF EVLMAX;
            B:  AN INTERVAL IS FOUND  WITH LENGTH  LESS  THAN TWO TIMES
                THE PRESCRIBED PRECISION,ON WICH A MINIMUM IS EXPECTED;
            IF THE VALUE OF STRONGSEARCH  IS FALSE,  THE PROCESS  MAKES
            ALSO USE OF A THIRD STOPPING CRITERION :
            C:  MU <= (H(ALFAK) - H(ALFA0)) / (ALFAK * DF0) <= 1 - MU,
                WHEREBY ALFAK IS THE CURRENT ITERATE AND MU A
                PRESCRIBED CONSTANT;
    IN:     <ARRAY IDENTIFIER>;
            ENTRY:
            "ARRAY" IN[1:3];
            IN[1]:  THE  RELATIVE  PRECISION,  EPSR,  NECESSARY FOR THE
                    STOPPING CRITERION B, (SEE STRONGSEARCH);
            IN[2]:  THE  ABSOLUTE  PRECISION,  EPSA,  NECESSARY FOR THE
                    STOPPING CRITERION B, (SEE STRONGSEARCH);
            THE PRESCRIBED PRECISION, EPS, AT ALFA = ALFAK IS GIVEN BY:
            EPS = NORM ( X0 + ALPHA * D ) * EPSR + EPSA, WHERE
            NORM ( . ) DENOTES THE EUCLIDEAN NORM.
            IN[3]: THE PARAMETER MU NECESSARY FOR STOPPING CRITERION C;
                   THIS  PARAMETER  MUST  SATISFY:   0 < MU < 0.5 ; IN
                   PRACTICE,A CHOICE OF MU = 0.0001 IS ADVISED.

DATA AND RESULTS:

    LINEMIN   CALCULATES   AN    APPROXIMATION   OF   A  MINIMUM  OF  A
    HIGHER - DIMENSIONAL FUNCTION ON A GIVEN LINE;
    THE QUANTITY DF0 MUST SATIFY: DF0 < 0;
    IF MOREOVER DF1 > 0,  THEN  THE PROCEDURE WILL YIELD A RESULT  THAT
    SATISFIES ONE OF THE CHOSEN STOPPING CRITERIA, (SEE STRONGSEARCH),
    OTHERWISE WE CAN NOT GUARANTEE SUCH A RESULT.

PROCEDURES USED:

    VECVEC = CP34010,
    ELMVEC = CP34020,
    DUPVEC = CP31030.

REQUIRED CENTRAL MEMORY:
    N WORDS.

METHOD AND PERFORMANCE:

    AN APPROXIMATION TO THE MINIMUM  ON  THE  GIVEN LINE  IS CALCULATED
    WITH CUBIC INTERPOLATION ([2]);THE STOPPING CRITERION USED WHEN THE
    VALUE OF STRONGSEARCH IS FALSE  IS DESCRIBED  IN  [3]  AND  [4];  A
    DETAILED DESCRIPTION OF THIS PROCEDURE IS GIVEN IN [1].

REFERENCES:
    [1] BUS, J. C. P.
        MINIMIZATION OF FUNCTIONS OF SEVERAL VARIABLES (DUTCH).
        MATHEMATICAL CENTRE, AMSTERDAM, NR 29/72 (1972).
    [2] DAVIDON, W. C.
        VARIABLE METRIC METHOD FOR MINIMIZATION.
        ARGONNE NAT. LAB. REPORT, ANL 5990 (1959).
    [3] FLETCHER, R.
        A NEW APPROACH TO VARIABLE METRIC ALGORITHMS.
        COMP. J. 6, (1963), P.163 - 168.
    [4] GOLDSTEIN, A. A. AND PRICE, J. F.
        AN EFFECTIVE ALGORITHM FOR MINIMIZATION.
        NUMER. MATH. 10, (1967), P.184 - 189.


SUBSECTION: RNK1UPD.

CALLING SEQUENCE:

    THE HEADING OF THIS AUXILIARY PROCEDURE IS:
    "PROCEDURE" RNK1UPD(H, N, V, C); "VALUE" N, C;
    "INTEGER" N; "REAL" C; "ARRAY" H, V;
    "CODE" 34211;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE  SYMMETRIC  MATRIX, WHOSE UPPERTRIANGLE IS
            STORED COLUMNWISE IN THE ONE - DIMENSIONAL ARRAY H;
    C:      <ARITHMETIC EXPRESSION>;
            SEE V;
    V:      <ARRAY IDENTIFIER>;
            "ARRAY" V[1 : N];
            THE GIVEN MATRIX IS UPDATED (ANOTHER MATRIX IS ADDED TO IT)
            WITH A SYMMETRIC MATRIX , U, OF RANK ONE, DEFINED BY:
                       U[I,J] = C * V[I] * V[J];
    H:      <ARRAY IDENTIFIER>;
            "ARRAY" H[1 : N * (N + 1) // 2];
            ENTRY:  THE  UPPERTRIANGLE   (STORED  COLUMNWISE, I.E. :
                    A[I,J] = H[(J-1)*J//2+I], 1 <= I <= J <= N)
                    OF THE  SYMMETRIC MATRIX THAT HAS TO BE UPDATED;
            EXIT:   THE  UPPERTRIANGLE   (STORED  COLUMNWISE)   OF  THE
                    UPDATED MATRIX.

PROCEDURES USED:

    ELMVEC = CP34020.

REQUIRED CENTRAL MEMORY:

    NO AUXILIARY ARRAYS ARE DECLARED IN RNK1UPD.


SUBSECTION: DAVUPD.

CALLING SEQUENCE:

    THE HEADING OF THIS AUXILIARY PROCEDURE IS:
    "PROCEDURE" DAVUPD(H, N, V, W, C1, C2); "VALUE" N, C1, C2;
    "INTEGER" N; "REAL" C1, C2; "ARRAY" H, V, W;
    "CODE" 34212;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER  OF  THE  SYMMETRIC MATRIX WHOSE UPPERTRIANGLE IS
            STORED COLUMNWISE IN THE ONE - DIMENSIONAL ARRAY H;
    C1:     <ARITHMETIC EXPRESSION>;
            SEE W;
    C2:     <ARITHMETIC EXPRESSION>;
            SEE W;
    V:      <ARRAY IDENTIFIER>;
            "ARRAY" V[1 : N];
            SEE W;
    W:      <ARRAY IDENTIFIER>;
            "ARRAY" W[1 : N];
            THE GIVEN MATRIX  IS UPDATED  WITH  A SYMMETRIC MATRIX U OF
            RANK TWO, DEFINED BY:
            U[I,J] = C1 * V[I] * V[J] - C2 * W[I] * W[J];
    H:      <ARRAY IDENTIFIER>;
            "ARRAY" H[1 : N * (N + 1) // 2];
            ENTRY:  THE UPPERTRIANGLE (STORED COLUMNWISE, I.E. :
                    A[I,J] = H[(J - 1) * J // 2 + I], 1 <= I <= J <= N)
                    OF THE MATRIX  THAT HAS TO BE UPDATED;
            EXIT:   THE  UPPERTRIANGLE   (STORED  COLUMNWISE)   OF  THE
                    UPDATED MATRIX.

PROCEDURES USED: NONE.

REQUIRED CENTRAL MEMORY:

    NO AUXILIARY ARRAYS ARE DECLARED IN DAVUPD.


SUBSECTION: FLEUPD.

CALLING SEQUENCE:

    THE HEADING OF THIS AUXILIARY PROCEDURE IS:
    "PROCEDURE" FLEUPD(H, N, V, W, C1, C2); "VALUE" N, C1, C2;
    "INTEGER" N; "REAL" C1, C2; "ARRAY" H, V, W;
    "CODE" 34213;

    THE MEANING OF THE FORMAL PARAMETERS IS:
    N:      <ARITHMETIC EXPRESSION>;
            THE ORDER OF THE SYMMETRIC MATRIX  WHOSE  UPPERTRIANGLE  IS
            STORED COLUMNWISE IN THE ONE - DIMENSIONAL ARRAY H;
    C1:     <ARITHMETIC EXPRESSION>;
            SEE W;
    C2:     <ARITHMETIC EXPRESSION>;
            SEE W;
    V:      <ARRAY IDENTIFIER>;
            "ARRAY" V[1 : N];
            SEE W;
    W:      <ARRAY IDENTIFIER>;
            "ARRAY" W[1 : N];
            THE GIVEN MATRIX IS UPDATED  WITH A SYMMETRIC MATRIX  U  OF
            RANK TWO, DEFINED BY:
            U[I,J]= C2 * V[I] * V[J] - C1 *(V[I] * W[J] + W[I] * V[J]);
    H:      <ARRAY IDENTIFIER>;
            "ARRAY" H[1 : N * (N + 1) // 2];
            ENTRY:  THE UPPERTRIANGLE (STORED COLUMNWISE, I.E. :
                    A[I,J] = H[(J - 1) * J // 2 + I], 1 <= I <= J <= N)
                    OF THE MATRIX THAT HAS TO BE UPDATED;
            EXIT:   THE  UPPERTRIANGLE   (STORED  COLUMNWISE)   OF  THE
                    UPDATED MATRIX.

PROCEDURE USED: NONE.

REQUIRED CENTRAL MEMORY:

    NO AUXILIARY ARRAYS ARE DECLARED IN FLEUPD.

SOURCE TEXT(S):
"CODE" 34210;
"CODE" 34211;
"CODE" 34212;
"CODE" 34213;