wu :: forums
« wu :: forums - Find optimal function »

Welcome, Guest. Please Login or Register.
Apr 17th, 2014, 8:18pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   general
   wanted
(Moderators: william wu, Eigenray, Grimbal, SMQ, Icarus, towr, ThudnBlunder)
   Find optimal function
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Find optimal function  (Read 3724 times)
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Find optimal function  
« on: May 23rd, 2003, 1:41am »
Quote Quote Modify 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-1f
 
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: male
Posts: 12994
Re: Find optimal function  
« Reply #1 on: May 23rd, 2003, 1:39pm »
Quote Quote Modify 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: male
Posts: 1732
Re: Find optimal function  
« Reply #2 on: May 25th, 2003, 12:25am »
Quote Quote Modify Modify

Hi towr,
 
I hope your contest went well...  Smiley
 
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: male
Posts: 12994
Re: Find optimal function  
« Reply #3 on: May 25th, 2003, 2:56am »
Quote Quote Modify 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 ill-phrased 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)-1F(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 25th, 2003, 3:03am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
BNC
Uberpuzzler
*****





   


Gender: male
Posts: 1732
Re: Find optimal function  
« Reply #4 on: May 25th, 2003, 6:25am »
Quote Quote Modify 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: male
Posts: 12994
Re: Find optimal function  
« Reply #5 on: May 25th, 2003, 7:00am »
Quote Quote Modify 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 25th, 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: male
Posts: 12994
Re: Find optimal function  
« Reply #6 on: May 26th, 2003, 3:16am »
Quote Quote Modify Modify

on May 23rd, 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(t-x) = a(x)
and then  
Int(-inf, inf, a(x)b(x,y))dx = f(y)
would become
 
Int(-inf, inf, c(t-x)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(t-x), 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: male
Posts: 1732
Re: Find optimal function  
« Reply #7 on: May 27th, 2003, 2:16am »
Quote Quote Modify 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(y-x), 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...  Grin
 
 
I'd like to thank you again for taking the time to think about my problem Smiley Smiley Hope I can return the favor sometime.
IP Logged

How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board