2D discrete function minimization if extreme points are known, using Matlab

[andreass]

Hello everyone.

I would like to hear some suggestions on minimizing a function.
I have discrete 2D function (a grid, where each (x,y) point have some value), where I know only extreme points (more specifically - ridges. http://en.wikipedia.org/wiki/Ridge_detection).

I want to reconstruct this function just from these points by minimizing "smoothness function" (or cost function?).
My smoothness function looks like this:

sum[ ( 4*f(x,y) - f(x-1,y) - f(x+1,y) - f(x,y-1) - f(x, y+1) )^2 ]

for all points (x, y) in the grid (of course in border and corner points it's (3*f(x, y) - ...)^2 and (2*f(x, y) - ...)^2 ).

I use fmincon by passing all extreme point values (as a vector) and upper and lower bounds. It works good and converges very good, but it takes much too long on minimizing grids that are bigger than 100x100.

Providing outside defined gradient and Hessian seems to help to converge, but runtime gets even much greater due to the many calculations.

I also use use sparse matrices and set Hessian to 'lbfgs', but it helps to certain size.

Any suggestions on how to make it run faster?

 

[Valkarie]

Maybe there is an alternative way to minimize this function? Or maybe there is a better way to define the smoothness function? Or maybe there are some specific settings to fmincon that I didn't consider?Thanks in advance!