Site search: |
Home -> Science -> Computations -> |

## An overviewMethods of nonlinear programming are used to find maxima and minima of functions of several variables within a constrained region. Nonlinearity of the problem makes it possible to achieve a maximum or minimum not only on a boundary of the search, but also within the search area. One of the commonly used approaches to the multi-dimensional optimization is a Complex method, which is stochastic in nature. In a vicinity of initial search point, a set of random points ("complex") is generated. The "worst" point of the complex is then replaced by a "better" one by reflecting about the center of gravity or by shrinking the complex. On convergence to a minimum or maximum of the function, the complex collapses to a point. In practice, the search for an optimum stops when certain condition is satisfied. For example, a sufficiently small standard deviation of the function values at the vetices of the complex can be used as a convergence criterion.
This page of the site presents an on-line implementation of the Complex method. Optimization can be performed with constraints for each of the coordinates (in a N-dimensional parallelepiped, where N is a number of variables). Also, optimization with partial constraints or with no constraints is possible. Input data are prepared by a user as a plain text file - for example, with the use of ## Structure of the input data fileFile with input data contains three mandatory blocks of lines. Each of the blocks begins with an auxiliary line containing "#" character in the first position. The auxiliary line is followed by lines of data. The first block contains a code of the function to be optimized. In the second block, a type of optimization is specified (search for a minimum or maximum). The third block contains coordinates of the starting point and constraints of the search. The first block can be preceded by any number of comment lines, each of them should not begin with symbol #. In addition, a comment may be placed in an auxiliary line after the first symbol #. Such a comment cannot be continued on the next line. Empty lines within the blocks are ignored. ## Block of lines with a code of the optimized function
Only the right side of a function expression shoud be encoded (i.e. without "F=" or "Y="). Variables are numbered
The following names of the most common mathematical functions are allowed within the code of the optimized function. A function code can be continued on multiple lines without breaking numbers or function names. Spaces within a function code are ignored.
An example of input data file Rosenbrock.txt for Rosenbrock's function ## Block of lines to specify optimization typeThis is the shortest block with a single line of data where the number -1 or 1 is indicated, corresponding to the search for a minimum or maximum, respectively. An example for finding a minimum is given in Rosenbrock.txt. ## Block of lines with the starting point and constraints
The third mandatory block must contain at least N non-empty lines of data. Each of these lines refers to one of the variables in numerical order (the first non-empty line - to X ## The additional block of optimization parameters
This is an optional block, it can be omitted. The main parameters of the Complex method are the size (L) of the area where an initial complex with 2N vertices is generated, and the convergence limit ε (standard deviation of the function values in vertices of the complex, under which the optimization process stops). The default value of L is 0.02, i.e. the initial complex is generated in a hypercube with the edge of 0.02 in each coordinate. The starting point of optimization is at the center of the hypercube. The default value of ε is 10 The additional block contains two lines of data, the first of which indicates the value of L, and the second - the value of ε. For example, when ε = 10^{-6} (the default precision), search for the minimum of Rosenbrock's function does not reach the extremum, since it is located in a very narrow cleft (see fugure). Insufficient convergence can be seen after optimization with the additional block deleted from Rosenbrock.txt file. However, specifying the value ε = 10^{-9} in the additional block allows easy finding of the minimum with coordinates X_{1}=1, X_{2}=1 for Rosenbrock's test function.
In the original publication by Box (M.J. Box, A new method of constrained optimization and a comparison with other methods. Computer J. 1965, Vol.8, P.42-52), it was proposed to generate a random initial complex within the whole search area (in a parallelepiped). One of the vertices of such a complex coincides with the starting point of optimization. This approach doesn't use the parameter L and automatically accounts for differences in the scale of coordinate axes. However, behavior of too extended complex is not ideal for functions with a large number of optima in the search area. You can use the original version of the method developed by Box if a negative value of L is indicated in the additional block of lines. In this case, the upper and lower boundaries must be defined for ALL the variables, otherwise the parameter L will be set to default, and the initial complex will be generated in a hypercube with the edge L=0.02.
## Some features of the optimization performanceThe input data file saved on a local computer should be submitted to the server using the form given above on this page. In a few seconds the browser will display a result of the optimization. The program recognizes most common errors, including mistakes in the function encoding. Corresponding error messages are displayed in the user's browser. However, it should be noted that the function code is interpreted on the server to a temporary PHP-script, and if this script contains any syntax errors of PHP language, then the user will see a "white screen". For example, this happens when a comma is present instead of the decimal point in a number, or a variable is specified as X{5} instead of {5} within the function code. If you observe the "white screen" for more than 20 seconds (the time limit for optimization), you should carefully check the function code, fix errors in your input data, and repeat the calculation. Please send your feedback about the program of online optimization to a.k@ngs.ru |