In some optimizations problems, the objective-function is just too complicated to evaluate directly at every iteration, and in this case, we use surrogate functions, functions that mimic most of the properties of the true objective-function, but that is much simpler analytically and/or computationally.

Lately, I have done some thinking about what properties a surrogate function (or surrogate model) should have to be practical.

The Wikipedia on surrogate models is informative, but leaves many questions opened.

For example, should a surrogate function have its derivative’s zeroes in the same place as the real function’s derivative? Should it have its derivative’s signs match the signs of the real function’s derivatives?

In some cases, it’s quite possible to do have such a surrogate function. Let’s suppose you need to know, not the exact distance, but which points on a sphere is further than an other. If you’re dealing with the unit sphere centered on and points expressed as , , , coordinates also centered on , then if is a point and another, is the distance between and as measured on the sphere.

But let’s pretend that, for some reason, is troublesome to compute. We will want to use the surrogate , the , or Euclidean distance, between the two points and .

The surrogate is well behaved, relative to . As for , if you rotate around , is unchanged. If you bring closer to (while remaining on the sphere), both decrease—while not a the same rate. If you push further from , both grow—again not at the same rate.

The figure illustrates the regions:

* * *

So behaves mostly as , and, by hypothesis, is much easier to compute (if a square root is a lot less costly to compute than arccos, which remains to be seen). For many algorithms, could be used as a cromulent surrogate.

This is of course a rather simple example of surrogate, and I wonder how much one can build into the surrogate. What are the conditions for a surrogate to be well-behaved? What does it even mean to be well-behaved?

I searched a bit but found precious little on the topic. I now uncompunctiously ask from you, reader, to hint me, to suggest me books, articles, or any resources on the topic.

This entry was posted on Tuesday, July 26th, 2011 at 10:45 am and is filed under algorithms, Mathematics, Science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

@NicolasChapados merci! mais il reste encore deux chapitres à compléter. Ensuite, ça sera les joies de l'index, de recoudre les xrefs, etc. 6 hours ago