3
$\begingroup$

I have a function defined by three parameters (or variables): $f(a,b,c)$ This function is not explicitly defined but is actually a piece of code which returns the result of fitting a curve $g(a,b,c)$ to a set of $(x,y)$ points in a 2D space:

O = {$(x_1,y_1,w_1), (x_2,y_2,w_2), ...$}

where $w$ are weights associated with each point. The smaller $f$, the better the fit of $g$ with those points. Each one of these points has a weight associated to it.

Each of these three parameters can only assume values from a given discrete set:

A = {$a_1, a_2, a_3, ..., N_a$}

B = {$b_1, b_2, b_3, ..., N_b$}

C = {$c_1, c_2, c_3, ..., N_c$}

Every set $(a_i,b_j,c_k)$ implies a value for $f(a_i,b_j,c_k)$ and as I said, I need to find the $(a_i,b_j,c_k)$ set that returns the minimum value for $f$.

What I do to evaluate $f$ is:

  1. Take a set of $(a_i,b_j,c_k)$ values and construct a $g_{ijk} (a_i,b_j,c_k)$ curve in 2D space.
  2. For each $(x,y)$ point in $O$, find the point in $g_{ijk}$ that is closest to it (euclidean distance)
  3. Multiply that distance by the weight ($0<w<1$) associated to that $(x,y)$ point. This gives me a weighted distance for each point.
  4. After processing all points in the $O$ set, sum all weighted distances.
  5. The sum obtained above is what I call $f(a_i,b_j,c_k)$, ie: a measure of how good $g_{ijk} (a_i,b_j,c_k)$ fitted $O$.

So far I've managed to do this through a brute force approach where I test every possible combination of $a,b,c$ (ie: $N_a*N_b*N_c$ combinations) one after another and at the end I simply isolate the minimum.

Is there a better/more efficient algorithm to perform this minimization, given the restrictions on my function and parameters?


Add

After a bit of research it looks like this falls into the category of combinatorial optimization problems for which methods such as Cross-Entropy seem to be the standard approach.

$\endgroup$

migrated from stats.stackexchange.com Sep 25 '13 at 14:50

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • $\begingroup$ It is a function in the strict sense, but if you do not assume any other properties, there is nothing more that can be said about finding its minimum value: brute force is all there is. Because you posted this here on a stats forum instead of a math forum, one would guess you have some additional statistical knowledge about the behavior of $f$. What is it? $\endgroup$ – whuber Sep 23 '13 at 15:44
  • $\begingroup$ I'm not sure I can provide much more information on $f$. It's basically a fitting function that returns a value according to how well a curve (characterized by a set of $(x,y,z)$ parameters) fits a cloud of points in a 2D space. The goodness of fit is defined through a measurement of how distant (euclidian distance) those points are from the curve. $\endgroup$ – Gabriel Sep 23 '13 at 16:05
  • 1
    $\begingroup$ Often more than half the task of answering a statistical question is figuring out how to ask it in the first place :-). Actually, this phenomenon is not confined to statistics. $\endgroup$ – whuber Sep 23 '13 at 19:34
  • 1
    $\begingroup$ might be better suited for scicomp.SE $\endgroup$ – Memming Sep 24 '13 at 13:47
  • 1
    $\begingroup$ @Gabriel You probably mean $(a_i, b_j, c_k)$ instead of $(a_i, b_i, c_i)$ in your question. Second, this is a problem of discrete optimization, and if you take any book in this direction you may get somewhere. $\endgroup$ – Nico Schlömer Sep 25 '13 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.