wu :: forums « wu :: forums - Find optimal function » Welcome, Guest. Please Login or Register. Oct 10th, 2015, 3:57am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    general    wanted (Moderators: william wu, Eigenray, Grimbal, SMQ, Icarus, towr, ThudnBlunder)    Find optimal function « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Find optimal function  (Read 4558 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

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13269
 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

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13269
 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)

 « 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

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13269
 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: 13269
 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