CFD Online Discussion Forums (https://www.cfd-online.com/Forums/)
-   Main CFD Forum (https://www.cfd-online.com/Forums/main/)
-   -   Minimization (https://www.cfd-online.com/Forums/main/7081-minimization.html)

 doche January 30, 2004 05:25

Minimization

Hello, I'm searching for a method which can evaluate the global minimum of a multivariable function f(x,y,z). But due to feedback consideration, I have only acces to values of grad(f)(no way to calculate f). How can I do?

 Ananda Himansu February 3, 2004 18:29

Re: Minimization

If you cannot evaluate the cost function "f" itself, then you cannot cheaply employ random searches of the solution space, or search methods such as genetic algorithms that must be fed the value of f at random locations. Since you have access to only the values of "grad(f)", for efficiency reasons you are restricted to optimization methods that rely on gradient information to descend into the valleys. Pick a classical gradient-based algorithm, such as a Newton-based or a quasi-Newton or Powell's method or BGFS etc.

Pick a suitable starting point r0 = (x0, y0, z0). Arbitrarily label the value of f at r0 as f0 = f(r0) = 0. Evaluate grad(f0). Step through the minimization (optimization) procedure, but anywhere in the algorithm that you come across a needed value of f, get a second or third order (if the Hessian is involved) estimate of f by extrapolation using previous points and the gradient at those points. You can numerically approximate the Hessian by numerically differentiating the Jacobian grad(f). Eventually the algorithm should terminate at a location where grad(f) is approximately zero (a minimum). This procedure will locate the minimum in the search space, i.e., rmin = (xmin, ymin, zmin), but of course it will not tell you the absolute value of fmin = f(rmin), since you do not have access to that. It only tells you the relative or gauge f, i.e., fmin - f0.

If you suspect that the minimum found by the algorithm is only local and not global, you will need to restart the algorithm from a different initial point, say r0n = (x0n, y0n, z0n). Integrate grad(f) from f(r0)=0 to the point r0n (using a second or third order integration based on values of grad(f)), to find a value of f(r0n) that is consistent with f(r0)=0. Use an integration contour (path) that is parallel to one of the coordinate axes for each of its three legs (from (x0,y0,z0) to (x0n,y0,z0) to (x0n,y0n,z0) to (x0n,y0n,z0n)), or integrate along a straight line from (x0,y0,z0) to (x0n,y0n,z0n), parametrically. Then begin the second run of the minimization algorithm at r0n. Similarly if you need a third or further runs.

Of course, you can use this procedure of integration of grad(f) to find a consistent gauge value of f for every single required function evaluation even in methods such as genetic algorithms or simulated annealing etc, but the cost would probably be prohibitive unless you are working in a really small search space.

Of course, to do all this, you will probably be unable to use canned routines. You should use a routine from say the book Numerical Recipes (Vetterling et al), and modify the source code to estimate values of f as I described. Good luck.

Ananda Himansu

 Ananda Himansu February 4, 2004 02:57

Clarification Re: Minimization

Perhaps I failed to mention the simple mathematical concept behind the bookkeeping that I suggested in the previous post.

Let the cost function that you are trying to minimize be denoted by g(r). Pick an arbitrary point r0=(x0,y0,z0) in your search domain. Then we can alternatively represent g as

g(r) = g(r0) + Definite Path Integral of grad(g) from r0 to r

Your cost evaluation function does not return g but rather grad(g). So g(r0) is unknown. Define a gauge cost function f by

f(r) = Definite Path Integral of grad(g) from r0 to r

From this definition, note that if g is single-valued, then f is independent of the path of integration (in theory). Also that f(r0) = 0. And that grad(f) = grad(g), and hessian(f) = hessian(g). The definition of f is theoretically equivalent to saying f(r) = g(r) - g(r0), but algorithmically the path integral definition of f must be used, since the value of g(r) is unknown. A key fact that follows from the definition of f is that if the minimum (gmin) of g occurs at rmin=(xmin,ymin,zmin), gmin = g(rmin), then the minimum (fmin) of f also occurs at rmin, i.e., fmin = f(rmin). Also, fmin = gmin - g(r0).

Apply a classical gradient-based minimization algorithm to f, taking into account that because of the integral definition, the value of f must be extrapolated from nearby point/s using the value of grad(g). The end-result of your minimization effort will be obtaining the values of rmin and fmin ( = f(rmin)-f(r0) = g(rmin)-g(r0)).

Ananda Himansu

 doche February 4, 2004 06:50

Re: Clarification

Thank you very much for your response The gauge function should be very usefull

 Ananda Himansu February 4, 2004 12:23

Re: Clarification

You are quite welcome. To clarify further, the path integral definition of g is obtained as the antiderivative of the differential relation

where the * represents a vector dot product, which may not have been clear from the way I wrote it previously.

With a classical gradient-based optimization algorithm, the construction of the gauge function f is only required in order to know how low your minimum is relative to your starting point, i.e., to know gmin-g(r0). If you did not care to know this, with pure gradient-based algorithms, you could eliminate all references to f itself, and merely find the point rmin as the endpoint of your descent path, without constructing f.

If your search space is small enough to do a systematic exhaustive search on a mesh with a spacing small enough to satisfy your accuracy requirement, then you will need to construct the gauge cost f, in order to efficiently compare the values and find the minimum achieved on the selected mesh. In this case, grad(g) is used only to construct f, instead of being used to select a descent direction.

 Ananda Himansu February 5, 2004 02:28

Re: Minimization

This may be more information than you are looking for, but ... my friend and officemate Farhad reminded me of a different approach to your minimization problem. This approach is not as general as the one I previously described, but worth mentioning since it will involve less programming on your part, and may also require less computation, because no numerical path integral is needed.

If you can be certain that your cost function g(r) is differentiable, and that it does not achieve its minimum on the boundary of your search domain, but rather at a point in the interior, then sufficient conditions that an interior point rmin be the location of a minimum (local or global) is that grad(g) = 0, and that hessian(g) be positive definite, at rmin.

You can define a new objective function