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 f: Value;        (* In/out: function value at "x" *)
          VAR g: Gradient;     (* In/out: gradient of "f" at "x" *)
          dist: Length;        (* Guessed distance from optimum *)
          flat: Slope;         (* Stopping criterion *)
          tol: Length;         (* Guessed radius of optimum region *)
          maxEvals: CARDINAL := LAST(CARDINAL); (* Max number of "eval"s allowed *)
          trace: TraceProc := NIL;   (* A path reporting procedure *)
        );
      (*
        Finds a local minimum of a function "F" starting at "x".
        Returns the minimum position in "x", and its function value in "f".
        
        The function "F" is computed by calling "eval(x, f, g)", where
        "x" is the current argument vector; the "eval" procedure
        should return in "f" the function value "F(x)", and in "g" its
        gradient at "x".
        
        The search will stop when the slope of "F" becomes "flat" or less, 
        or after "maxEvals" calls to "eval" --- whichever happens
        first. (However, some algorithms may fail to test these conditions
        after certain calls to "eval".)
        
        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.
        
        If the "trace" procedure is not NIL, the optimizer will
        call "trace(x, f, g)" at certain 'interesting points'
        along the process, where 
        |
        |   "x" is an argument vector, 
        |   "f" is the corresponding function value "F(x)",
        |   "g" is the gradient at "x"
        |
        The definition of 'interesting point' is instance-specific.

        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;
        (*
          Returns TRUE iff this particular minimizer needs/returns
          the gradient of the function.  When this method
          returns FALSE, all "Gradient" parameters are ignored
          by the "minimize" method, and should not be trusted
          by the client. *)
      
      name(): TEXT;
        (*
          Returns the minimizer's name, possibly with
          any internal parameters. *)

    END;

TYPE
  EvalProc = PROCEDURE(READONLY x: Point; VAR f: Value; VAR g: Gradient);
    (*
      Called by the integrator to compute the function value ("f") 
      and its gradient ("g") at the point "x". *)
      
  TraceProc = PROCEDURE(READONLY x: Point; f: Value; READONLY g: Gradient);
    (*
      Called by the integrator to report an 'interesting' point
      "x" along the path. *)

END Minimizer.