NUMAL Section 5.1.2.2.3

BEGIN SECTION : 5.1.2.2.3 (December, 1975)

AUTHOR: J.C.P.BUS.

INSTITUTE: MATHEMATICAL CENTRE.

RECEIVED: 730620.

BRIEF DESCRIPTION:

    THIS SECTION CONTAINS TWO PROCEDURES, RNK1MIN AND FLEMIN, FOR
    MINIMIZING A GIVEN DIFFERENTIABLE FUNCTION OF SEVERAL VARIABLES;
    BOTH PROCEDURES USE A VARIABLE METRIC METHOD; THE USER HAS TO
    PROGRAM THE EVALUATION OF THE FUNCTION AND ITS GRADIENT;
    THE CHOICE OF RNK1MIN AND FLEMIN IS DEPENDENT ON THE PROBLEM
    INVOLVED; IF THE NUMBER OF VARIABLES OF THE FUNCTION TO BE
    MINIMIZED IS VERY LARGE AND THE CALCULATION OF THE FUNCTION AND ITS
    GRADIENT IS RELATIVELY CHEAP (THE NUMBER OF ARITHMETIC OPERATIONS
    IS OF ORDER AT MOST N ** 2),THEN THE USER IS ADVISED TO USE FLEMIN;
    IF THE HESSIAN OF THE FUNCTION IS EXPECTED TO BE (ALMOST) SINGULAR
    AT THE MINIMUM, THEN RNK1MIN IS PREFERRED;

KEYWORDS:

    OPTIMIZATION,
    HIGHER - DIMENSIONAL,
    UNCONSTRAINED,
    VARIABLE METRIC METHOD.


SUBSECTION: RNK1MIN.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "REAL" "PROCEDURE" RNK1MIN(N, X, G, H, FUNCT, IN, OUT);
    "VALUE" N; "INTEGER" N;
    "ARRAY" X, G, H, IN, OUT;
    "REAL" "PROCEDURE" FUNCT;
   "CODE" 34214;

    RNK1MIN: DELIVERS THE CALCULATED LEAST VALUE OF THE GIVEN FUNCTION;

    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 INDEPENDENT VARIABLES;
            ENTRY:  AN APPROXIMATION OF A MINIMUM OF THE FUNCTION;
            EXIT:   THE CALCULATED MINIMUM OF THE FUNCTION;
    G:      <ARRAY IDENTIFIER>;
            "ARRAY" G[1 : N];
            EXIT:   THE GRADIENT  OF  THE FUNCTION  AT  THE  CALCULATED
                    MINIMUM;
    H:      <ARRAY IDENTIFIER>;
            "ARRAY" H[1 : N * (N + 1) // 2];
            THE  UPPERTRIANGLE  OF  AN  APPROXIMATION  OF  THE  INVERSE
            HESSIAN IS STORED COLUMNWISE IN H (I.E. THE I,J-TH ELEMENT=
            H[ (J - 1) * J // 2 + I], 1 <= I<= J <= N );
            IF  IN[6] > 0  INITIALIZING OF H WILL BE DONE AUTOMATICALLY
            AND  THE INITIAL APPROXIMATION  OF THE INVERSE HESSIAN WILL
            EQUAL THE UNITMATRIX MULTIPLIED WITH THE VALUE OF IN[6];
            IF IN[6] < 0 NO INITIALIZING OF H WILL BE DONE AND THE USER
            SHOULD GIVE IN  H  AN APPROXIMATION OF THE INVERSE HESSIAN,
            AT THE STARTING POINT;THE UPPERTRIANGLE OF AN APPROXIMATION
            OF  THE  INVERSE  HESSIAN  AT  THE  CALCULATED  MINIMUM  IS
            DELIVERED IN H;
    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 MUST EFFECTUATE IN:
            1:  FUNCT BECOMES THE VALUE OF THE FUNCTION TO BE MINIMIZED
                AT THE POINT X;
            2:  THE VALUE OF G[I], (I = 1, ..., N),  BECOMES  THE VALUE
                OF THE I - TH COMPONENT OF THE GRADIENT OF THE FUNCTION
                AT X;

    IN:     <ARRAY IDENTIFIER>;
            "ARRAY" IN[0 : 8];
            ENTRY:
            IN[0]:  THE MACHINE PRECISION;
                    FOR THE CYBER 73-26 A SUITABLE VALUE IS "-14;
            IN[1]:  THE RELATIVE TOLERANCE FOR THE SOLUTION;
                    THIS TOLERANCE SHOULD  NOT  BE CHOSEN  SMALLER THAN
                    IN[0];
            IN[2]:  THE ABSOLUTE TOLERANCE FOR THE SOLUTION;
            IN[3];  A PARAMETER USED FOR  CONTROLLING LINEMINIMIZATION,
                    ([3], [4]); USUALLY A SUITABLE VALUE IS: 0.0001;
            IN[4]:  THE ABSOLUTE  TOLERANCE  FOR  THE EUCLIDEAN NORM OF
                    THE GRADIENT AT THE SOLUTION;
            IN[5]:  A LOWERBOUND FOR THE FUNCTIONVALUE;
            IN[6]:  THIS PARAMETER  CONTROLS  THE INITIALIZATION OF THE
                    APPROXIMATION  OF  THE  INVERSE  HESSIAN  (METRIC),
                    SEE H; USUALLY THE CHOICE IN[6] = 1  WILL GIVE GOOD
                    RESULTS;
            IN[7]:  THE MAXIMUM ALLOWED NUMBER OF CALLS OF FUNCT;
            IN[8]:  A PARAMETER USED FOR  CONTROLLING  THE UPDATING  OF
                    THE METRIC; IT IS USED  TO AVOID  UNBOUNDEDNESS  OF
                    THE METRIC (SEE: [6], FORMULA (19));
                    THE VALUE OF IN[8] SHOULD SATISFY:
                    SQRT(IN[0] / IN[1]) / N < IN[8] < 1;
                    USUALLY A SUITABLE VALUE WILL BE 0.01;
    OUT:    <ARRAY IDENTIFIER>;
            "ARRAY" OUT[0:4];
            EXIT:
            OUT[0]: THE EUCLIDEAN NORM OF THE PRODUCT OF THE METRIC AND
                    THE GRADIENT AT THE CALCULATED MINIMUM;
            OUT[1]: THE  EUCLIDEAN  NORM   OF   THE  GRADIENT   AT  THE
                    CALCULATED MINIMUM;
            OUT[2]: THE NUMBER OF CALLS OF FUNCT,  NECESSARY  TO ATTAIN
                    THIS RESULT;
            OUT[3]: THE NUMBER OF ITERATIONS  IN WHICH A LINESEARCH WAS
                    NECESSARY;
            OUT[4]: THE NUMBER OF ITERATIONS  IN WHICH A DIRECTION  HAD
                    TO  BE  CALCULATED  WITH  THE METHOD  GIVEN IN [5];
                    IN  SUCH  AN  ITERATION   A    CALCULATION  OF  THE
                    EIGENVALUES  AND  EIGENVECTORS  OF  THE  METRIC  IS
                    NECESSARY.

DATA AND RESULTS:

    USUALLY THE CALCULATED SOLUTION WILL SATISFY:
    NORM ( XMIN - XCAL ) < NORM ( XCAL ) * IN[1] + IN[2].
    WHERE AT  XMIN THE GIVEN FUNCTION IS MINIMAL,  XCAL THE  CALCULATED
    APPROXIMATION OF XMIN AND NORM( . ) DENOTES THE EUCLIDEAN NORM
    OF X;  HOWEVER,  WE CANNOT GUARANTEE SUCH A RESULT;  THE CALCULATED
    SOLUTION  POSSIBLY WILL  NOT  SATISFY  THE ABOVE INEQUALITY  IF THE
    PROBLEM IS VERY ILL - CONDITIONED;  THE USER  CAN DISCOVER  SUCH  A
    SITUATION BY LOOKING AT THE EUCLIDEAN NORM OF THE METRIC, DELIVERED
    IN H; THE PROBLEM IS ILL - CONDITIONED IF  THIS  NORM  IS  LARGE
    RELATIVE TO 1.

PROCEDURES USED:

    VECVEC = CP34010,
    MATVEC = CP34011,
    TAMVEC = CP34012,
    SYMMATVEC = CP34018,
    INIVEC = CP31010,
    INISYMD = CP31013,
    MULVEC = CP31020,
    DUPVEC = CP31030,
    EIGSYM1 = CP34156,
    LINEMIN = CP34210,
    RNK1UPD = CP34211,
    DAVUPD = CP34212,
    FLEUPD = CP34213.

REQUIRED CENTRAL MEMORY:

    EXECUTION FIELD LENGTH: VARIES FROM 5 * N + 26 TO
                        N ** 2 + N * (N + 1) // 2 + 5 * N + 35 WORDS.

RUNNING TIME:

    DEPENDS STRONGLY ON THE PROBLEM TO BE SOLVED;

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    RNK1MIN  CALCULATES  AN APPROXIMATION  OF  A  MINIMUM  OF  A  GIVEN
    FUNCTION  BY  MEANS  OF  A  VARIABLE METRIC METHOD;  THE RANK - ONE
    UPDATING  FORMULA,  USED  IN  THIS  ALGORITHM   IS  GIVEN  IN  [6],
    (FORMULA (4));  TO AVOID  UNBOUNDEDNESS  OF  THE  METRIC (SEE [8]),
    SOMETIMES  A  RANK - TWO UPDATING  FORMULA IS USED  ([3],
    FORMULAS (1) AND (5)); TO AVOID LINESEARCHES AS MUCH AS POSSIBLE  A
    STRATEGY GIVEN IN [4] IS USED;  IF IN AN ITERATION  THE FUNCTION IS
    INCREASING IN THE DIRECTION GIVEN BY THE VARIABLE METRIC ALGORITHM,
    BECAUSE THE METRIC IS NOT POSITIVE DEFINITE, THEN A METHOD GIVEN IN
    [5] IS USED TO CALCULATE A NEW DIRECTION;  THIS METHOD REQUIRES
    THE CALCULATION OF THE EIGENVECTORS  AND EIGENVALUES OF THE METRIC;
    USUALLY,THE NUMBER OF TIMES SUCH A CALCULATION IS NECESSARY IS VERY
    SMALL RELATIVE TO THE NUMBER OF ITERATIONS (AND OFTEN EQUALS ZERO);
    IF THE NUMBER OF VARIABLES  OF THE FUNCTION  IS  VERY LARGE AND THE
    CALCULATION OF THE FUNCTION  AND  ITS GRADIENT  IS RELATIVELY CHEAP
    (THE NUMBER OF ARITHMETICAL OPERATIONS IS OF ORDER AT MOST N ** 2),
    THEN THE USER IS ADVISED TO USE FLEMIN (CP32105);
    A DETAILED DESCRIPTION OF THE ALGORITHM  AND SOME RESULTS ABOUT ITS
    CONVERGENCE IS GIVEN IN [1].


SUBSECTION: FLEMIN.

CALLING SEQUENCE:

    THE HEADING OF THIS PROCEDURE IS:
    "REAL" "PROCEDURE" FLEMIN(N, X, G, H, FUNCT, IN, OUT);
    "VALUE" N; "INTEGER" N;
    "ARRAY" X, G, H, IN, OUT; "REAL" "PROCEDURE" FUNCT;
   "CODE" 34215;

    FLEMIN: DELIVERS THE CALCULATED LEAST VALUE OF THE GIVEN FUNCTION;

    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 INDEPENDENT VARIABLES;
            ENTRY:  AN APPROXIMATION OF A MINIMUM OF THE FUNCTION;
            EXIT:   THE CALCULATED MINIMUM OF THE FUNCTION;
    G:      <ARRAY IDENTIFIER>;
            "ARRAY" G[1 : N];
            EXIT:   THE GRADIENT  OF  THE  FUNCTION  AT  THE CALCULATED
                    MINIMUM;
    H:      <ARRAY IDENTIFIER>;
            "ARRAY" H[1 : N * (N + 1) // 2];
            THE  UPPERTRIANGLE  OF  AN  APPROXIMATION  OF  THE  INVERSE
            HESSIAN IS STORED COLUMNWISE IN H (I.E. THE I,J-TH ELEMENT=
            H[ (J - 1) * J // 2 + I], 1 <= I <= J <= N);
            IF IN[6] > 0  INITIALIZING OF  H WILL BE DONE AUTOMATICALLY
            AND  THE INITIAL APPROXIMATION  OF THE INVERSE HESSIAN WILL
            EQUAL THE UNITMATRIX MULTIPLIED WITH THE VALUE OF IN[6]; IF
            IN[6] < 0  NO INITIALIZING OF  H  WILL BE DONE AND THE USER
            SHOULD GIVE IN  H  AN APPROXIMATION OF  THE INVERSE HESSIAN
            AT THE STARTING POINT;
            THE  UPPERTRIANGLE  OF  AN  APPROXIMATION  OF  THE  INVERSE
            HESSIAN AT THE CALCULATED MINIMUM IS DELIVERED IN H;
    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 IN:
            1:  FUNCT BECOMES THE VALUE OF THE FUNCTION TO BE MINIMIZED
                AT THE POINT X;
            2:  THE VALUE OF G[I], (I = 1, ..., N),  BECOMES  THE VALUE
                OF THE I - TH COMPONENT OF THE GRADIENT OF THE FUNCTION
                AT X;

    IN:     <ARRAY IDENTIFIER>;
            "ARRAY" IN[1 : 7];
            ENTRY:
            IN[1]:  THE RELATIVE TOLERANCE FOR THE SOLUTION;
            IN[2]:  THE ABSOLUTE TOLERANCE FOR THE SOLUTION;
            IN[3]:  A PARAMETER  USED FOR CONTROLLING LINEMINIMIZATION
                    ([3], [4]); USUALLY A SUITABLE VALUE IS 0.0001;
            IN[4]:  THE ABSOLUTE TOLERANCE  FOR  THE EUCLIDEAN  NORM OF
                    THE GRADIENT AT THE SOLUTION;
            IN[5]:  A LOWERBOUND FOR THE FUNCTION VALUE;
            IN[6]:  THIS  PARAMETER  CONTROLS THE INITIALIZATION OF THE
                    APPROXIMATION OF THE INVERSE HESSIAN (METRIC) (SEE
                    H); USUALLY IN[6] = 1 WILL GIVE GOOD RESULTS;
            IN[7]:  THE MAXIMUM ALLOWED NUMBER OF CALLS OF FUNCT;
    OUT:    <ARRAY IDENTIFIER>;
            "ARRAY" OUT[0:4];
            EXIT:
            OUT[0]: THE EUCLIDEAN NORM OF THE PRODUCT OF THE METRIC AND
                    THE GRADIENT AT THE CALCULATED MINIMUM;
            OUT[1]: THE  EUCLIDEAN  NORM    OF  THE  GRADIENT  AT   THE
                    CALCULATED MINIMUM;
            OUT[2]: THE NUMBER OF CALLS OF FUNCT,  NECESSARY  TO ATTAIN
                    THESE RESULTS;
            OUT[3]: THE NUMBER OF ITERATIONS IN WHICH A LINESEARCH  WAS
                    NECESSARY;
            OUT[4]: IF OUT[4] = - 1,  THEN  THE  PROCESS  IS BROKEN OFF
                    BECAUSE  NO DOWNHILL DIRECTION COULD BE CALCULATED;
                    THE PRECISION  ASKED FOR MAY NOT BE ATTAINED AND IS
                    POSSIBLY CHOSEN TOO HIGH;
                    NORMALLY OUT[4] = 0;

DATA AND RESULTS:

    USUALLY THE CALCULATED SOLUTION WILL SATISFY:
    NORM ( XMIN - XCAL ) < NORM ( XCAL ) * IN[1] + IN[2].
    WHERE AT XMIN THE GIVEN FUNCTION IS MINIMAL,  XCAL THE  CALCULATED
    APPROXIMATION OF XMIN AND NORM ( . )  DENOTES THE EUCLIDEAN  NORM
    OF X;  HOWEVER, WE CAN NOT GUARANTEE SUCH A RESULT;  THE CALCULATED
    SOLUTION POSSIBLY WILL NOT SATISFY  THE  ABOVE  INEQUALITY  IF  THE
    PROBLEM IS VERY ILL - CONDITIONED;  THE  USER  CAN  DISCOVER SUCH A
    SITUATION BY LOOKING AT THE EUCLIDEAN NORM OF THE METRIC, DELIVERED
    IN H;  THE  PROBLEM IS ILL - CONDITIONED  IF  THIS  NORM  IS  LARGE
    RELATIVE TO 1.

PROCEDURES USED:

    VECVEC = CP34010,
    ELMVEC = CP34020,
    SYMMATVEC = CP34018,
    INIVEC = CP31010,
    INISYMD = CP31013,
    MULVEC = CP31020,
    DUPVEC = CP31030,
    LINEMIN = CP34210,
    DAVUPD = CP34212,
    FLEUPD = CP34213.

REQUIRED CENTRAL MEMORY:

    EXECUTION FIELD LENGTH: 3 * N + 19 WORDS.

RUNNING TIME:

    DEPENDS STRONGLY ON THE PROBLEM TO BE SOLVED;

LANGUAGE:   ALGOL 60.

METHOD AND PERFORMANCE:

    FLEMIN CALCULATES AN APPROXIMATION OF A MINIMUM OF A GIVEN FUNCTION
    BY MEANS OF THE VARIABLE METRIC ALGORITHM GIVEN IN [3],  EXCEPT FOR
    SOME DETAILS (SEE [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.
    [5] GREENSTADT, J. L.
        ON THE RELATIVE EFFICIENCIES OF GRADIENT METHODS.
        MATH. COMP. 21, (1967), P.360 - 367.
    [6] POWELL, M. J. D.
        RANK ONE METHODS FOR UNCONSTRAINED OPTIMIZATION.
        IN: ABADIE, J. (ED.)
            INTEGER AND NONLINEAR PROGRAMMING.
            NORTH - HOLLAND, (1970).

EXAMPLE OF USE:

    THE MINIMUM OF THE FUNCTION:
    F(X) = (X[2] - X[1] ** 2) ** 2 * 100 + (1 - X[1]) ** 2,
    CALCULATED WITH BOTH  RNK1MIN  AND  FLEMIN  MAY  BE OBTAINED BY THE
    FOLLOWING PROGRAM:

"BEGIN"
    "REAL" "PROCEDURE" ROSENBROCK(N, X, G); "VALUE" N;
    "INTEGER" N; "ARRAY" X, G;
    "BEGIN" ROSENBROCK:= (X[2] - X[1] ** 2) ** 2 * 100
        + (1 - X[1]) ** 2;
        G[1]:= ((X[1] ** 2 - X[2]) * 400 + 2) * X[1] - 2;
        G[2]:=(X[2] - X[1] ** 2) * 200
    "END" ROSENBROCK;
    "INTEGER" I; "BOOLEAN" AGAIN; "REAL" F;
    "ARRAY" X, G[1:2], H[1:3], IN[0:8], OUT[0:4];

    IN[0]:= "-14; IN[1]:= "-5; IN[2]:= "-5; IN[3]:= "-4;
    IN[4]:= "-5; IN[5]:= -10; IN[6]:= 1; IN[7]:= 100; IN[8]:= 0.01;
    X[1]:= -1.2; X[2]:= 1; AGAIN:= "TRUE";
    F:= RNK1MIN(2, X, G, H, ROSENBROCK, IN, OUT);
    "GOTO" PRINT;
NEXT: X[1]:= -1.2; X[2]:= 1; AGAIN:= "FALSE";
    F:= FLEMIN(2, X, G, H, ROSENBROCK, IN, OUT);
PRINT: OUTPUT(61, "(""("LEAST VALUE:")"B+.15D"+3D,//, "("X:")",
    2(B+.15D"+3DB),//,"("GRADIENT:")", 2(B+.15D"+3DB),//, "("METRIC:")"
    ,2(B+.15D"+3DB),/,32B+.15D"+3D,//,"("OUT:")", 5(B+.15D"+3DB,/),///
    ")",F, X[1], X[2], G[1], G[2], H[1], H[2], H[3], OUT[0], OUT[1],
    OUT[2], OUT[3], OUT[4]);
    "IF" AGAIN "THEN" "GOTO" NEXT
"END"

    DELIVERS:

    LEAST VALUE: +.200699798801180"-018

    X: +.999999999944840"+000  +.999999999845220"+000

    GRADIENT: +.176731305145950"-007  -.889173179530190"-008

    METRIC: +.499982414863250"+000  +.999957383810230"+000
                                    +.200489757679290"+001

    OUT: +.164157123774660"-009
         +.197838933606480"-007
         +.550000000000000"+002
         +.800000000000000"+001
         +.400000000000000"+001

    LEAST VALUE: +.811973499921290"-016

    X: +.999999999758770"+000  +.999999998616780"+000

    GRADIENT: +.359826657359010"-006  -.180154557938290"-006

    METRIC: +.501085356975550"+000  +.100198139199600"+001
                                    +.200861655543510"+001

    OUT: +.133802289387830"-008
         +.402406371833370"-006
         +.440000000000000"+002
         +.700000000000000"+001
         +.000000000000000"+000

SOURCE TEXT(S):
"CODE" 34214;
"CODE" 34215;