Главная
Главная

Site search:
Russian version         English version Home -> Science -> Computations ->

A function of several variables optimization tool using Complex method

Select input data file:



387 successful optimizations have been carried out.

An overview

Methods 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 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 file

File 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 starting with 1, and their numbers should be given in braces. For example, X1 and X2 are encoded as {1} and {2}, respectively (the letter X is omitted). Thus, the function F = 5X12 + X2 - 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.
   sin(), cos(), tan() - the standard trigonometric functions (sine, cosine, tangent). Argument is specified in radians.
   asin(), acos(), atan() - the inverse trigonometric functions. Values are calculated in radians.
   exp() - exponent.
   log() - natural logarithm.
   sqrt() - square root.
   abs() - absolute value.
   ceil() - value rounded up to the nearest integer.
   floor() - value rounded down to the nearest integer.
   pow(<Number>, <Power>) - raising a <Number> to a <Power>.
For example, the expression X13 can be encoded as {1}*{1}*{1} or pow({1},3). The code pow({10},1/3) corresponds to cube root of X10. The number π is defined by two letters: pi. Thus, cosine of 60o can be written as cos(pi/3).

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(X1, X2) = (1 - X1)2 + 100(X2 - X12)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 type

This 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 X1, the second - to X2, 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 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-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 X1=1, X2=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.

Examples of input data files for other test functions:
Himmelblau's function  f(X1,X2) = (X12 + X2 - 11)2 + (X1 + X22 - 7)2  (see figure)
Sphere function  f(X1,X2, ..., Xn) = Σ Xi2
Sphere function with a constraint
Easom's function  f(X1,X2) = - cos(X1) cos(X2) exp [ -(X1-π)2 - (X2-π)2]  (see figure)

Some features of the optimization performance

The 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

© Andrei Khlebnikov


  

Рейтинг@Mail.ru