RGA - algorithm for black box  global optimization.

RGA  is the acronym, which stands for  Regularized Global Approximation



The RGA -algorithm for  black box global optimization  is  a tool for finding a global optimum/optima of a cost/ objective function  (OF)  of  n variables, subjected to general constraints: the goal is to get the result with  as few OF-calls as possible.
The  OF   is not assumed  differentiable  or  continuous *,  and the values which are returned by the OF  in response to relevant OF-calls can be corrupted with noise.


The algorithm is in fact a smooth nonlinear estimator  with  unsupervised leaning.
It  is a powerful tool for optimization problems governed with  expensive or/and defined in multi-dimensional spaces  OFs,  and  for estimation of (vector-valued)  functions or functionals,  defined on multi-parameter families of functions.
The RGA -algorithm  has no external adjustable  parameters,  all parameters are self- adapted.

1. to get an approximation (f) of a function F of  n variables, i.e. to estimate the OF at  any point of  a given domain.
2.  to find extreme points (minima/maxima/global extremum)  of the function F in the given domain.
1.  to  indicate a finite domain of search/constrains
2.  to evaluate  the OF  on the set of n-D points, which are implied by the algorithm
all of intrinsic  points, which are representative for the OF.
Regularized Global Approximation of the OF ( RGA-algorithm).


Given the values of the OF  on an (initial) set of starting n-D points, a differentiable (regularized)approximation f of the function F  is constructed in the entire domain of search (global approximation).
The next step consists in expansion of the initial set of points by all the extreme points (minima and maxima) of the (differentiable) approximation f . The OF should be evaluated at these points. Now the expanded set of the OF-values constitutes  a base  for  constructing a new approximation.
So, throughout  its every step ('try')  the algorithm "enriches" the previous set of points and constructs a new approximation after the OF returns the values on the subset of new (intrinsic) points.
The approximate function f can be interpreted as prediction of the true value at any point of the domain of search.
The algorithm is terminated when the minimum of having been calculated values of the OF is reached namely at that point which has been predicted as the point of global minimum provided the value itself is well-predicted.

Block-schema: principlesBlock-schema: details
Block-schema of RGA-algorithm **.


 A few illustrations of RGA-tests/applicationsTo the next page

References

1. Gennady  A. Ryzhikov and Marina S. Biryulina, 1995,
   3D nonlinear inversion by Entropy of Image Contrast (EnIC) optimization See '3D...', p.21
2. Ryzhikov, G.A., Biryulina, M.S. and Keydar, S., 1995,
   Analysis of 1D seismic waveform inversion by Regularized Global Approximation To the relevant web-page

* Sure, OF is assumed to be continuous/smooth in a small vicinity of a global minimum.
** Calligraphic F  stands  here  for  the approximate function  f
***   By no means  our  approximation  leads to  loss of accuracy: see, e.g.  protein folding.  Due to the use of  the  so called  "partly unbiased  estimation" we are dealing in fact with interpolation/extrapolation  of the function F.


to the next RGA-page   .To the next RGA-page
HOME
TOP



Google


 
 
Геннадий Рыжиков