NUMAL Section 5.1.2.1.2
BEGIN SECTION : 5.1.2.1.2 (October, 1975)
AUTHOR: J. C. P. BUS.
INSTITUTE: MATHEMATICAL CENTRE.
RECEIVED: 741101.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS THE PROCEDURE MININDER, FOR MINIMIZING A
FUNCTION OF ONE VARIABLE IN A GIVEN INTERVAL, WHEN THE ANALYTICAL
DERIVATIVE OF THE FUNCTION IS AVAILABLE.
KEYWORDS :
MINIMIZATION,
FUNCTIONS OF ONE VARIABLE.
CALLING SEQUENCE:
THE HEADING OF THIS PROCEDURE IS:
"REAL" "PROCEDURE" MININDER(X, Y, FX, DFX, TOLX);
"REAL" X, Y, FX, DFX, TOLX;
"CODE" 34435;
MININDER DELIVERS THE CALCULATED MINIMUM VALUE OF THE FUNCTION,
DEFINED BY FX, ON THE INTERVAL WITH END POINTS A AND B.
THE MEANING OF THE FORMAL PARAMETERS IS:
X: <REAL VARIABLE>;
A JENSEN VARIABLE; THE ACTUAL PARAMETERS FOR FX, DFX AND
TOLX DEPEND ON X;
ENTRY: ONE OF THE END POINTS OF THE INTERVAL ON WHICH THE
FUNCTION HAS TO BE MINIMIZED;
EXIT: THE CALCULATED APPROXIMATION OF THE POSITION OF THE
MINIMUM;
Y: <REAL VARIABLE>;
ENTRY: THE OTHER END POINT OF THE INTERVAL ON WHICH THE
FUNCTION HAS TO BE MINIMIZED;
EXIT: A VALUE SUCH THAT ABS(X - Y) <= TOL(X) * 3;
FX: <ARITHMETIC EXPRESSION>;
THE FUNCTION IS GIVEN BY THE ACTUAL PARAMETER FX WHICH
DEPENDS ON X;
DFX: <ARITHMETIC EXPRESSION>;
THE DERIVATIVE OF THE FUNCTION IS GIVEN BY THE ACTUAL
PARAMETER DFX WHICH DEPENDS ON X; FX AND DFX ARE EVALUATED
SUCCESSIVELY FOR A CERTAIN VALUE OF X;
TOLX: <ARITHMETIC EXPRESSION>;
THE TOLERANCE IS GIVEN BY THE ACTUAL PARAMETER TOLX, WHICH
MAY DEPEND ON X; A SUITABLE TOLERANCE FUNCTION IS:
ABS(X) * RE + AE, WHERE RE IS THE RELATIVE PRECISION
DESIRED AND AE IS AN ABSOLUTE PRECISION WHICH SHOULD NOT
BE CHOSEN EQUAL TO ZERO.
DATA AND RESULTS:
THE USER SHOULD BE AWARE OF THE FACT THAT THE CHOICE OF TOLX
MAY HIGHLY AFFECT THE BEHAVIOUR OF THE ALGORITHM, ALTHOUGH
CONVERGENCE TO A POINT FOR WHICH THE GIVEN FUNCTION IS
MINIMAL ON THE GIVEN INTERVAL IS ASSURED; THE ASYMPTOTIC
BEHAVIOUR WILL USUALLY BE FINE AS LONG AS THE NUMERICAL FUNCTION IS
STRICTLY DELTA-UNIMODAL ON THE GIVEN INTERVAL (SEE [1]) AND THE
TOLERANCE FUNCTION SATISFIES TOL(X) >= DELTA, FOR ALL X IN THE
GIVEN INTERVAL; LET THE VALUE OF DFX AT THE BEGIN AND END POINT OF
THE INITIAL INTERVAL BE DENOTED BY DFA AND DFB, RESPECTIVELY, THEN,
FINDING A GLOBAL MINIMUM IS ONLY GUARANTEED IF THE FUNCTION IS
CONVEX AND DFA <= 0 AND DFB >= 0; IF THESE CONDITIONS ARE NOT
SATISFIED, THEN A LOCAL MINIMUM OR A MINIMUM AT ONE OF THE END
POINTS MIGHT BE FOUND.
PROCEDURES USED: NONE.
REQUIRED CENTRAL MEMORY: NO AUXILIARY ARRAYS ARE DECLARED IN MININDER.
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE:
MININDER HAS ALMOST THE SAME STRUCTURE AS THE PROCEDURE GIVEN IN
[1]; HOWEVER, CUBIC INTERPOLATION (SEE [2]) IS USED INSTEAD OF
QUADRATIC INTERPOLATION TO APPROXIMATE THE MINIMIUM.
REFERENCES:
[1]: BRENT, R.P.
ALGORITHMS FOR MINIMIZATION WITHOUT DERIVATIVES. CH.5.
PRENTICE HALL, 1973.
[2]: DAVIDON, W.C.
VARIABLE METRIC METHODS FOR MINIMIZATION.
REP. A.N.L. 5990, 1959.
EXAMPLE OF USE:
THE FOLLOWING PROGRAM MAY BE USED TO CALCULATE THE MINIMUM OF THE
FUNCTION F(X) = SUM(((I * 2 - 5)/(X - I ** 2)) ** 2; I = 1 (1) 20)
ON THE INTERVAL [1.01,3.99] (SEE [1]).
"BEGIN"
"REAL" M, X, Y; "INTEGER" CNT;
"REAL" "PROCEDURE" F(X); "VALUE" X; "REAL" X;
"BEGIN" "INTEGER" I; "REAL" S;
S:= 0; "FOR" I:= 1 "STEP" 1 "UNTIL" 20 "DO"
S:= S + ((I * 2 - 5) / (X - I ** 2)) ** 2;
CNT:= CNT + 1; F:= S
"END" F;
"REAL" "PROCEDURE" DF(X); "VALUE" X; "REAL" X;
"BEGIN" "INTEGER" I; "REAL" S;
S:= 0; "FOR" I:= 1 "STEP" 1 "UNTIL" 20 "DO"
S:= S + (I * 2 - 5) ** 2 / (X - I ** 2) ** 3;
DF:= -S * 2
"END" DF;
"REAL" "PROCEDURE" TOL(X); "VALUE" X; "REAL" X;
TOL:= ABS(X) * "-7 + "-7;
X:= 1.01; Y:= 3.99; CNT:= 0;
M:= MININDER(X, Y, F(X), DF(X),TOL(X));
OUTPUT(61 ,"("4B,"("MINIMUM IS ")",N,/4B,
"("FOR X IS ")",N,/4B,
"("AND Y IS ")",N,/4B,
"("THE NUMBER OF FUNCTION EVALUATIONS NEEDED IS ")",2ZD,/")",
M, X, Y, CNT)
"END"
RESULTS:
MINIMUM IS +3.6766990169021"+000
FOR X IS +3.0229155250302"+000
AND Y IS +3.0229151227386"+000
THE NUMBER OF FUNCTION EVALUATIONS NEEDED IS 9
SOURCE TEXT(S):
"CODE" 34435;