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;