octave-dev

[OctDev] Specification for nonlinear optim. front-end

[Etienne G. <et...@an...>]

  Hello,

here is a possible specification for a front-end to unconstrained
nonlinear optimization functions. The current "optimize()" function
does more or less this already, but only has the Nelder-Mead,
conjugate gradient and Levenberg-Marquardt ("D2" below) algorithms.


Synopsis of a front-end for optimization
----------------------------------------

  [x_best,v_best,...] = minimize (func, start_point, ...)

  start_point is the starting point for the iterative minimization
              method.

              If func takes more than one argument, start_point may be
              a list. By default, func will be minimized with respect
              to the first argument, but any other argument may be
              specified with the "narg" option below.

Implemented methods and their applicability
-------------------------------------------

  +--------------------+---+-------+-------+------+
  |                    |   | Deriv |       |      |
  | METHOD             |Dim| Order | Domain| Func |
  +--------------------+---+-------+-------+------+
  | Newton-Ralphson    | 1 |   2   |  all  |  C2  |
  | Nelder-Mead        | N |   0   |  all  | cont |
  | BFGS               | N |   1   |  all  |  C1  |
  | Conjugate Gradient | N |   1   |  all  |  C1  |
  | DFP                | N |   1   |  all  |  C1  |
  | D2                 | N |   2   |  all  |  C2  |
  +--------------------+---+-------+-------+------+

Options indication 1st or second differential
---------------------------------------------

"dfunc" dfuncname
  => Use an algorithm that uses the differential.
     Assumes the differential df can be calculated with 
    
       df = dfuncname (x)

"d2func" dfuncname
  => Use an algorithm that uses the 1st and 2nd differentials.
     Assumes the function value f, differentials df and d2f can be
     calculated with  
    
       [f,d2,d2f] = d2funcname (x)

"ndif"
  => Use numerical differentiation.

Options indicating the algorithm
--------------------------------

newton_ralphson       (nr)
  => Dim == 1

nelder_mead           (nm)

bfgs
  => Need Dfunc

cong_grad             (cg)
  => Need Dfunc

dfp
  => Need Dfunc

levenberg_marquardt   (lm)
  => Need D2func

-- Default :
   If    Dfunc  is given : Method == bfgs, cg or dfp
   Elsif D2func is given
     If Dim == 1 : Method == nr
     Else        : Method == lm

Options controling termination
------------------------------

  Option    Description                   Applicable methods  
  -----------------------------------------------------------
  ftol h    Absolute function improvement (nm, dfp, bfgs, lm)
  vtol h    Volume   of simplex	          (nm)
  rtol h    Radius of simplex		  (nm)
  dtol h    Amplitude of derivative	  (dfp, bfgs, lm)
  xtol h    Amplitude of step		  (nm, dfp, bfgs, lm)

Other options
-------------
narg n               Indicate which argument with respect to which
                     func is optimized (when it takes multiple
                     arguments).

step h               Indicate the initial step size (not for method
                     that uses 2nd diff)

maxev n          Maximum number of function evaluations

verbose          Show status during algorithm run

shorthand        Do not perform the optimization, but return the name
                 of the backend function and the options that are
                 passed to it. The backend can then be called
                 directly, with little overhead.

Checks that should be done on the coherence of the input 
--------------------------------------------------------

If Dfunc  is needed, but not specified : do numerical differentiation

If D2func is needed, but not specified :

  If Dim == 1 : do numerical differentiation
  Else        : error (not yet implemented)

If Dim == 1 but size Xstart != 1 : error

If termination criterion is used w/ inappropriate method : error

If Dfunc or  D2func are specified but not required by method : warn

If both Dfunc and D2func are specified : warn



-- 
Etienne Grossmann ------ http://www.isr.ist.utl.pt/~etienne

Re: [OctDev] Specification for nonlinear optim. front-end

[Ben S. <bs...@la...>]

Hi Etienne,

This is great.  Thank you for writing it up.  I have a few comments.  

I think the "ndif" option should be replaced with an "order" option. 
-----------------------------------------------------------------------
order -> specify 0,1,2 and get the default method for that order.  

ndif -> If we add the order option this option is superfluous.  The logic for 
checking coherence of the arguments can take care of the case where a method 
is explicitly chosen and where an order is chosen.  

I suggest this mainly becuase it seems more intuitive to me.  What do you 
think?  

Comments on Order 1 methods
-----------------------------------------------------------------------
The interface for bfgs and dfp are not the same as cg_min.  I think that they 
should be changed to match.  I also happen to think that cg_min has a better 
intefrace than bfgs and dfp.   At the very least we need to make a way to 
pass variables through to the function being minimized which bfgs and dfp 
currently don't allow.   

You did not suggest a default for the order one methods.  I think bfgs should 
be the default.  When faced with multiple options for a problem we should 
choose the one that will probably be the fastest for most problems.  

Do we need/want to maintain dfp?  I wrote it becuase we used both in a class 
I was taking.   dfp and bfgs are essentially the same.  That is they try to 
construct the inverse hessian from gradients.  I am not sure it adds any 
thing except work. Here is a quote from  Linear and Nonlinear Programming by 
David Luenberger talking about the BFGS method.  "Numerical experiments have 
repeatedly indicated that [BFGS] performance is superior to that of the DFP 
formula, for this reason [BFGS] is now generally preferred."   My feeling is 
we should toss it unless someone has a reason to keep it.  

Shorthand option
-------------------------------------------------------
I had not thought of this.  I think it is a particularly nice feature that is 
not available for most analysis packages.  It is always a good idea to make 
things as transparent as possible.  


On Saturday 16 March 2002 10:02 am, Etienne Grossmann wrote:
>   Hello,
>
> here is a possible specification for a front-end to unconstrained
> nonlinear optimization functions. The current "optimize()" function
> does more or less this already, but only has the Nelder-Mead,
> conjugate gradient and Levenberg-Marquardt ("D2" below) algorithms.
>
>
> Synopsis of a front-end for optimization
> ----------------------------------------
>
>   [x_best,v_best,...] = minimize (func, start_point, ...)
>
>   start_point is the starting point for the iterative minimization
>               method.
>
>               If func takes more than one argument, start_point may be
>               a list. By default, func will be minimized with respect
>               to the first argument, but any other argument may be
>               specified with the "narg" option below.
>
> Implemented methods and their applicability
> -------------------------------------------
>
>   +--------------------+---+-------+-------+------+
>
>   |                    |   | Deriv |       |      |
>   |
>   | METHOD             |Dim| Order | Domain| Func |
>
>   +--------------------+---+-------+-------+------+
>
>   | Newton-Ralphson    | 1 |   2   |  all  |  C2  |
>   | Nelder-Mead        | N |   0   |  all  | cont |
>   | BFGS               | N |   1   |  all  |  C1  |
>   | Conjugate Gradient | N |   1   |  all  |  C1  |
>   | DFP                | N |   1   |  all  |  C1  |
>   | D2                 | N |   2   |  all  |  C2  |
>
>   +--------------------+---+-------+-------+------+
>
> Options indication 1st or second differential
> ---------------------------------------------
>
> "dfunc" dfuncname
>   => Use an algorithm that uses the differential.
>      Assumes the differential df can be calculated with
>
>        df = dfuncname (x)
>
> "d2func" dfuncname
>   => Use an algorithm that uses the 1st and 2nd differentials.
>      Assumes the function value f, differentials df and d2f can be
>      calculated with
>
>        [f,d2,d2f] = d2funcname (x)
>
> "ndif"
>   => Use numerical differentiation.
>
> Options indicating the algorithm
> --------------------------------
>
> newton_ralphson       (nr)
>   => Dim == 1
>
> nelder_mead           (nm)
>
> bfgs
>   => Need Dfunc
>
> cong_grad             (cg)
>   => Need Dfunc
>
> dfp
>   => Need Dfunc
>
> levenberg_marquardt   (lm)
>   => Need D2func
>
> -- Default :
>    If    Dfunc  is given : Method == bfgs, cg or dfp
>    Elsif D2func is given
>      If Dim == 1 : Method == nr
>      Else        : Method == lm
>
> Options controling termination
> ------------------------------
>
>   Option    Description                   Applicable methods
>   -----------------------------------------------------------
>   ftol h    Absolute function improvement (nm, dfp, bfgs, lm)
>   vtol h    Volume   of simplex	          (nm)
>   rtol h    Radius of simplex		  (nm)
>   dtol h    Amplitude of derivative	  (dfp, bfgs, lm)
>   xtol h    Amplitude of step		  (nm, dfp, bfgs, lm)
>
> Other options
> -------------
> narg n               Indicate which argument with respect to which
>                      func is optimized (when it takes multiple
>                      arguments).
>
> step h               Indicate the initial step size (not for method
>                      that uses 2nd diff)
>
> maxev n          Maximum number of function evaluations
>
> verbose          Show status during algorithm run
>
> shorthand        Do not perform the optimization, but return the name
>                  of the backend function and the options that are
>                  passed to it. The backend can then be called
>                  directly, with little overhead.
>
> Checks that should be done on the coherence of the input
> --------------------------------------------------------
>
> If Dfunc  is needed, but not specified : do numerical differentiation
>
> If D2func is needed, but not specified :
>
>   If Dim == 1 : do numerical differentiation
>   Else        : error (not yet implemented)
>
> If Dim == 1 but size Xstart != 1 : error
>
> If termination criterion is used w/ inappropriate method : error
>
> If Dfunc or  D2func are specified but not required by method : warn
>
> If both Dfunc and D2func are specified : warn

-- 
Ben Sapp                         Los Alamos National Laboratory
email: <mailto:bs...@la...>   Phone: (505)667-3277
Fax:   (505)665-7920             URL:   http://www.neutrino.lanl.gov/
--