ENTRUST is a MATLAB library which implements algorithms for finding a vector X which minimizes the value of a scalar function F(X), by Jeff Borggaard and Gene Cliff.
ENTRUST is a driver for the solution of an unconstrained optimization problem using line search or trust-region globalization strategies and several types of secant update strategies.
ENTRUST also includes the capability to handle least-squares problems, in which a vector X is sought which minimizes the sum of squares of the components of a nonlinear vector function R(X).
Both optimization and nonlinear minimization can also be performed with "box constraints", which require the solution to lie within a specified rectangular region. These constraints are incorporated into the trust-region algorithm.
For problems in scalar optimization, we're seeking a vector X which minimizes the value of the scalar functional F(X).
Related versions of this problem try to maximize F(X), or restrict the range of acceptable X to some rectangular region. ENTRUST can handle these related problems if the user requests them.
To specify an optimization problem, we assume we have
In least-squares problems, we're seeking a vector X which minimizes the Euclidean norm of a vector of functions R(X). The dimension of X is denoted by N whereas the dimension of R is denoted by M. Often M is larger, even much larger, than N.
A common source of such problems occurs in data fitting. For example, we might seek the coefficients A and B of a linear model - a line in the plane that comes closest to M pairs of data values. Here N will be 2 (the two unknown coefficients), but M, the number of data pairs, can be much larger. This generalizes to polynomial models; a polynomial of degree N-1 requires N unknown coefficients, which will play the role of the vector X. In such cases, the residual vector R(X) is actually linear in the parameters, and we have a linear least squares problem.
To specify a problem in least squares, we assume we have:
The Optimization and Nonlinear Least Squares problems are related, though not equivalent.
If we have a least squares problem (R and J), we can create a corresponding optimization problem. We simply define
F(X) = sum ( 1 <= i <= M ) R_{i}(X)^{2}Certainly, minimizing F will minimize the sum of squares of the entries of R.
If we have an optimization problem (F, G and H), we can create a related least squares problem. We simply define
R(X) = G(X)Note that for this least squares problem, we will have M=N. We minimize the norm of R(X), and if this minimum norm is zero, we have a critical point of our optimization function F; however, the critical point is not a guaranteed minimizer of F, though for some problems, there is extra information that can tell us we have, indeed, found a minimizer.
To solve a problem, the user must first encode the information that defines the problem.
For an optimization problem, write a MATLAB "FGH" M-file of the form
[ f, g, H ] = fname ( x, flag )which returns the values of the optimization function, gradient vector, and Hessian matrix evaluated at x. (The input value flag should generally be defined to be the empty value, that is, "flag=[]".) The value of the Hessian is only needed when a Newton method is being used. Otherwise, the M-file does not need to compute the Hessian, and can simply return an empty value.
For a least squares problem, write a MATLAB "RJ" M-file of the form
[ r, J ] = fname ( x, flag )which returns the values of the nonlinear functions and the jacobian evaluated at x. (The input value flag should generally be defined to be the empty value, that is, "flag=[]".)
The user must also set an initial value for the solution estimate X0. If no estimate is known, it is acceptable to set X0 to zero, but note that changing the initial value can cause the optimization code to converge quickly, very slowly, or to fail to converge. In some cases, changing the initial value can mean that the program converges, but to an entirely different solution with a different optimal value.
Once the problem definition has been taken care of, it is necessary to choose a solution algorithm, and, if desired, to change some of the solution parameters from their default value. All information about the solution algorithm is contained in a single MATLAB structure called options, and any choice the user makes is recorded in this single quantity. The first thing the user should do is "zero out" this quantity, so that it starts with all default values:
options = [];
ENTRUST provides four solution algorithms for the user:
To choose a solution algorithm, the user sets the method component of the options structure. A typical command would be:
options.method = 'newton';
It's probably a good idea to try to run the problem once without specifying any of the other components of options. The results of the first run, if unsatisfactory, can then be used as a guide for determining how to adjust some values of options to get a better result. Typical values that might be changed on a second run would involve
options.verbose = 1;
options.max_fevals = 50;
options.gradient_tolerance = 0.00000001;
To seek a minimizer for
f(x) = (x1-2)^{4}+((x1-2)*x2)^{2}+(x2+1)^{2}we write an FGH routine of the form:
function [ f, g, H ] = test_fgh ( x, flag ) f = ( x(1) - 2 )^4... + ( ( x(1) - 2 ) * x(2) )^2... + ( x(2) + 1 )^2; g(1) = 4 * ( x(1) - 2 )^3 ... + 2 * ( x(1) - 2 ) * x(2)^2; g(2) = 2 * ( x(1) - 2 )^2 * x(2)... + 2 * ( x(2) + 1 ); H = [];We are setting the Hessian matrix H to an empty value. We do not intend to use a Newton method, so the Hessian is not needed.
Assuming that our starting point is (1,2), we now issue the following commands:
fname = 'test_fgh'; x0 = [ 1; 2 ]; options = []; options.method = 'secant'; x = entrust ( fname, x0, options );Note that you can also use the "at sign" to refer to the function directly:
x = entrust ( @test_fgh, x0, options );
ENTRUST has a default solution procedure, but it allows the user to control the computation by overriding the default values of solution parameters. The solution procedure is specified in a MATLAB structure called options, which is the third input argument.
The user should always initialize options to its default value, by a command like:
options = [];
Then the user can specify particular solution parameters by assigning components of options. For instance, options has a component called options.method that specifies the algorithm to be used. This defaults to 'secant'. Here is how a different algorithm can be chosen:
options.method = 'newton';
The most common components to be changed include the method, gradient_tolerance, max_iterations and max_fevals. The scripts that run the examples include many cases where components are varied.
General options:
Stopping criteria:
Globalization criteria:
There are a number of example problems available. Most are available in two versions, as an optimization "FGH" problem and as a nonlinear least squares "RJ" problem:
Note that fminsearch is a MATLAB built in command which minimizes a scalar function of several variables using the Nelder-Mead algorithm.
The computer code and data files made available on this web page are distributed under the GNU LGPL license.
ENTRUST is available in a MATLAB version.
ASA047, a MATLAB library which minimizes a scalar function of several variables using the Nelder-Mead algorithm.
COMPASS_SEARCH, a MATLAB library which seeks the minimizer of a scalar function of several variables using compass search, a direct search algorithm that does not use derivatives.
NELDER_MEAD, a MATLAB program which minimizes a scalar function of multiple variables using the Nelder-Mead algorithm.
PRAXIS, a MATLAB library which minimizes a scalar function of several variables, without requiring derivative information, by Richard Brent.
TEST_OPT, a MATLAB library which defines test problems requiring the minimization of a scalar function of several variables.
TOMS178, a MATLAB library which optimizes a scalar functional of multiple variables using the Hooke-Jeeves method.
Jeff Borggaard,
Gene Cliff,
Virginia Tech.