INTERFACE UniMin;

(*
  Defines a generic "univariate minimizer", an abstract
  object type encapsulating various algorithms that 
  minimize an arbitrary function of a single real variable,
  with or without using derivative information.
  
  Some specific instance of this type are defined in the interfaces
  "BrentUniMin" and "JSUniMin". 
  
  Created by J.Stolfi on 07/95.
*)

TYPE
  T = OBJECT 

      debug: BOOLEAN;  (* Asks for diagnostic output on stderr *)

    METHODS
  
      minimize(
          eval: EvalProc;                 (* Function to minimize. *)
          VAR x: LONGREAL;                (* In: starting guess; out: local min *)
          VAR fx: LONGREAL;               (* In/out: function value at "x". *)
          VAR dfx: LONGREAL;              (* In/out: derivative at "x". *)
          tol: LONGREAL;                  (* Desired uncertainty of result. *)
          dist: LONGREAL;                 (* Estimated distance from minimum *)
          a: LONGREAL := FIRST(LONGREAL); (* Left endpoint of domain. *)
          b: LONGREAL := LAST(LONGREAL);  (* Right endpoint of domain. *)
          check: CheckProc;               (* Acceptance criterion. *)
        );
        (*
          Looks for an approximate local minimum of a function "f"
          in the interval "[a__b]".

          The method will stop searching when it determines that there is
          a local minimum of "f" on some interval of size "tol" or less
          containing "x"; or when "check" returns "TRUE" (see below).
          
          Upon entry "x" must contain the initial guess for the
          minimum position, "fx" the corresponding function value, and
          "dfx" the corresponding derivative.  The method will call
          "eval(u, fu, dfu)" to evaluate the function and its
          derivative at additional points "u" in "[a _ b]".
          
          If "check" is not NIL, the minimizer will call "check(lo,
          hi, x, fx, dfx, ddfx, q)" whenever a new point "x" is found
          where the function value is less than the previous values.
          At that point "[lo _ hi]" ins a sub-interval of "[a _ b]"
          that is known to contain a local minimum of "f".
          
          The "check" procedure is given also the first and second
          derivatives "dfx/q" and "ddfx/q" of "f" at "x"; the
          latter being estimated numerically.  (If the minimizer does
          not use derivative information, then "df/q" will be estimated,
          too.) The scaling factor "q" is never negative; but may be zero,
          meaning that the derivatives could not be estimated reliably.
          
          Some specific types of minimizer ignore the derivative
          information, and work only with the functon values.  When
          using such minimizers, the input value of "dfx" is
          irrelevant, the "eval" function need not compute the
          derivative, and the output value of "dfx" is meaningless.

          The "dist" estimate is used to choose the initial probes
          around "x"; the details depend on the particular 
          instance of the minimizer.
        *)

      needsDerivative(): BOOLEAN;
        (*
          Returns TRUE iff this particular minimizer needs/returns
          the derivative of the function.  When this method
          returns FALSE, the "dfx" parameters of "minimize"
          and "eval" are ignored by the minimizer, and should
          not be trusted by the client. *)
      
      name(): TEXT;
        (*
          Returns the minimizer's name, possibly with
          any internal parameters. *)
    END;
  
TYPE
  EvalProc = PROCEDURE (x: LONGREAL; VAR f, df: LONGREAL);
    (*
      Evaluates the function to minimizer and, if necessary,
      its derivative. *)
  
TYPE
  CheckProc = PROCEDURE (lo, hi: LONGREAL; x, fx, dfx, ddfx, q: LONGREAL): BOOLEAN;
    (*
      Client procedure called by the "minimize" method to decide
      whether to continue the search. *)

PROCEDURE ComputeDerivatives(
    u, fu, v, fv, x, fx: LONGREAL; 
    VAR dfx, ddfx, q: LONGREAL;
  );
  (*
    Computes estimates "dfx/q" and "ddfx/q" for the first and second
    derivatives of a function "f" at "x", by fitting 
    a quadratic through the three points "(u, fu)", "(v, fv)",
    and "(x, fx)".  
    
    The scaling factor "q" will be positive if all three arguments
    "u", "v", "w" are sufficiently distinct,and zero otherwise. *)

END UniMin.