
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 multidimensional 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 online implementation of the Complex method. Optimization can be performed with constraints for each of the coordinates (in a Ndimensional 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 Notepad editor. This file is then submitted to the server via the form (see above on this page). Optimization takes not more than 20 seconds, and the user's browser will display an output, including the information on whether the convergence condition is achieved. 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 functionOnly the right side of a function expression shoud be encoded (i.e. without "F=" or "Y="). Variables are numbered starting with 1, and their numbers should be given in braces. For example, X_{1} and X_{2} are encoded as {1} and {2}, respectively (the letter X is omitted). Thus, the function F = 5X_{1}^{2} + X_{2}  3.4 is written as follows: 5*{1}*{1}+{2}3.4
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 f(X_{1}, X_{2}) = (1  X_{1})^{2} + 100(X_{2}  X_{1}^{2})^{2} contains all mandatory blocks of lines, as well as comments and an additional block described below. Users should download this file as a template to prepare their own input data. 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 constraintsThe third mandatory block must contain at least N nonempty lines of data. Each of these lines refers to one of the variables in numerical order (the first nonempty line  to X_{1}, the second  to X_{2}, etc.). A line contains three numbers separated by commas. The first number sets the lower boundary for a given variable. The second number in a line is a coordinate of the starting point, and the third number is the upper boundary of the search. For example, the line "4 , 7.8 , 20" indicates that the optimization will start from the value of 7.8 for a given coordinate, and this variable will be constrained between 4 and 20 during the search. A coordinate of the starting point is mandatory, while any of the boundaries, or both, may be missing. In this case, a comma on each side from the starting point coordinate must be present. Thus, the line " , 7.8 , 20" means that the variable hasn't a lower boundary but has an upper boundary, i.e. the coordinate may vary from ∞ to 20. If there is a line like " , 7.8 , ", then the corresponding coordinate is not constrained. In the example input data file, an unconstrained search for a minimum is defined for both of the variables. The additional block of optimization parametersThis 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^{6}. For most cases from the practice, the default parameters provide a sufficient accuracy of optimization. However, sometimes it is necessary to use other values of L or ε. 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.4252), 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.
Examples of input data files for other test functions: 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 PHPscript, 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 