INTERFACE Minimizer;

(*
  Defines a generic "minimizer" object, an abstract data type
  for encapsulating various algorithms that 
  minimize an arbitrary function of several real variables.
  
  Some specific instances of this type are defined in the interfaces
  "GradMinimizer", "CoordMinimizer", etc. 
  
  Created by J.Stolfi on 07/95.
*)

TYPE
  Coord = LONGREAL;          (* Point coordinates *)
  Length = LONGREAL;         (* Point distances *)
  Value = LONGREAL;          (* Function values *)
  Slope = LONGREAL;          (* Positional derivative of function *)
  Point = ARRAY OF Coord;    (* Point in parameter sace *)
  Gradient = ARRAY OF Slope; (* Gradient of function *)
  Vector = ARRAY OF Coord;   (* Difference of two points *)

TYPE
  T = OBJECT 
  
      debug: BOOLEAN;   (* Asks for diagnostic output on "stderr" *)
  
    METHODS

      setSize(n: CARDINAL): T;
        (* 
          Allocates internal tables for minimization of an
          "n"-argument function. Should be called before
          "minimize". *)
          
      minimize(
          eval: EvalProc;      (* Evaluates the goal function. *)
          VAR x: Point;        (* In: initial guess, out: minimum point. *) 
          VAR fx: Value;       (* In/out: function value at "x" *)
          VAR dfx: Gradient;   (* In/out: gradient of "F" at "x" *)
          dist: Length;        (* Guessed distance from optimum *)
          tol: Length;         (* Guessed radius of optimum region *)
          check: CheckProc;    (* Acceptance test *)
        );
      (*
        Finds a local minimum of a function "F" starting at "x".
        
        Upon entry, "x" must be an initial guess for the minimum,
        "fx" must be the value of "F" at "x", and "dfx" must be 
        the gradient of "F" at "x" (if the integrator requires it; see
        "needsGradient" below).
        
        Upon exit, "fx" will be the smallest function value ever seen,
        "x" will be the last point where "F" was found to have value "fx",
        and "dfx" will be the correponding gradient (if available).
        
        The method will usually call "eval(u, fu, dfu)" to evaluate
        the function value "fu" (and its gradient "dfu", if needed) at
        other points "u".
        
        The method will call "check(x, fx, dfx)" whenever it finds a 
        point "x" where the function value "fx" is less than or equal to
        those all previously seen values of "fx". (In particular, it will
        call "check" for the initial point.)
        
        The search will continue until some call to "eval" or "check"
        returns "TRUE".  The "minimize" method will then return, with
        "x" and "fx" set to the best point found among the initial
        guess and all points for which "eval" returned FALSE.  In case
        of ties, the most recent probe is returned. Note that if
        "eval" returns TRUE, its arguments are discarded; whereas, if
        "check" returns true, its arguments are returned as the
        result.
        
        The client must provide a rough guess "dist" of the
        distance between the starting point and the optimum set (the
        region where the gradient is less than "flat"), and an upper
        bound "tol" for the size of the optimum set, across its
        smallest dimension.  These two parameters are used to select
        internal paramters such as step sizes, the variance of random
        probes, etc.  The details depend on the specific optimizer.
        
        Specific subtypes of "T" may expand or modify this basic description,
        for instance by introducing additional stopping criteria
        or attaching special semantics to "eval".
      *)

      needsGradient(): BOOLEAN;
        (*
          If "needsGradient()" returns TRUE, the minimizer
          will use the gradient "dfx" of the function, as given to 
          "minimize" and returned by the "eval" procedure.
          In that case, "minimize" will properly set "dfx"
          before calling "check" or exiting.
          
          If "needsGradient()=FALSE", the minimizer
          does not use any gradient information; moreover,
          the "dfx" parameter should not be used by "check", 
          and is undefined upon exit. *)
      
      name(): TEXT;
        (*
          Returns the minimizer's name, possibly with
          any internal parameters. *)

    END;

TYPE
  EvalProc = PROCEDURE(READONLY x: Point; VAR fx: Value; VAR dfx: Gradient): BOOLEAN;
    (*
      Called by the minimizer to compute the function value "fx" at the point "x".
      If the minimizer's "needsGradient()" is true, the procedure should also
      compute the gradient "dfx" of the function at "x".  
      
      If the "EvalProc" procedure returns TRUE, the returned "fx" and "gx" are ignored,
      the search is ended, and the best point found previously is returned. *)
      
  CheckProc = PROCEDURE(READONLY x: Point; fx: Value; READONLY dfx: Gradient): BOOLEAN;
    (*
      Called by the minimizer to report a new historical minimum "x".
      The procedure should return "TRUE" to stop the optimization
      and return "x" as the result, "FALSE" to continue searching. *)

END Minimizer.