Author |
Topic: Find optimal function (Read 6163 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
Find optimal function
« on: May 23rd, 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-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:
Posts: 13730
|
|
Re: Find optimal function
« Reply #1 on: May 23rd, 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 25th, 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: 13730
|
|
Re: Find optimal function
« Reply #3 on: May 25th, 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 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:
Posts: 1732
|
|
Re: Find optimal function
« Reply #4 on: May 25th, 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: 13730
|
|
Re: Find optimal function
« Reply #5 on: May 25th, 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 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:
Posts: 13730
|
|
Re: Find optimal function
« Reply #6 on: May 26th, 2003, 3:16am » |
Quote 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:
Posts: 1732
|
|
Re: Find optimal function
« Reply #7 on: May 27th, 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(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... 
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]
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print