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;