Minimizing or Maximizing a Function

はじめる前に
新機能一覧
Maple ワークシートの作成
Mapleワークシートを共有
Maple ウィンドウのカスタマイズ
Maple システムのカスタマイズ
コネクティビティ
Mathematics
数学
物理
プログラミング
グラフィックス
Student パッケージ
Science and Engineering
科学・エンジニアリング
アプリケーションと例題
リファレンス
システム
MapleSim
MapleSim ツールボックス
MapleSim ヘルプ
Tasks
Toolboxes
- BlockImporter
- Global Optimization
- Grid Computing
- Maple-NAG Connector
  - General information
  - Computational Routines
    - a02 (Complex Arithmetic)
    - c02 (Zeros of Polynomials)
    - c05 (Roots of One or More Transcendental Equations)
    - c06 (Fourier Transforms)
    - d01 (Quadrature)
    - d02 (Ordinary Differential Equations)
    - d03 (Partial Differential Equations)
    - d06 (Mesh Generation)
    - e01 (Interpolation)
    - e02 (Curve and Surface Fitting)
    - e04 (Minimizing or Maximizing a Function)
      - e04 Introduction
      - e04abc (nag_opt_one_var_no_deriv)
      - e04bbc (nag_opt_one_var_deriv)
      - e04ccc (nag_opt_simplex)
      - e04dgc (nag_opt_conj_grad)
      - e04fcc (nag_opt_lsq_no_deriv)
      - e04gbc (nag_opt_lsq_deriv)
      - e04hcc (nag_opt_check_deriv)
      - e04hdc (nag_opt_check_2nd_deriv)
      - e04jbc (nag_opt_bounds_no_deriv)
      - e04kbc (nag_opt_bounds_deriv)
      - e04lbc (nag_opt_bounds_2nd_deriv)
      - e04mfc (nag_opt_lp)
      - e04mzc (nag_opt_sparse_mps_read)
      - e04ncc (nag_opt_lin_lsq)
      - e04nfc (nag_opt_qp)
      - e04nkc (nag_opt_sparse_convex_qp)
      - e04ucc (nag_opt_nlp)
      - e04ugc (nag_opt_nlp_sparse)
      - e04unc (nag_opt_nlin_lsq)
      - e04xac (nag_opt_estimate_deriv)
      - e04yac (nag_opt_lsq_check_deriv)
      - e04ycc (nag_opt_lsq_covariance)
    - f01 (Matrix Factorizations)
    - f02 (Eigenvalues and Eigenvectors)
    - f03 (Determinants)
    - f04 (Simultaneous Linear Equations)
    - f06 (Linear Algebra Support Functions)
    - f07 (Linear Equations (LAPACK))
    - f08 (Least-squares and Eigenvalue Problems (LAPACK))
    - f11 (Large Scale Linear Systems)
    - f16 (NAG Interface to BLAS)
    - g01 (Simple Calculations on Statistical Data)
    - g02 (Correlation and Regression Analysis)
    - g03 (Multivariate Methods)
    - g04 (Analysis of Variance)
    - g05 (Random Number Generators)
    - g07 (Univariate Estimation)
    - g08 (Nonparametric Statistics)
    - g10 (Smoothing in Statistics)
    - g11 (Contingency Table Analysis)
    - g12 (Survival Analysis)
    - g13 (Time Series Analysis)
    - h (Operations Research)
    - m01 (Sorting)
    - s (Approximations of Special Functions)
    - x01 (Mathematical Constants)
    - x02 (Machine Constants)
    - x04 (Input-Output Utilities)
  - Getting Started
  - Example Worksheet
エラーメッセージガイド
マニュアル
数学アプリ

NAG Library e04 - Minimizing or Maximizing a Function

Scope of the Chapter

An optimization problem involves minimizing a function (called the objective function) of several variables, possibly subject to restrictions on the values of the variables defined by a set of constraint functions. The functions in the Library are concerned with function minimization only, since the problem of maximizing a given objective function F(x) is equivalent to minimizing .

This introduction is only a brief guide to the subject of optimization designed for the casual user. Anyone with a difficult or protracted problem to solve will find it beneficial to consult a more detailed text, such as Gill et al. (1981) or Fletcher (1987).

Users who are unfamiliar with the mathematics of the subject may find some sections difficult at first reading; if so, they should concentrate on Sections [Types of Optimization Problems], [Geometric Representation and Terminology], [Scaling], [Analysis of Computed Results] and [Recommendations on Choice and Use of Available Functions].

Background to the Problems

Types of Optimization Problems

The solution of optimization problems by a single, all-purpose, method is cumbersome and inefficient. Optimization problems are therefore classified into particular categories, where each category is defined by the properties of the objective and constraint functions, as illustrated by some examples below.

Properties of Objective Function	Properties of Constraints
Nonlinear	Nonlinear
Sums of squares of nonlinear functions	Sparse linear
Quadratic	Linear
Sums of squares of linear functions	Bounds
Linear	None

For instance, a specific problem category involves the minimization of a nonlinear objective function subject to bounds on the variables. In the following sections we define the particular categories of problems that can be solved by functions contained in this chapter. Not every category is given special treatment in the current version of the Library; however, the long-term objective is to provide a comprehensive set of functions to solve problems in all such categories.

	Unconstrained minimization
	In unconstrained minimization problems there are no constraints on the variables. The problem can be stated mathematically as follows: where , that is, .

	Nonlinear least-squares problems
	Special consideration is given to the problem for which the function to be minimized can be expressed as a sum of squared functions. The least-squares problem can be stated mathematically as follows: $minimize {f^T,f,=,(∑),f[i]^2,(x)} x in R^n$ where the th element of the -vector is the function .

Minimization subject to bounds on the variables

These problems differ from the unconstrained problem in that at least one of the variables is subject to a simple bound (or restriction) on its value, e.g., , but no constraints of a more general form are present.

The problem can be stated mathematically as follows:

subject to .

This format assumes that upper and lower bounds exist on all the variables. By conceptually allowing and all the variables need not be restricted.

Minimization subject to linear constraints

A general linear constraint is defined as a constraint function that is linear in more than one of the variables, e.g., . The various types of linear constraint are reflected in the following mathematical statement of the problem:

subject to the

equality constraints:		;
inequality constraints:		;
		;
range constraints:

bounds constraints:

where each is a vector of length ; , and are constant scalars; and any of the categories may be empty.

Although the bounds on could be included in the definition of general linear constraints, we prefer to distinguish between them for reasons of computational efficiency.

If is a linear function, the linearly-constrained problem is termed a linear programming problem (LP problem); if is a quadratic function, the problem is termed a quadratic programming problem (QP problem). For further discussion of LP and QP problems, including the dual formulation of such problems, see Dantzig (1963).

Minimization subject to nonlinear constraints

A problem is included in this category if at least one constraint function is nonlinear, e.g., . The mathematical statement of the problem is identical to that for the linearly-constrained case, except for the addition of the following constraints:

equality constraints:		;
inequality constraints:		;
range constraints:		,

where each is a nonlinear function; and are constant scalars; and any category may be empty. Note that we do not include a separate category for constraints of the form , since this is equivalent to .

Although the general linear constraints could be included in the definition of nonlinear constraints, again we prefer to distinguish between them for reasons of computational efficiency.

If is a nonlinear function, the nonlinearly-constrained problem is termed a nonlinear programming problem (NLP problem). For further discussion of NLP problems, see Gill et al. (1981) or Fletcher (1987).

	Minimization subject to bounds on the objective function
	In all of the above problem categories it is assumed that where and . Problems in which and/or are finite can be solved by adding an extra constraint of the appropriate type (i.e., linear or nonlinear) depending on the form of . Further advice is given in Section [Function Evaluations at Infeasible Points].

Geometric Representation and Terminology

To illustrate the nature of optimization problems it is useful to consider the following example in two dimensions:

(This function is used as the example function in the documentation for the unconstrained functions.)

Figure 1 is a contour diagram of . The contours labelled are isovalue contours, or lines along which the function takes specific constant values. The point is a local unconstrained minimum, that is, the value of () is less than at all the neighbouring points. A function may have several such minima. The lowest of the local minima is termed a global minimum. In the problem illustrated in Figure 1, is the only local minimum. The point is said to be a saddle point because it is a minimum along the line AB, but a maximum along CD.

If we add the constraint (a simple bound) to the problem of minimizing , the solution remains unaltered. In Figure 1 this constraint is represented by the straight line passing through , and the shading on the line indicates the unacceptable region (i.e., ). The region in satisfying the constraints of an optimization problem is termed the feasible region. A point satisfying the constraints is defined as a feasible point.

If we add the nonlinear constraint , represented by the curved shaded line in Figure 1, then is not a feasible point because . The solution of the new constrained problem is , the feasible point with the smallest function value (where ).

	Gradient vector
	The vector of first partial derivatives of is called the gradient vector, and is denoted by , i.e., For the function illustrated in Figure 1, The gradient vector is of importance in optimization because it must be zero at an unconstrained minimum of any function with continuous first derivatives.

	Hessian matrix
	The matrix of second partial derivatives of a function is termed its Hessian matrix. The Hessian matrix of is denoted by , and its th element is given by . If has continuous second derivatives, then must be positive semi-definite at any unconstrained minimum of .

Jacobian matrix; matrix of constraint normals

In nonlinear least-squares problems, the matrix of first partial derivatives of the vector-valued function is termed the Jacobian matrix of and its th component is .

The vector of first partial derivatives of the constraint is denoted by

a[i](x)=[(&PartialD;c[i](x))/(&PartialD;x[1]),,,(&PartialD;c[i](x))/(&PartialD;x[2]),,,..,,,(&PartialD;c[i](x))/(&PartialD;x[n])]^T

The matrix whose columns are the vectors is termed the matrix of constraint normals. At a point , the vector is orthogonal (normal) to the isovalue contour of passing through ; this relationship is illustrated for a two-dimensional function in Figure 2.

Note that if is a linear constraint involving , then its vector of first partial derivatives is simply the vector .

Sufficient Conditions for a Solution

All nonlinear functions will be assumed to have continuous second derivatives in the neighbourhood of the solution.

Unconstrained minimization

The following conditions are sufficient for the point to be an unconstrained local minimum of :

; and

is positive-definite,

where denotes the Euclidean length of .

Minimization subject to bounds on the variables

At the solution of a bounds-constrained problem, variables which are not on their bounds are termed free variables. If it is known in advance which variables are on their bounds at the solution, the problem can be solved as an unconstrained problem in just the free variables; thus, the sufficient conditions for a solution are similar to those for the unconstrained case, applied only to the free variables.

Sufficient conditions for a feasible point to be the solution of a bounds-constrained problem are as follows:

; and

is positive-definite; and

; ,

where is the gradient of with respect to the free variables, and is the Hessian matrix of with respect to the free variables. The extra condition (iii) ensures that cannot be reduced by moving off one or more of the bounds.

Linearly-constrained minimization

For the sake of simplicity, the following description does not include a specific treatment of bounds or range constraints, since the results for general linear inequality constraints can be applied directly to these cases.

At a solution , of a linearly-constrained problem, the constraints which hold as equalities are called the active or binding constraints. Assume that there are active constraints at the solution , and let denote the matrix whose columns are the columns of corresponding to the active constraints, with the vector similarly obtained from ; then

The matrix is defined as an matrix satisfying:

[[(A)^TZ=0 ],[Z^TZ=I ]]

The columns of form an orthogonal basis for the set of vectors orthogonal to the columns of .

Define

, the projected gradient vector of ;

, the projected Hessian matrix of .

At the solution of a linearly-constrained problem, the projected gradient vector must be zero, which implies that the gradient vector can be written as a linear combination of the columns of , i.e., . The scalar is defined as the Lagrange-multiplier corresponding to the th active constraint. A simple interpretation of the th Lagrange-multiplier is that it gives the gradient of along the th active constraint normal; a convenient definition of the Lagrange-multiplier vector (although not a recommended method for computation) is:

Sufficient conditions for to be the solution of a linearly-constrained problem are:

is feasible, and ; and

, or equivalently, ; and

is positive-definite; and

if corresponds to a constraint ;

if corresponds to a constraint .

The sign of is immaterial for equality constraints, which by definition are always active.

Nonlinearly-constrained minimization

For nonlinearly-constrained problems, much of the terminology is defined exactly as in the linearly-constrained case. The set of active constraints at again means the set of constraints that hold as equalities at , with corresponding definitions of and : the vector contains the active constraint functions, and the columns of are the gradient vectors of the active constraints. As before, is defined in terms of as a matrix such that:

[[(A)^TZ=0 ],[Z^TZ=I]]

where the dependence on has been suppressed for compactness.

The projected gradient vector is the vector . At the solution of a nonlinearly-constrained problem, the projected gradient must be zero, which implies the existence of Lagrange-multipliers corresponding to the active constraints, i.e., .

The Lagrangian function is given by:

We define as the gradient of the Lagrangian function; as its Hessian matrix, and as its projected Hessian matrix, i.e., .

Sufficient conditions for to be the solution of a nonlinearly-constrained problem are:

is feasible, and ; and

, or, equivalently, ; and

is positive-definite; and

if corresponds to a constraint of the form .

The sign of is immaterial for equality constraints, which by definition are always active.

Note that condition (ii) implies that the projected gradient of the Lagrangian function must also be zero at , since the application of annihilates the matrix .

Background to Optimization Methods

All the algorithms contained in this chapter generate an iterative sequence ${x^(k)}$ that converges to the solution in the limit, except for some special problem categories (i.e., linear and quadratic programming). To terminate computation of the sequence, a convergence test is performed to determine whether the current estimate of the solution is an adequate approximation. The convergence tests are discussed in Section [Analysis of Computed Results].

Most of the methods construct a sequence ${x^(k)}$ satisfying:

where the vector is termed the direction of search, and is the steplength. The steplength is chosen so that and is computed using one of the techniques for one-dimensional optimization referred to in Section [One-dimensional optimization].

	One-dimensional optimization
	The Library contains two special functions for minimizing a function of a single variable. Both functions are based on safeguarded polynomial approximation. One function requires function evaluations only and fits a quadratic polynomial whilst the other requires function and gradient evaluations and fits a cubic polynomial. See Section 4.1 of Gill et al. (1981).

Methods for unconstrained optimization

The distinctions among methods arise primarily from the need to use varying levels of information about derivatives of in defining the search direction. We describe three basic approaches to unconstrained problems, which may be extended to other problem categories. Since a full description of the methods would fill several volumes, the discussion here can do little more than allude to the processes involved, and direct the user to other sources for a full explanation.

a. Newton-type Methods (Modified Newton Methods)

Newton-type methods use the Hessian matrix , or a finite-difference approximation to , to define the search direction. The functions in the Library either require a function that computes the elements of directly, or they approximate by finite-differences.

Newton-type methods are the most powerful methods available for general problems and will find the minimum of a quadratic function in one iteration. See Sections 4.4 and 4.5.1 of Gill et al. (1981).

b. Quasi-Newton Methods

Quasi-Newton methods approximate the Hessian by a matrix which is modified at each iteration to include information obtained about the curvature of along the current search direction . Although not as robust as Newton-type methods, quasi-Newton methods can be more efficient because is not computed directly, or approximated by finite-differences. Quasi-Newton methods minimize a quadratic function in iterations. See Section 4.5.2 of Gill et al. (1981).

c. Conjugate-Gradient Methods

Unlike Newton-type and quasi-Newton methods, conjugate-gradient methods do not require the storage of an by matrix and so are ideally suited to solve large problems. Conjugate-gradient type methods are not usually as reliable or efficient as Newton-type, or quasi-Newton methods. See Section 4.8.3 of Gill et al. (1981).

Methods for nonlinear least-squares problems

These methods are similar to those for unconstrained optimization, but exploit the special structure of the Hessian matrix to give improved computational efficiency.

Since

the Hessian matrix is of the form

where is the Jacobian matrix of , and is the Hessian matrix of .

In the neighbourhood of the solution, is often small compared to (for example, when represents the goodness-of-fit of a nonlinear model to observed data). In such cases, may be an adequate approximation to , thereby avoiding the need to compute or approximate second derivatives of . See Section 4.7 of Gill et al. (1981).

Methods for handling constraints

Bounds on the variables are dealt with by fixing some of the variables on their bounds and adjusting the remaining free variables to minimize the function. By examining estimates of the Lagrange-multipliers it is possible to adjust the set of variables fixed on their bounds so that eventually the bounds active at the solution should be correctly identified. This type of method is called an active set method. One feature of such methods is that, given an initial feasible point, all approximations are feasible. This approach can be extended to general linear constraints. At a point, , the set of constraints which hold as equalities being used to predict, or approximate, the set of active constraints is called the working set.

Nonlinear constraints are more difficult to handle. If at all possible, it is usually beneficial to avoid including nonlinear constraints during the formulation of the problem. The methods currently implemented in the Library handle nonlinearly constrained problems by transforming them into a sequence of quadratic programming problems. A feature of such methods is that is not guaranteed to be feasible except in the limit, and this is certainly true of the functions currently in the Library. See Chapter 6, particularly Sections 6.4 and 6.5, of Gill et al. (1981).

Anyone interested in a detailed description of methods for optimization should consult the references.

Scaling

Scaling (in a broadly defined sense) often has a significant influence on the performance of optimization methods. Since convergence tolerances and other criteria are necessarily based on an implicit definition of "small" and "large", problems with unusual or unbalanced scaling may cause difficulties for some algorithms. Although there are currently no user-callable scaling functions in the Library, scaling is automatically performed by default in the functions which solve sparse LP, QP or NLP problems. The following sections present some general comments on problem scaling.

Transformation of variables

One method of scaling is to transform the variables from their original representation, which may reflect the physical nature of the problem, to variables that have certain desirable properties in terms of optimization. It is generally helpful for the following conditions to be satisfied:

the variables are all of similar magnitude in the region of interest;

a fixed change in any of the variables results in similar changes in . Ideally, a unit change in any variable produces a unit change in ;

the variables are transformed so as to avoid cancellation error in the evaluation of .

Normally, users should restrict themselves to linear transformations of variables, although occasionally nonlinear transformations are possible. The most common such transformation (and often the most appropriate) is of the form

where is a diagonal matrix with constant coefficients. Our experience suggests that more use should be made of the transformation

where is a constant vector.

Consider, for example, a problem in which the variable represents the position of the peak of a Gaussian curve to be fitted to data for which the extreme values are 150 and 170; therefore is known to lie in the range 150–170. One possible scaling would be to define a new variable , given by

A better transformation, however, is given by defining as

Frequently, an improvement in the accuracy of evaluation of can result if the variables are scaled before the functions to evaluate are coded. For instance, in the above problem just mentioned of Gaussian curve fitting, may always occur in terms of the form , where is a constant representing the mean peak position.

Scaling the objective function

The objective function has already been mentioned in the discussion of scaling the variables. The solution of a given problem is unaltered if is multiplied by a positive constant, or if a constant value is added to . It is generally preferable for the objective function to be of the order of unity in the region of interest; thus, if in the original formulation is always of the order of (say), then the value of should be multiplied by when evaluating the function within an optimization function. If a constant is added or subtracted in the computation of , usually it should be omitted, i.e., it is better to formulate as rather than as or even . The inclusion of such a constant in the calculation of can result in a loss of significant figures.

Scaling the constraints

A "well scaled" set of constraints has two main properties. Firstly, each constraint should be well-conditioned with respect to perturbations of the variables. Secondly, the constraints should be balanced with respect to each other, i.e., all the constraints should have "equal weight" in the solution process.

The solution of a linearly- or nonlinearly-constrained problem is unaltered if the th constraint is multiplied by a positive weight . At the approximation of the solution determined by a Library function, any active linear constraints will (in general) be satisfied "exactly" (i.e., to within the tolerance defined by machine precision) if they have been properly scaled. This is in contrast to any active nonlinear constraints, which will not (in general) be satisfied "exactly" but will have "small" values (for example, , , and so on). In general, this discrepancy will be minimized if the constraints are weighted so that a unit change in produces a similar change in each constraint.

A second reason for introducing weights is related to the effect of the size of the constraints on the Lagrange-multiplier estimates and, consequently, on the active set strategy. This means that different sets of weights may cause an algorithm to produce different sequences of iterates. Additional discussion is given in Gill et al. (1981).

Analysis of Computed Results

Convergence criteria

The convergence criteria inevitably vary from function to function, since in some cases more information is available to be checked (for example, is the Hessian matrix positive-definite?), and different checks need to be made for different problem categories (for example, in constrained minimization it is necessary to verify whether a trial solution is feasible). Nonetheless, the underlying principles of the various criteria are the same; in non-mathematical terms, they are:

is the sequence ${x^(k)}$ converging?

is the sequence ${F^(k)}$ converging?

are the necessary and sufficient conditions for the solution satisfied?

The decision as to whether a sequence is converging is necessarily speculative. The criterion used in the present functions is to assume convergence if the relative change occurring between two successive iterations is less than some prescribed quantity. Criterion (iii) is the most reliable but often the conditions cannot be checked fully because not all the required information may be available.

Checking results

Little a priori guidance can be given as to the quality of the solution found by a nonlinear optimization algorithm, since no guarantees can be given that the methods will not fail. Therefore, the user should always check the computed solution even if the function reports success. Frequently a "solution" may have been found even when the function does not report a success. The reason for this apparent contradiction is that the function needs to assess the accuracy of the solution. This assessment is not an exact process and consequently may be unduly pessimistic. Any "solution" is in general only an approximation to the exact solution, and it is possible that the accuracy specified by the user is too stringent.

Further confirmation can be sought by trying to check whether or not convergence tests are almost satisfied, or whether or not some of the sufficient conditions are nearly satisfied. When it is thought that a function has raised an error only because the requirements for "success" were too stringent it may be worth restarting with increased convergence tolerances.

For nonlinearly-constrained problems, check whether the solution returned is feasible, or nearly feasible; if not, the solution returned is not an adequate solution.

Confidence in a solution may be increased by re-solving the problem with a different initial approximation to the solution. See Section 8.3 of Gill et al. (1981) for further information.

Monitoring progress

Many of the functions in the chapter have facilities to allow the user to monitor the progress of the minimization process, and users are encouraged to make use of these facilities. Monitoring information can be a great aid in assessing whether or not a satisfactory solution has been obtained, and in indicating difficulties in the minimization problem or in the ability of the function to cope with the problem.

The behaviour of the function, the estimated solution and first derivatives can help in deciding whether a solution is acceptable and what to do in the event of a return with a fail other than NE_NOERROR.

Confidence intervals for least-squares solutions

When estimates of the parameters in a nonlinear least-squares problem have been found, it may be necessary to estimate the variances of the parameters and the fitted function. These can be calculated from the Hessian of at the solution.

In many least-squares problems, the Hessian is adequately approximated at the solution by (see Section [Methods for nonlinear least-squares problems]). The Jacobian, , or a factorization of is returned by all the comprehensive least-squares functions and, in addition, a function is available in the Library to estimate variances of the parameters following the use of most of the nonlinear least-squares functions, in the case that is an adequate approximation.

Let be the inverse of , and be the sum of squares, both calculated at the solution ; an unbiased estimate of the variance of the th parameter is

and an unbiased estimate of the covariance of and is

If is the true solution, then the confidence interval on is

where is the percentage point of the -distribution with degrees of freedom.

In the majority of problems, the residuals , for , contain the difference between the values of a model function calculated for different values of the independent variable , and the corresponding observed values at these points. The minimization process determines the parameters, or constants , of the fitted function . For any value, , of the independent variable , an unbiased estimate of the variance of is

var`ϕ`=(2S)/(m-n)(∑)(∑)[(&PartialD;`ϕ`)/(&PartialD;x[i])][z][(&PartialD;`ϕ`)/(&PartialD;x[j])][z]H[ij]

The confidence interval on at the point is

For further details on the analysis of least-squares solutions see Bard (1974) and Wolberg (1967).

Optional Facilities

The optimization functions of this chapter provide a range of optional facilities: these offer the possibility of fine control over many of the algorithmic paramters and the means of adjusting the level and nature of the printed results.

Control of these optional facilities is exercised by a structure of type Nag_E04_Opt, the members of the structure being optional input or output parameters to the function. After declaring the structure variable, which is named options in this manual, the user must initialize the structure by passing its address in a call to the utility function e04xxc (nag_opt_init). Selected members of the structure may then be set to the user's required values and the address of the structure passed to the optimization function. Any member which has not been set by the user will indicate to the optimization function that the default value should be used for this parameter. A more detailed description of this process is given below in Section [Method of Setting Optional Parameters]

Examples of parameters to the algorithms which may be altered from their default value are options.linesearch_tol or options.optim_tol (these control the accuracy to which the linesearch and final solution are computed, respectively), and options.max_iter (which limits the number of iterations the algorithm will perform). Certain members of options supply further details concerning the final results, for example the member pointer options.state gives the status of the constraints, while in the LP and QP solvers the member pointers options.lambda and options.ax also give the final values of the Lagrange multipliers and the linear constraints respectively.

The optimization process may sometimes terminate before a satisfactory answer has been found, for instance when the limit on the number of iterations has been reached. In such cases the user may wish to re-enter the function making use of the information already obtained. Functions e04dgc (nag_opt_conj_grad), e04fcc (nag_opt_lsq_no_deriv) and e04gbc (nag_opt_lsq_deriv) can simply be re-entered but the functions e04jbc (nag_opt_bounds_no_deriv), e04kbc (nag_opt_bounds_deriv), e04mfc (nag_opt_lp), e04ncc (nag_opt_lin_lsq), e04nfc (nag_opt_qp), e04nkc (nag_opt_sparse_convex_qp), e04ucc (nag_opt_nlp) and e04unc (nag_opt_nlin_lsq) have a structure member which needs to be set appropriately if the function is to make use of information from the previous call. The member is init_state in functions e04jbc (nag_opt_bounds_no_deriv) and e04kbc (nag_opt_bounds_deriv), and start in the other functions listed.

Control of Printed Output

Results from the optimization process may be printed to a file. These include the results after each iteration and the final results at termination of the search process. The amount of detail printed out may be increased or decreased by setting the print_level option. An example value is "Nag_Soln" which when assigned to print_level will cause the optimization function to print only the final result; all intermediate results printout is suppressed.

If the results printout is not in the desired form then it may be switched off, by setting the print_level option to "Nag_NoPrint".

In addition to the results, the values of the parameters to the optimization function are printed out when the function is entered; the Boolean options, list, may be set to FALSE if this listing is not required.

Memory Management

The options structure contains a number of pointers for the input of data and the output of results. The optimization functions will manage the allocation of memory to these pointers; when all calls to these functions have been completed then a utility function NAG[FreeOptions] can be called by the user's program to free the NAG allocated memory which is no longer required.

If the calling function is part of a larger program then this utility function allows the user to conserve memory by freeing the NAG allocated memory before the options structure goes out of scope. NAG[FreeOptions] can free all NAG allocated memory in a single call, but it may also be used selectively. In this case the memory assigned to certain pointers may be freed leaving the remaining memory still available; pointers to this memory and the results it contains may then be passed to other functions in the user's program without passing the structure and all its associated memory.

Although the NAG C Library optimization functions will manage all memory allocation and deallocation, it may occasionally be necessary for the user to allocate memory to the options structure from within the calling program before entering the optimization function.

An example of this is where the user stores information in a file from an optimization run and at a later date wishes to use that information to solve a similar optimization problem or the same one under slightly changed conditions. The pointer options.state, for example, would need to be allocated memory by the user before the status of the constraints could be assigned from the values in the file. The member options.init_state would need to be appropriately set for functions e04jbc (nag_opt_bounds_no_deriv) and e04kbc (nag_opt_bounds_deriv) and member options.start for functions e04mfc (nag_opt_lp) and e04nfc (nag_opt_qp).

If the user does assign memory to a pointer within the options structure then the deallocation of this memory must also be performed by the user; the utility function NAG[FreeOptions] will only free memory allocated by NAG C Library optimization functions. When user allocated memory is freed using the standard C library function free() then the pointer should be set to NULL immediately afterwards; this will avoid possible confusion in the NAG memory management system if a NAG function is subsequently entered.

Reading Optional Parameter Values From a File

Optional parameter values may be placed in a file by the user and the function e04xyc (nag_opt_read) used to read the file and assign the values to the options structure. This utility function permits optional parameter values to be supplied in any order and altered without recompilation of the program. The values read are also checked before assignment to ensure they are in the correct range for the specified option. Pointers within the options structure cannot be assigned to using e04xyc (nag_opt_read).

Method of Setting Optional Parameters

The method of using and setting the optional parameters is:

step 1 declare a structure of type Nag_E04_Opt.

step 2 initialize the structure using e04xxc (nag_opt_init).

step 3 assign values to the structure.

step 4 pass the address of the structure to the optimization function.

step 5 call NAG[FreeOptions] to free any memory allocated by the optimization function.

If after step 4, it is wished to re-enter the optimization function, then step 3 can be returned to directly, i.e., step 5 need only be executed when all calls to the optimization function have been made.

At step 3, values can be assigned directly and/or by means of the option file reading function e04xyc (nag_opt_read). If values are only assigned from the options file then step 2 need not be performed as e04xyc (nag_opt_read) will automatically call e04xxc (nag_opt_init) if the structure has not been initialized.

Recommendations on Choice and Use of Available Functions

The choice of function depends on several factors: the type of problem (unconstrained, etc.); the level of derivative information available (function values only, etc.); the experience of the user (there are easy-to-use versions of some functions); whether or not storage is a problem; whether or not the function is to be used in a multithreaded environment; and whether computational time has a high priority. Not all choices are catered for in the current version of the Library.

Service Functions

One of the most common errors in the use of optimization functions is that user-supplied functions do not evaluate the relevant partial derivatives correctly. Because exact gradient information normally enhances efficiency in all areas of optimization, the user should be encouraged to provide analytical derivatives whenever possible. However, mistakes in the computation of derivatives can result in serious and obscure run-time errors. Consequently, service functions are provided to perform an elementary check on the user-supplied gradients. These functions are inexpensive to use in terms of the number of calls they require to user-supplied functions.

The appropriate checking functions are as follows:

Minimization function	Checking function(s)
e04lbc (nag_opt_bounds_2nd_deriv)	e04hcc (nag_opt_check_deriv) and e04hdc (nag_opt_check_2nd_deriv)
e04gbc (nag_opt_lsq_deriv)	e04yac (nag_opt_lsq_check_deriv)

It should be noted that functions e04ucc (nag_opt_nlp) and e04ugc (nag_opt_nlp_sparse) each incorporate a check on the gradients being supplied. This involves verifying the gradients at the first point that satisfies the linear constraints and bounds. There is also an option to perform a more reliable (but more expensive) check on the individual gradient elements being supplied. Note that the checks are not infallible.

A second type of service function computes a set of finite-differences to be used when approximating first derivatives. Such differences are required as input parameters by some functions that use only function evaluations.

e04ycc (nag_opt_lsq_covariance) estimates selected elements of the variance-covariance matrix for the computed regression parameters following the use of a nonlinear least-squares function.

e04xac (nag_opt_estimate_deriv) estimates the gradient and Hessian of a function at a point, given a function to calculate function values only, or estimates the Hessian of a function at a point, given a function to calculate function and gradient values.

Function Evaluations at Infeasible Points

All the functions for constrained problems will ensure that any evaluations of the objective function occur at points which approximately satisfy any simple bounds or linear constraints. Satisfaction of such constraints is only approximate because functions which estimate derivatives by finite-differences may require function evaluations at points which just violate such constraints even though the current iteration just satisfies them.

There is no attempt to ensure that the current iteration satisfies any nonlinear constraints. Users who wish to prevent their objective function being evaluated outside some known region (where it may be undefined or not practically computable), may try to confine the iteration within this region by imposing suitable simple bounds or linear constraints (but beware as this may create new local minima where these constraints are active).

Note also that some functions allow the user-supplied function to return a parameter () with a negative value to force an immediate clean exit from the minimization function when the objective function (or nonlinear constraints where appropriate) cannot be evaluated.