Thread Subject: automatic differentiation

I am trying to solve a system of nonlinear equations, and I
am trying to obtain its Jacobian with automatic
differentiation tools. I tried Tapenade on my fortran code
(which I later mex and try to solve the system with fsolve),
but there seems to be a problem. Inside my code that gives
the values of the system, I have a call to "zeroin", which
is a single-equation solver.
In other words, I need to solve a single equation inside a
routine that gives the values for the non-linear system I
want to ultimately solve. The arguments of the non-linear
system appear as parameters in that single equation. Later,
I use the solution to that single equation to obtain some of
the parameters in my non-linear system.
Clearly, the arguments of the system have an effect on the
solution of the single equation with zeroin (since they are
parameters in that equation), which then have an effect on
the value of the system. But Tapenade seems to ignore that
effect. Is there any remedy for this? I am new to AD, so I
don't know what it can and what it cannot do.
Thank you.

 Sergei

Hello Sergei:
As far as I understood, it appears that your post has little
to do with matlab but with Tapenade. Let us know if I am wrong.
Regarding your problem: do you have access to the zeroin
routines? If not, you have to specify by hand to Tapenade
how each returned variable partial derivative relates (or
not) with the input parameters calling. That assummes that
you at least has access to the algorithm used at zeroin.
If you have access to the zeroin routines, be shure to
include them in the call to Tapenade.
Regards
Carlos

"carlos lopez" <clv2clv_00000000_@adinet.com.uy> wrote in
message <g1eq6p$5vj$1@fred.mathworks.com>...
> Hello Sergei:
> As far as I understood, it appears that your post has little
> to do with matlab but with Tapenade. Let us know if I am
wrong.
> Regarding your problem: do you have access to the zeroin
> routines? If not, you have to specify by hand to Tapenade
> how each returned variable partial derivative relates (or
> not) with the input parameters calling. That assummes that
> you at least has access to the algorithm used at zeroin.
> If you have access to the zeroin routines, be shure to
> include them in the call to Tapenade.
> Regards
> Carlos
>
 Hi Carlos,
I mex my fortran code that gives the values of my system,
and then try to solve it with matlab's fsolve. But you are
right, my question is not directly related to matlab. I use
Tapenade only because I stumbled upon it. I am not sure if
there are good AD tools for matlab?
I do have access to "zeroin", and I give it to Tapenade. But
since it solves the single equation by some combination of
bisection and some other methods, I suspect that Tapenade
cannot tell how the solution changes with changes in the
arguments.
How can I tell Tapenade how each returned variable partial
derivative relates with the input parameters?
Thank you.

 Sergei

"Sergei " <sstepanchuk@gmail.com> wrote in message
<g1eqv6$apd$1@fred.mathworks.com>...
> Hi Carlos,
> I mex my fortran code that gives the values of my system,
> and then try to solve it with matlab's fsolve. But you are
> right, my question is not directly related to matlab. I use
> Tapenade only because I stumbled upon it. I am not sure if
> there are good AD tools for matlab?
I am familiar with ADMIT/ADMAT, but I believe that it is not
easily available on the Web. Contact me at clv2clv at
adinet.com.uy for a copy. However, you might want to solve
all the stuff within the FORTRAN environment
> I do have access to "zeroin", and I give it to Tapenade. But
> since it solves the single equation by some combination of
> bisection and some other methods, I suspect that Tapenade
> cannot tell how the solution changes with changes in the
> arguments.
> How can I tell Tapenade how each returned variable partial
> derivative relates with the input parameters?
I have never did myself, but how to explictly set the
derivatives is explained somewhere in the tapenade website.
It is intended for routines which you have not access to the
source, so you specify by hand the derivatives. However, if
you cannot figure out which is the relationship both (you
and Tapenade) are in trouble ;-).
If the function to be solved by zeroin is smooth enough,
maybe you can perform one step of another method (like
Newton-Raphson) once zeroin gives back the solution.
Anyway, you should request an opinion from a Tapenade's
newsgroup (if there is any)
Regards
Carlos

I cannot help you with the specific question, but automatic
differentiation is rarely efficient.

If you have big program and lazy to go through it, then try
to locate parts that is tricky to derive (such as the
iterative solver). Use your automatic tool for the rest of
your program, than do manual differentiation for the tricky
part, then combine both together.

Full manual differentiation gives always better result for
me, because I ultimately know how the code behaves.

Bruno

"Bruno Luong" <b.luong@fogale.fr> wrote in message
<g1f8am$983$1@fred.mathworks.com>...
> I cannot help you with the specific question, but automatic
> differentiation is rarely efficient.
>
> If you have big program and lazy to go through it, then try
> to locate parts that is tricky to derive (such as the
> iterative solver). Use your automatic tool for the rest of
> your program, than do manual differentiation for the tricky
> part, then combine both together.
>
> Full manual differentiation gives always better result for
> me, because I ultimately know how the code behaves.
>
> Bruno

 Thanks for all the comments,
I am trying to do exactly that now. I haven't managed to get
 explicitly the derivative to the part that I get by
"zeroin" (by the way, its just a fortran analog of matlab's
fzero, as I understand it), so I do that by finite
differences. But I do the rest using AD tool (tapenade for
now, maybe I'll try something else later).
I was also thinking about trying to get that derivative
explicitly using implicit function theorem (the solution has
to satisfy a single equation, like f(x;arg) = 0, where arg
are the arguments of my nonlinear system I want to solve,
they appear as parameters in that single equation, while x
is the solution of that equation given the values of arg's;
so I thought I could get dx/darg using IFT). Does that sound
like a good idea?
By the way, Bruno, why do you say that AD is not efficient?
I think it is what all those people that develop solvers
like knitro, snopt etc. use? Also, it is part of tomlab,
which, I thought, is state of the art?
I have also read recently about some sort of a "complex
variables" approach to finite differencing. The claim was
that it allows one to get rid of some sort of a cancellation
error in real finite differences. Does anyone have any
comments about that?
Also, does anyone have any comments about choosing the
"optimal" delta for finite differences?

 Sergei

Yes, if your zeroing solver provides accurate solution, then
implicite theorem is the way to go.

For the delta, I have not aware any rigorous and reliable
method for choosing it. But most of the time 1e-6 x expected
variation of the parameter should work OK.

Doing hand differentiation, one can apply direct or backward
substitution when it needs. Some compromise about memory
saving and computation speed must be made. Usually this kind
of decision is better made by a human programmer than the
automatic tool.

But automatic tool is so convenient, and it works OK 90%.
Just the 10% of the rest that needs hand differentiation.
This is spoke from experience only.

Bruno

You can use the complex step option when using num diff in TOMLAB (see
the main manual for the options). If you want to use AD all your code
has to be Matlab code, MEX code is not supported.

Best wishes, Marcus
http://matlabad.com/

take a look here:
http://www.autodiff.org/?module=Tools&language=MATLAB

I use ADiMat
(http://www.sc.rwth-aachen.de/vehreschild/adimat/index.html); the
documentation provided is large and detailed but sometimes
it is a bit difficult to start with this program. However
the author Andre Vehreschild answered promptly to my emails
and, by the way, the program is very good.

"Sergei " <sstepanchuk@gmail.com> wrote in message
<g1epam$ej$1@fred.mathworks.com>...
> I am trying to solve a system of nonlinear equations, and
I
> am trying to obtain its Jacobian with automatic
> differentiation tools. I tried Tapenade on my fortran code
> (which I later mex and try to solve the system with
fsolve),
> but there seems to be a problem. Inside my code that gives
> the values of the system, I have a call to "zeroin", which
> is a single-equation solver.
> In other words, I need to solve a single equation inside a
> routine that gives the values for the non-linear system I
> want to ultimately solve. The arguments of the non-linear
> system appear as parameters in that single equation.
Later,
> I use the solution to that single equation to obtain some
of
> the parameters in my non-linear system.
> Clearly, the arguments of the system have an effect on the
> solution of the single equation with zeroin (since they
are
> parameters in that equation), which then have an effect on
> the value of the system. But Tapenade seems to ignore that
> effect. Is there any remedy for this? I am new to AD, so I
> don't know what it can and what it cannot do.
> Thank you.
>
> Sergei


I recollect using something from Netlib (www.netlib.org) in
the past and I run a quick search that gave these results:

Query "automatic differentiation" found 6 matches.
1. bib/all_brec.readme
  for: Automatic Differentiation -- notes on bibliography
  by: George Corliss
  Score: 100%


2. bib/all_brec.bib
  for: Automatic Differentiation database
  by: George Corliss
  size: 279 kB
  Score: 100%


3. bibnet/subjects/all_brec.bib
  for: automatic differentiation
  size: 271 kB
  Score: 100%


4. jakef
  for: automatic differentiation a precompiler that
analyses a given Fortran77 source code for the evaluation
of a scalar or vector function and then generates an
expanded Fortran subroutine that simultaneously evaluates
the gradient or Jacobian respectively. For scalar functions
the ratio between the run-time of the resulting gradient
routine and that of the original evaluation routine is
never greater than a fixed bound of about five. The storage
requirement may be considerable as it is also proportional
to the run-time of the original routine. Since no
differencing is done the partial derivative values obtained
are exact up to round-off errors.
  by: A. Griewank, Argonne National Laboratory
<griewank@mcs.anl.gov> 12/1/88.
  master: ornl.gov
  Score: 100%


5. toms/746
  ref: TOMS 21,3 (Sep 1995) 233
  alg: pcomp
  for: fortran code for automatic differentiation
  by: M. Dobmann, M. Liepelt and K. Schittkowski
  size: 284 kB
  Score: 100%


6. toms/755
  ref: TOMS 22,2 (Jun 1996) 131
  for: {ADOL-C}: A Package for the Automatic
Differentiation of Algorithms Written in {C/C++}
  by: Griewank, A., Juedes, D. and Utke, J.
  size: 484 kB
  Score: 100%



I believe I use Jakef, but I can't remember if or how a
problem like yours was addressed. Also, it's pretty old
stuff and runs on F77.
Hope it may help, anyway.
Riccardo