pluginName = Common methods of data optimization analysis plug-in
providerName = Biosoft.Ru

glbsolve.descr = \
\<html>\
\<h2>GLBSOLVE algorithm.</h2>\
\<div align="justify">\
\A deterministic global optimization method<sup><font size=3>1</font></sup>. It is a version of \
\the DIRECT algorithm<sup><font size=3>2</font></sup> that handles nonlinear and integer constraines.\
\The first step in the DIRECT algorithm is to transform the search space to be the unit hypercube. \
\The function is then sampled at the center-point of this cube. Computing the function value at \
\the center-point instead of doing it at the vertices is an advantage when dealing with problems \
\in higher dimensions. The hypercube is then divided into smaller hyperrectangles whose center-\
\points are also sampled. Instead of using a Lipschitz constant when determining the rectangles \
\to sample next, DIRECT identifies a set of potentially optimal rectangles in each iteration. All \
\potentially optimal rectangles are further divided into smaller rectangles whose center-points are \
\sampled. When no Lipschitz constant is used, there is no natural way of defining convergence \
\(except when the optimal function value is known as in the test problems). Instead, the procedure \
\described above is performed for a predefined number of iterations.<br><br>\
\<font size=3>\
\<sup>1</sup>M. Bj&ouml;rkman and K. Holmstr&ouml;m, \
\"Global Optimization Using the DIRECT Algorithm in Matlab". \
\AMO, vol. 1, #2, pp. 17-37, 1999.<br>\
\<sup>2</sup>D.R. Jones, \
\"DIRECT global optimization algorithm". \
\Encyclopedia of optimization, pp. 431-440, 2001.\
\</font>\
\</div>\
</html>

asa.descr = \
\<html>\
\<h2>Adaptive simulated annealing (ASA).</h2>\
\<div align="justify">\
\ASA algorithm<sup><font size=3>1</font></sup> is developed to statistically find the best global fit of a nonlinear non-convex \
\cost-function over a <i>D</i>-dimensional space. It is argued that this algorithm permits an annealing \
\schedule for "temperature" <i>T</i> decreasing exponentially in annealing-time k, \
\<i>T = T</i><sub>0</sub>exp(-<i>c</i>k<sup>(1/<i>D</i>)</sup>)). The introduction of re-annealing also permits adaptation\
\ to changing sensitivities in the multi-dimensional parameter-space. This annealing schedule is faster\
\ than fast Cauchy annealing, where <i>T = T</i><sub>0</sub>/k, and much faster than Boltzmann annealing, \
\where <i>T = T</i><sub>0</sub>/ln k.<br><br>\
\<font size=3>\
<sup>1</sup>L. Ingber, \
\"Adaptive simulated annealing (ASA): Lessons learned. \
\Control and Cybernetics, Vol. 25, No. 1, pp. 33-54, 1996.\
\</font>\
\</div>\
</html>

sres.descr =  \
\<html>\
\<body>\
\<h2>Stochastic ranking evolution strategy (SRES)<sup><font size=3>1<font size=3></sup>.</h2>\
\<div align="justify">\
\ &#09;&#09;In the (&mu; &lambda;)-ES algorithm, the individual <i>i</i> is a set of real-valued vectors\
\ <nobr>(x<sub><i>i</i></sub>, &sigma;<sub><i>i</i></sub>)</nobr> <nobr>&forall; <i>i</i> &isin; {1,...,&lambda;}.</nobr>\
\ The initial population of x is generated according to a uniform <i>n</i>-dimensional probability\
\ distribution over the search space <i>S</i>. Let &delta;x be an approximate measure of the expected\
\ distance to the global optimum, then the initial setting for the "mean step sizes" should be\
\ <center>\
\ <nobr>&sigma;<sub><i>i, j</i></sub><sup>(0)</sup> = &delta;x<sub><i>j</i></sub> / <i>n</i><sup>&frac12;</sup> &asymp;\
\ (<i>l<sub>j</sub> &minus; r<sub>j</sub></i>) / <i>n</i><sup>&frac12;</sup>,</nobr>\
\ <br>\
\ <nobr><i>l<sub>j</sub></i> &le; x<sub><i>j</i></sub> &le; <i>r<sub>j</sub></i>,\
\ <i>i</i> &isin; {1,...,&lambda;}, <i>j</i> &isin; {1,...,<i>n</i>},</nobr>\
\ </center>\
\ where &sigma;<sub><i>i, j</i></sub> denotes the <i>j</i>th component of the vector &sigma;<sub><i>i</i></sub>.\
\ We use these initial values as upper bounds on &sigma;.<br>\
\ &#09;&#09;Following the bubble-sort procedure is used to rank the individuals in a population, and the best (highest ranked)\
\ &mu; individuals out of &lambda; are selected for the next generation. The truncation level is set at\
\ <nobr>&mu; / &lambda; &asymp; 1/7.</nobr><br>\
\ &#09;&#09;Variation of strategy parameters is performed before the modification of objective variables. We generate &lambda;\
\ new strategy parameters from &mu; old ones so that we can use the &lambda; new strategy parameters in generating &lambda; offspring later.\
\ The "mean step sizes" are updated according to the log-normal update rule:\
\ <nobr><i>i</i> = 1,...,&mu;</nobr>, <nobr><i>h</i> = 1,...,&lambda;</nobr>, <nobr><i>j</i> = 1,...,<i>n</i>,</nobr>\
\ <table border="0" width="100%">\
\ <tr>\
\ <td width="90%" align="center">\
\ <nobr>&sigma;<sub><i>h, j</i></sub><sup>(<i>g</i>+1)</sup> = 1/2 (&sigma;<sub><i>h, j</i></sub><sup>(<i>g</i>)</sup> + &sigma;<sub><i>k</i>, <i>j</i></sub><sup>(<i>g</i>)</sup>) \
\ exp(&tau;&prime; <i>N</i>(0,1) + &tau; <i>N<sub>j</sub></i>(0,1)))</nobr>\
\ </td>\
\ <td width="10%" align="right">\
\ <b>(1)</b>\
\ </table>\
\ where <i>N</i>(0,1) is a normally distributed one-dimensional random variable with an expectation of 0 and variance 1 and\
\ <nobr><i>k</i> &isin; {1,...,&mu;}</nobr> is an index generated at random and anew for each <i>j</i>.\
\ The "learning rates" &tau; and &tau;&prime; are set equal to <nobr>(4<i>n</i>)<sup>&minus;&frac14;</sup></nobr> and <nobr>(2<i>n</i>)<sup>&minus;&frac12;</sup></nobr>, respectively.\
\ Recombination is performed on the self-adaptive parameters before applying the update rule given by (1).<br>\
\ &#09;&#09;Having varied the strategy parameters, each individual <nobr>(x<sub><i>i</i></sub>, &sigma;<sub><i>i</i></sub>),</nobr>\
\ <nobr>&forall; <i>i</i> &isin; {1,...,&mu;}</nobr> creates <nobr>&lambda;/&mu;</nobr> offspring on average, so that a total\
\ of &lambda; offspring are generated\
\ <center>\
\ <nobr>x<sub><i>h, j</i></sub><sup>(<i>g</i>+1)</sup> = x<sub><i>h, j</i></sub><sup>(<i>g</i>)</sup> + &sigma;<sub><i>h, j</i></sub><sup>(<i>g</i>+1)</sup> <i>N<sub>j</sub></i>(0,1).</nobr>\
\ </center>\
\ &#09;&#09;Recombination is not used in the variation of objective variables. When an offspring is generated outside the parametric\
\ bounds defined by the problem, the mutation (variation) of the objective variable will be retried until the variable is within its\
\ bounds. In order to save computation time, the mutation is retried only ten times and then ignored, learning the object variable\
\ in its original state within the parameter bounds.\
\<br><br>\
\<font size=3>\
\<sup>1</sup>Thomas P. Runarsson and Xin Yao,\
\ "Stochastic Ranking for Constrained Evolutionary Optimization".\
\ IEEE Transactions on Evolutionary Computation, vol. 4, #3, pp. 284-294, Sept 2000.\
\</font>\
\</div>\
\</body>\
\</html>

goldfeld.descr = \
\<html>\
\<body>\
\<h2>Minimization by quadratic Hill-climbing<sup><font size=3>1<font size=3></sup>.</h2>\
\<div align="justify">\
\   A gradient method for minimazing general function -H(x), where variable x denotes the column vector\
\ of variables <nobr>(x<sub>1</sub>,...,x<sub>n</sub>)</nobr>. This method rests on maximizing a quadratic\
\ approximation to the function H(x) on a suitably chosen spherical region. Computational technique\
\ for maximization take the form of an iterative procedure. The method is specifically designed to work\
\ for functions which are not concave and for starting points which are not necessarily near a maximum.<br>\
\   Let us denote by F<sub>x</sub> the vector of first partial derivatives evaluated at x\
\ and by S<sub>x</sub> the symmetric (n x n) matrix of second partial derivatives\
\ evaluated at x.<br>\
\   Assume that H(x) admits of a second-order Taylor series expansion around a point\
\ <nobr>a = (a<sub>1</sub>,...,a<sub>n</sub>):</nobr>\
\ <table border="0" width="100%">\
\ <tr>\
\ <td width="90%" align="center">\
\ <nobr>H(x) &asymp; H(a) + (x &minus; a)'F<sub>a</sub> + &frac12;(x &minus; a)'S<sub>a</sub>(x &minus; a)</nobr>\
\ </td>\
\ <td width="10%" align="right">\
\ <b>(1)</b>\
\ </table>\
\ where the subscripts indicate the point of evaluation.<br>\
\   The iterative procedure for finding the maximum of the function is,\
\ given point x<sup>p</sup> at which S<sub>x<sup>p</sup></sub> and F<sub>x<sup>p</sup></sub>\
\ are evaluated, to define the next point, x<sup>p+1</sup>, as the maximum of the quadratic\
\ approximation (1) on a spherical region centered at x<sup>p</sup>. Ideally, the region\
\ should be taken as large as possible provided that it is small enough that in the region the quadratic\
\ approximation is a satisfactory guide to the actual behavior of the function. The following procedure\
\ attempts to approximate this ideal.<br>\
\    Two distinct cases arise:<br>\
\       <b>(a)</b> F<sub>x<sup>p</sup></sub> significantly different from 0. In this event we choose a number\
\       <table border="0" width="100%">\
\       <tr>\
\       <td width="90%" align="center">\
\       <nobr>&alpha; = &lambda;<sub>1</sub> + R||F<sub>x<sup>p</sup></sub>||</nobr>\
\       </td>\
\       <td width="10%" align="right">\
\       <b>(2)</b>\
\       </table>\
\       where &lambda;<sub>1</sub> is the largest eigenvalue of S<sub>x<sup>p</sup></sub>, and\
\       R is a positive parameter determined by the following rule.\
\          Let &Delta;H be the actual change in the function due to the proposed &Delta;x and let\
\       &Delta;Q be the corresponding change in the quadratic approximation. Let <nobr>z = &Delta;H/&Delta;Q.</nobr>\
\       If z &le; 0, the proposed &Delta;x implies overshooting; it is therefore not accepted, R is\
\       increased by a factor of 4 and a new <nobr>(S - &alpha;I)<sup>-1</sup></nobr> is calculated. If <nobr>z > 0</nobr>\
\       and close to unity (in practice, if z is between 0.7 and 1.3) R is decreased by multiplying R\
\       by a factor of 0.4. If <nobr>z > 2</nobr>, R is again increased by a factor of 4. For other values of z\
\       (<nobr>0&le;z&le;0.7</nobr> and <nobr>1.3&le;z&le;2</nobr>) the magnitude of the factor multiplying R is determined by\
\       linear interpolation between 0.4 and 4.\
\       We now take\
\       <center>\
\       <nobr>\
\       x<sup>p+1</sup> = x<sup>p</sup> &minus; (S<sub>x<sup>p</sup></sub> &minus; &alpha; I)<sup>-1</sup>F<sub>x<sup>p</sup></sub>\
\       </nobr>\
\       </center>\
\       or\
\      <center>\
\       <nobr>\
\       x<sup>p+1</sup> = x<sup>p</sup> &minus; S<sup>-1</sup><sub>x<sup>p</sup></sub> F<sub>x<sup>p</sup></sub>\
\       </nobr>\
\      </center>\
\       according to whether &alpha; is positive or not. If &alpha;=0 at this point, we generally directly\
\       computed the step size necessary to produce a positive &alpha;. This typically saved a number of iterations.<br>\
\       Now x<sup>p+1</sup> is the maximum of the quadratic\
\       approximation to the function on a region B<sub>&alpha;</sub> of radius\
\       <center>\
\       <nobr>\
\       ||(S<sub>x<sup>p</sup></sub> &minus; &alpha; I)<sup>-1</sup>F<sub>x<sup>p</sup></sub>||\
\       </nobr>\
\       </center>\
\       with the center at x<sup>p</sup>.<br>\
\       <b>(b)</b> F<sub>x<sup>p</sup></sub>is so near 0 that the length of the step taken is within a preset\
\       tolerance of 0. Then, if S<sub>x<sup>p</sup></sub> is negative definite, the process is terminated\
\       and x<sup>p</sup> is accepted as the location of the maximum. If S<sub>x<sup>p</sup></sub> is not\
\       negative definite, we are at a saddle point or at the bottom of a cylindrical valley. A step is taken\
\       along the eigenvector corresponding &lambda;<sub>1</sub> and the algorithm recycles in the usual manner.<br>\
\       One final feature, incorporated for reason of computational efficiency rather than theoretical\
\       elegance, was the introduction of a scalar h<sup>p</sup> into (2), writing it as\
\       <center>\
\       <nobr>\
\       x<sup>p+1</sup> = x<sup>p</sup> &minus; h<sup>p</sup>(S<sub>x<sup>p</sup></sub> &minus; &alpha; I)<sup>-1</sup>F<sub>x<sup>p</sup></sub>.\
\       </nobr>\
\       </center>\
\       At each step the computation is first performed with <nobr>h<sup>p</sup>=1</nobr>. If this gives an improvement\
\       in H(x), h<sup>p</sup> is multiplied by a constant, which magnitude is a decreasing function of the\
\       absolute value of the angle between the current step and the immediately preceding step. Then the\
\       function is examined at the new point so obtained. This process is repeated until the function\
\       declines in which event the last step is accepted. It should be noted that these attempts at\
\       stretching the step are relatively cheap since they require only an evaluation of the function.\
\       This is in contrast to changes in &alpha; within each iteration which require reinversion of\
\       (<nobr>S<sub>x<sup>p</sup></sub> &minus; &alpha; I).</nobr><br><br>\
\<font size=3>\
\<sup>1</sup>Stephen M. Goldfeld et al,\
\"Maximization by Quadratic Hill-climbing".\
\Econometric Research Program, Research Memorandum #72, January 19, 1965.\
\</font>\
\</div>\
\</body>\
</html>