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 signed distance from minimum *)
          VAR a: LONGREAL;   (* Left endpoint of domain; may be "-INF". *)
          VAR b: LONGREAL;   (* Right endpoint of domain; may be "+INF". *)
          check: CheckProc;  (* Acceptance criterion. *)
        );
        (*
          Looks for an approximate local minimum of a function "F"
          in the interval "[a__b]".

          Upon entry "x" must contain the initial guess for the
          minimum position (a finite value in "[a__b]"); "fx" 
          must contain the corresponding function value, and 
          "dfx" the corresponding derivative.
          
          The method will call "eval(u, fu, dfu)" to evaluate the
          function and (if necessary) its derivative at additional
          points "u" in "[a__b]".
 
          Upon exit, "fx" will contain the minimum function
          value seen so far, "x" will be the last point where
          that value occurred, and "dfx" will be the corresponding
          derivative.
          
          The variables "a" and "b" will be updated to a ``min-range''
          for this new "x": a sub-interval "[a1__b1]" of the original
          "[a__b]" that contains "x" and is guaranteed to contain at
          least one of the local minima of "F" in the original
          interval "[a__b]".
         
          If "check" is not NIL, the minimizer will call 
          "check(a1, b1, x, fx, Dfx, DDfx, q)" whenever a new
          point "x" is found where the function value is less
          than or equal to the previous values. At that point "[a1__b1]" 
          will be a min-range for "x".  In particular, the method
          will call "check(a, b, x, fx, Dfx, DDfx, q)" right
          upon entry.  For the meaning of the parameters 
          "Dfx", "DDfx", and "q", see below.
          
          The "minimize" method will stop searching when it finds a
          min-range of size "tol" or less; or when either "eval" or
          "check" return "TRUE".  More precisely, if "eval" returns
          "TRUE", the point given to it will be discarded; if "check"
          returns "TRUE", the point given to it will be the returned 
          as the best solution.
          
          The "dist" estimate is used to choose the initial probes
          around "x"; the details depend on the particular 
          instance of the minimizer.
          
          Derivatives
          -----------
          
          Some specific types of minimizer ignore the derivative
          information, and work only with the functon values.  When
          using such minimizers, the input value of the "dfx"
          parameter is irrelevant, the "eval" function is not required
          to compute the derivative, and the output value of "dfx" is
          meaningless.

          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, by divided differences.  (If
          the minimizer does not use derivative information, then
          "Dfx/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.
        *)

      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 fx, dfx: LONGREAL): BOOLEAN;
    (*
      Evaluates the function to minimize 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 the goal 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.