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;