On Jul 13, 2011, at 9:50 AM, John Reid wrote:
I have many z_n and g_n (perhaps up to N=50,000,000) and I want to
find the value of 0 < x < 1 that maximises
argmax_x \sum_n (z_n log x) + (1 - z_n) log (1 - x g_n)
0 <= z_n <= 1 for all n and most are near 0.
The g_n are all positive and most are near 1.
Obviously I can do Newton's method but this scales badly in N. Is
there some way to get an approximate answer or to use the fact that
most z_n are near 0 or that most g_n are near 1?
It looks like the cost of optimizing this problem scales linearly with
N, which is not so bad. I would be surprised if a gradient-based
method in NLopt did not converge in a few dozen iterations at most,
and even for N=5e7 that should not take long.
However, since it looks like you are solving some statistical problem
(a maximum-entropy fit?), perhaps you can get a satisfactory
approximate answer by sampling. e.g. pick a random subset of n's, and
maximize over x. Repeat several times. Then take the mean x or
something. Obviously, whether something like this is effective depends
a lot on your problem, and you are better equipped to evaluate that.
I would just try the brute-force approach of optimizing the full
problem first, before trying approximations, however. Premature
optimization is the root of all evil, as the saying goes.
--SGJ
_______________________________________________
NLopt-discuss mailing list
[email protected]
http://ab-initio.mit.edu/cgi-bin/mailman/listinfo/nlopt-discuss
