Re: Passing Parameters by Reference

[Doug Rogers <rogers@...>]

On Monday 14 June 2004 11:39, Virgil Smith wrote:

> function Optimize(f, v, min, max) do
>    -- f is the function to be optimized (minimized)
>    -- v is the variable quantity, i.e. the position
>    --   along the "search" axis
>    -- min is a lower boundary for v
>    -- max is an upper boundary for v
> ......
> end

Hi Virgil. What do you use for the error function?

I did a minimization project in Ada (83!) a few years back using 
Levenberg-Marquardt minimization. While Ada does indeed provide for passing 
values by reference, I have to agree with the peanut gallery and say that I 
don't think that's the fundamental problem here.

With Ada generic packages it is possible to wrap all the state information 
into a single package and have the function being minimized gain local access 
to all the state information. I had default generic partial derivative 
function, but for one of my models I required a special-purpose one. It was 
very codey; it would be very simple and concise in Lua.

This could be done by wrapping the entire problem into a single table that 
holds not just the function but also its nonvariant state information. The 
variant (v) would then be perturbed according to whatever method you are 
using - L-M or some form of steepest descent, whatever.

The problem would be speed. In my L-M minimization, the minimizer itself did 
not consume too much CPU time. At most it performed a few 8x8 matrix 
inversions (I linked in some downloaded Ada code to do Singular Value 
Decomposition). The function(s) being minimized consumed the vast majority of 
the CPU time.

In Lua, though, each reference to state information comes at the cost of a 
table lookup. This cost is small compared to other scripting languages, but 
it would be huge in number-crunching algorithms in Lua. You simply cannot 
avoid that without butchering the code so much that you might as well call it 
a different language.

It may be that -- heaven forbid! -- Lua is not the appropriate language for 
your friend's problem. I would sooner cut off my own fingers than type the 
stuff that your friend is typing! :)

But being a fan of Lua, I guess I'd recommend finding ways to hide the 
time-critical calculations in C code behind proxy tables/userdata. It's not 
as much work as you might think. It took me a few days to get up to speed, 
but now I feel very comfortable writing mixed C/Lua applications. I was 
surprised how easily it all came together.

For example, you may be able to write the minimizer completely in Lua. Then 
use a wrapper to prep the data to go into C, FORTRAN, whatever, to do the 
real work of running the function being minimized. This would allow your 
friend to sit at an interpreter and inspect the results, then make trial runs 
repeatedly. But any changes to the function would have to happen in C.

Or you may find it more useful to provide C functions for vector and matrix 
calculations. Then you could write the forward function entirely in Lua. This 
would require more legwork up front, but would be time well spent because 
such routines are very general purpose and can serve you for lots of 
projects. I've written implementations of Vector and Matrix, below, but right 
now it's all in Lua, so not-so-fast.

-- Vector module provides length(), dot(), outer(), '+',  '-', any of which
--   could be optimized in C. The elements of the vector could be completely
--   hidden behind (light)userdata, requiring a single table lookup per
--   operation on the vector (rather than the value).
-- Vector.norm2 = function(v) return math.sqrt(v:dot(v)) end
-- Matrix module provides similar.
-- Matrix.numerical_partial(f, delta) return function... end

function minimize(problem, vstart)
-- 'problem' is table containing:
--    :f(v)     function taking Vector object, returning Vector
--    :dfdv(v)  partial derivative function taking Vector returning Matrix
--    .vmin     [optional] lower bounds for elements of v, Vector
--    .vmax     [optional] upper bounds for elements of v, Vector
--    .fmin     [optional] lower bounds for return values of f, Vector
--    .fmax     [optional] upper bounds for return values of f, Vector
-- Other elements of 'problem' can be set as desired.
-- Parameter
--    vstart    initial value for v, a Vector object
-- Returns a table with the best fit data, norm, and function results.
   local v = problem.vstart:copy()
   local fstart = problem:f(v)
   local best = {}
   best.norm = fstart:norm2()
   best.v = vstart
   best.f = fstart

   while (some search-technique-specific criteria are still met)
      pick new value for v
      recalculate error function
   end

   return best
end   -- minimize()

fxy = function(x, y) return (x * x * y) - (2 * x * y) - (y * y) end
fv = function(f, v) return f(v[1], v[2]) end
p = {
   f=fv,
   dfdv=Matrix.numerical_partial(fv, 0.001),
   vmin={ -1.0, -1.0 },
   vmax={ 20.0, 20.0 },
}

best = minimize(p, { 8.2, 2.5 })
print(best.v:tostring())

I *like* the idea of passing a table to the minimizer/optimizer. I think it 
provides a great way to distinguish between what is and what is not part of 
the problem space. The method (granted, of smaller scope) of using multiple 
return values doesn't always lead to more readable code.

But Lua is flexible enough to find a way that is pleasing to your own eye.

Doug

-- 
--__-__-____------_--_-_-_-___-___-____-_--_-___--____
Doug Rogers - ICI - V:703.893.2007x220 www.innocon.com
-_-_--_------____-_-_-___-_--___-_-___-_-_---_--_-__-_