🚀 go-pugleaf

In article <1992Aug31.202559.29383@tamsun.tamu.edu> skg8286@tamuts.tamu.edu (Srihari Kumar Gangaraj) writes:
>	I need help in finding the Global Minimum of a function of n variables
>		f = f(x_i) i=1,n
>the function f may not be smooth , so I cannot use the standard methods .
>The Downhill Simplex Method (or Flexible Polyhedron) in Numerical methods
>can give only a minimum and not the Global minimum ( of all the minimum it
>picks the minimum neaarest to the guess value).
>	Can someone tell if there is any book I can refer to  , or better
>thing would be a fortran subroutine available at any of the ftp sites.
>	Thank You.
>				== Srihari
>				  
>
>
>------------------------------------------------------------------------------
>
>Srihari Gangaraj,
>srihari@aero15.tamu.edu                               

There is no method of finding a global minimum of a general function.
The only way is to try an exhaustive search on the region of x (if
possible).
A book on this topic is: Nonlinear Programming, theory and algorithms,
by Bazraa and Shetty.
-Samer

In article <1992Aug31.202559.29383@tamsun.tamu.edu> skg8286@tamuts.tamu.edu
(Srihari Kumar Gangaraj) writes:
>	I need help in finding the Global Minimum of a function of n variables
>		f = f(x_i) i=1,n
>the function f may not be smooth , so I cannot use the standard methods .
>The Downhill Simplex Method (or Flexible Polyhedron) in Numerical methods
>can give only a minimum and not the Global minimum ( of all the minimum it
>picks the minimum neaarest to the guess value).
>	Can someone tell if there is any book I can refer to  , or better
>thing would be a fortran subroutine available at any of the ftp sites.
>	Thank You.
>				== Srihari

As someone else pointed out already there is no way to find the global minimum
in the case of a general function, except exhaustive search (which is normally
higly unpratical).
However, in most of the cases in real world, a good local minimum is still
valuable. In such cases I would suggest Simulated Annealing (SA) which as got
many advantages:
1) It doesn't get easly fouled by the first local minimum at hand and gives
consistently better results than greedy algorithms (like the Downhill Simplex
Method)	or purely random walks.
2) It doesn't care wether the objective functon is smooth or not. It doesn't
even care wether the function is defined on the set of the real or natural
numbers (it can be a function of points of any sort of abstract search space,
such as the space of the logic functions with a prescribed output).
3) It's quite easy to program (most of the effort is computing the objective
function).
4) It's not extremely fussy regarding its control parameters, although you can
get better results spending some time tuning them.
5) It is statistically guaranteed to find the global optimum (but it can take a
very unpratical time to do that).

There are obviously some drawbacks: it is normally pretty slow, but you should
remember that the problem you are trying to solve it's intrinsicly hard.
You may want to try others methods like Genetic Algorithms (GA), but they are
normally harder to program and to tune, even if they are more easly
parallelizable.
A good introduction to SA is the paper:
S. Kirkpatric, C.D. Gelatt, Jr., and M.P. Vecchi, Optimization by simulated
annealing, Science 220 (4598),671-680(1983)
Regarding GA there is something very basic on the July issue of Scientific
American with even some software described at the end of the magazine plus a
lot of references.
I hope it helps.

          Enzo

>				  
>
>
>------------------------------------------------------------------------------
>
>Srihari Gangaraj,
>srihari@aero15.tamu.edu                               
>

Enzo Liguori - Canon Information Systems Research Australia