Author 
Topic: Find optimal function (Read 3881 times) 

BNC
Uberpuzzler
Gender:
Posts: 1732


Find optimal function
« on: May 23^{rd}, 2003, 1:41am » 
Quote Modify

HI gang, I have a nasty optimization problem on my hands. I need to find a function a(x) that solves this: Int(inf, inf, a(x)b(x,y))dx = f(y) where b and f are known. My first solution was to use numeric calculation, using a and f as 1D vectors and B as a matrix: B*a=f and then a=B^{1}f Problem is... B is not invertable. This is probably a common case, but it's my 1st encounter with it. Any suggestions?


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13101


Re: Find optimal function
« Reply #1 on: May 23^{rd}, 2003, 1:39pm » 
Quote Modify

doing it numerically B doesn't have to be invertable.. I'll look it up tomorrow if noone else gives the answer first.. (It's late and I have a programming contest tomorrow, so must sleep..)


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



BNC
Uberpuzzler
Gender:
Posts: 1732


Re: Find optimal function
« Reply #2 on: May 25^{th}, 2003, 12:25am » 
Quote Modify

Hi towr, I hope your contest went well... 10x for looking into it. The only thing I came up with so far is the use of simulated anealing, but as my vectors are very long, I'm not happy about it.


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13101


Re: Find optimal function
« Reply #3 on: May 25^{th}, 2003, 2:56am » 
Quote Modify

mew, it didn't go too bad, but not too good either.. we were 6 or 7 out of 12.. With 3 out of 9 assignments completed (vs 8/9 from the winners) On the other hand we had little to no preperation, and the question were somewhat illphrased imo.. (They make a story around them, obscuring mathematical problems with realworld complications.) Anyway, about the problem at hand.. There are ways to solve A*b = 0 given A and to make B*a=f into A*b=0 can be done like this so you have this can be solved iteratively with 'newtons method for nonlinear systems' G(x) = x  J(x)^{1}F(x) where J(x) is the Jacobian matrix of F(x) (the second image) here's matlab code for it (some dutch) f is the function F(x) jacf is the jacobian of F(x) x0 is the vector you take as first approximation (it usually needs to be somewhere in the vicinity of where you need to be (just try it several times) tol is the tolerance, how big of an error can be made 'afdruk' = 'print', 1 will print intermediate results varargin, can be extra arguments for f function nulpunt=vnewton(f,jacf,x0,tol,afdruk,varargin) fx = feval(f, x0, varargin{:}); jx = feval(jacf, x0, varargin{:}); y = jx^1*fx; i =0; while norm(y,inf) > tol if afdruk ~=0 fprintf('it:%i nulpunt:[ ', i); fprintf('%3.3e ', x0); fprintf('] fout: %3.3e\n', norm(y,inf)); end x0 = x0 + y; fx = feval(f, x0, varargin{:}); jx = feval(jacf, x0, varargin{:}); y = jx^1*fx; i = i+1; end if afdruk ~=0 fprintf('it:%i nulpunt:[ ', i); fprintf('%3.3e ', x0); fprintf('] fout: %3.3e\n', norm(y)); end nulpunt = x0; % I think this should solve the matrix problem.. I'm not sure how well it'll solve the original problem though.. (you may need a very, very large vector to get enough accuracy) (basicly it's sort of gradiant decent instead of simulated annealing)

« Last Edit: May 25^{th}, 2003, 3:03am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



BNC
Uberpuzzler
Gender:
Posts: 1732


Re: Find optimal function
« Reply #4 on: May 25^{th}, 2003, 6:25am » 
Quote Modify

Thanks towr, I'll give it a go, and let you know how it went.


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13101


Re: Find optimal function
« Reply #5 on: May 25^{th}, 2003, 7:00am » 
Quote Modify

If it doesn't work I may have something else somewhere.. Though I can't say I fully understand that code and would have to rework it a little..

« Last Edit: May 25^{th}, 2003, 7:04am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13101


Re: Find optimal function
« Reply #6 on: May 26^{th}, 2003, 3:16am » 
Quote Modify

on May 23^{rd}, 2003, 1:41am, BNC wrote: I need to find a function a(x) that solves this: Int(inf, inf, a(x)b(x,y))dx = f(y) where b and f are known. 
 I keep wondering if it may be solved with convolutions.. cause I suppose you could choose a c(tx) = a(x) and then Int(inf, inf, a(x)b(x,y))dx = f(y) would become Int(inf, inf, c(tx)b(x,y))dx = f(y) using foruier transform you can then get C(t) . B(t,y) = f(y) and thus C(t) = f(y)/B(t,y) take the inverse fourier and you get c(tx), and form that you can get a(x).. hopefully.. (I'm not really sure how to do it properly.. or if it's even allowed)


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



BNC
Uberpuzzler
Gender:
Posts: 1732


Re: Find optimal function
« Reply #7 on: May 27^{th}, 2003, 2:16am » 
Quote Modify

Hi towr, As for the convolution, I don't see how it an be done. If b(x,y) was womewhat linear, it was possible to write b(x,y) ~ B0 + g(yx), and then the inegral woud be come the conolution integral. But that's not the case here. i got stuck in the Newton method with the Jacobian. My functions are quite complicated, and calculating the Jacobian analitically is not easy. On the other hand, I couldn't figure out a way to find it numerically. On the happy side, I calculated my A matrix again, after adding a few more terms of the Tailor series from which it originated, and the "new" (more accurate, more complex) function yielded an invertable matrix... I'd like to thank you again for taking the time to think about my problem Hope I can return the favor sometime.


IP Logged 
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]



