Unconstrained minimization using conjugate gradients

はじめる前に
新機能一覧
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[e04dgc] NAG[nag_opt_conj_grad] - Unconstrained minimization using conjugate gradients

Calling Sequence

e04dgc(objfun, x, objf, g, 'n'=n, 'optional_settings'=optional_settings, 'comm'=comm, 'fail'=fail)

nag_opt_conj_grad(. . .)

Parameters

objfun - procedure;

objfun must calculate the objective function and its gradient at a specified point .

Its specification is:

objfun(n, x, objf, g, comm)

n - integer;

On entry: the number of variables.

x - Vector(1..n, datatype=float[8]);

On entry: the point at which the objective function is required.

objf - assignable;

Note: On exit the variable objf will have a value of type float.

On exit: the value of the objective function at the current point .

g - Vector(1..n, datatype=float[8]);

On exit: must contain the value of at the point , for .

comm - table;

A Maple table, which should be generated using NAG[Nag_Comm], corresponding to the Nag_Comm structure.

The following fields may be accessed via NAG[GetOptions] and NAG[SetOptions]:

flag - integer

On entry: is always non-negative.

On exit: if objfun resets to some negative number then nag_opt_conj_grad (e04dgc) will terminate immediately with the error indicator NE_USER_STOP.

first - boolean

On entry: will be set to true on the first call to objfun and false for all subsequent calls.

nf - integer

On entry: the number of calculations of the objective function; this value will be equal to the number of calls made to objfun including the current one.

p - Maple

Before calling nag_opt_conj_grad (e04dgc) this field may be initialized for use by objfun when called from nag_opt_conj_grad (e04dgc).

Note: objfun should be tested separately before being used in conjunction with nag_opt_conj_grad (e04dgc). The array x must not be changed by objfun.

x - Vector(1..n, datatype=float[8]);

On entry: , an estimate of the solution point .

On exit: the final estimate of the solution.

objf - assignable;

Note: On exit the variable objf will have a value of type float.

On exit: the value of the objective function at the final iterate.

g - Vector(1..n, datatype=float[8]);

On exit: the objective gradient at the final iterate.

'n'=n - integer; (optional)

Default value: the first dimension of the arrays x, g.

On entry: the number of variables.

Constraint: . .

'optional_settings'=optional_settings - Vector; (optional)

On entry/exit: A Maple Vector, which should be generated using NAG[Nag_E04_Opt], corresponding to the Nag_E04_Opt structure. This offers the means of adjusting some of the parameter values of the algorithm. A description of the members of optional_settings is given below in Section [The optional_settings Parameter]. Further information and examples on setting and using vectors of this type are available, see the documentation for NAG[SetOptions], NAG[GetOptions], NAG[FreeOptions] and NAG[Nag_E04_Opt].

'comm'=comm - table; (optional)

A Maple table, which should be generated using NAG[Nag_Comm], corresponding to the Nag_Comm structure.

'fail'=fail - table; (optional)

The NAG error argument, see the documentation for NagError.

Description

	Purpose
	nag_opt_conj_grad (e04dgc) minimizes an unconstrained nonlinear function of several variables using a pre-conditioned, limited memory quasi-Newton conjugate gradient method. The function is intended for use on large scale problems.

Description

nag_opt_conj_grad (e04dgc) uses a pre-conditioned conjugate gradient method and is based upon algorithm PLMA as described in Gill and Murray (1979) and Section 4.8.3 of Gill et al. (1981).

The algorithm proceeds as follows:

Let be a given starting point and let denote the current iteration, starting with . The iteration requires , the gradient vector evaluated at , the th estimate of the minimum. At each iteration a vector (known as the direction of search) is computed and the new estimate is given by where (the step length) minimizes the function with respect to the scalar . At the start of each line search an initial approximation to the step is taken as:

$alpha[0]=min{1,,,2|F[k],-,F[est]|/g[k]^Tg[k]}$

where is a user-supplied estimate of the function value at the solution. If is not specified, the software always chooses the unit step length for . Subsequent step length estimates are computed using cubic interpolation with safeguards.

A quasi-Newton method computes the search direction, , by updating the inverse of the approximate Hessian and computing

(1)

The updating formula for the approximate inverse is given by

(2)

H[k+1] = H[k]-(H[k]*y[k]*s[k]^T+y[k]^T*s[k]*H[k])/(y[k]^T*s[k])+((1+y[k]^T*H[k]*y[k]*(1/(y[k]^T*s[k])))/(y[k]^T*s[k])*s[k])*s[k]^T

where and .

The method used by nag_opt_conj_grad (e04dgc) to obtain the search direction is based upon computing as where is a matrix obtained by updating the identity matrix with a limited number of quasi-Newton corrections. The storage of an by matrix is avoided by storing only the vectors that define the rank two corrections – hence the term limited-memory quasi-Newton method. The precise method depends upon the number of updating vectors stored. For example, the direction obtained with the "one-step" limited memory update is given by (1) using (2) with equal to the identity matrix, viz.

p[k+1] = -g[k+1]+(s[k]^T*g[k+1]*y[k]+y[k]^T*g[k+1]*s[k])/(y[k]^T*s[k])-s[k]^T*g[k+1]*(1+y[k]^T*y[k]*(1/(y[k]^T*s[k])))/(y[k]^T*s[k])*s[k]

nag_opt_conj_grad (e04dgc) uses a two-step method described in detail in Gill and Murray (1979) in which restarts and pre-conditioning are incorporated. Using a limited-memory quasi-Newton formula, such as the one above, guarantees to be a descent direction if all the inner products are positive for all vectors and used in the updating formula.

The termination criteria of nag_opt_conj_grad (e04dgc) are as follows:

Let specify an argument that indicates the number of correct figures desired in ( is equivalent to optional_settings[optim_tol] in the optional argument list, see Section [Optional Arguments]). If the following three conditions are satisfied:

or , where is the absolute error associated with computing the objective function

then the algorithm is considered to have converged. For a full discussion on termination criteria see Chapter 8 of Gill et al. (1981).

Error Indicators and Warnings

"NE_ALLOC_FAIL"

Dynamic memory allocation failed.

"NE_BAD_PARAM"

On entry, argument optional_settings[print_level] had an illegal value.

"NE_GRAD_TOO_SMALL"

The gradient at the starting point is too small, rerun the problem at a different starting point.

The value of is less than , where is the machine precision.

"NE_INT_ARG_LT"

On entry, n must not be less than 1: .

"NE_INVALID_INT_RANGE_1"

Value given to optional_settings[max_iter] not valid. Correct range is .

"NE_INVALID_REAL_RANGE_EF"

Value given to optional_settings[f_prec] not valid. Correct range is .

"NE_INVALID_REAL_RANGE_F"

Value given to optional_settings[max_line_step] not valid. Correct range is .

"NE_INVALID_REAL_RANGE_FF"

Value given to optional_settings[linesearch_tol] not valid. Correct range is .

"NE_NOT_APPEND_FILE"

Cannot open file for appending.

"NE_NOT_CLOSE_FILE"

Cannot close file .

"NE_OPT_NOT_INIT"

Options structure not initialized.

"NW_NO_IMPROVEMENT"

A sufficient decrease in the function value could not be attained during the final linesearch. Current point cannot be improved upon.

If objfun computes the function and gradients correctly, then this warning may occur because an overly stringent accuracy has been requested, i.e., optional_settings[optim_tol] is too small or if the minimum lies close to a step length of zero. In this case the user should apply the tests described in Section [Description] to determine whether or not the final solution is acceptable. For a discussion of attainable accuracy see Gill et al. (1981).

If many iterations have occurred in which essentially no progress has been made or nag_opt_conj_grad (e04dgc) has failed to move from the initial point, then the function objfun may be incorrect. The user should refer to the comments below under NE_DERIV_ERRORS and check the gradients using the optional_settings[verify_grad] argument. Unfortunately, there may be small errors in the objective gradients that cannot be detected by the verification process. Finite-difference approximations to first derivatives are catastrophically affected by even small inaccuracies.

"NW_STEP_BOUND_TOO_SMALL"

Computed upper-bound on step length was too small

The computed upper bound on the step length taken during the linesearch was too small. A rerun with an increased value of optional_settings[max_line_step] ( say) may be successful unless (the default value), in which case the current point cannot be improved upon.

"NW_TOO_MANY_ITER"

The maximum number of iterations, , have been performed.

If the algorithm appears to be making progress the value of optional_settings[max_iter] value may be too small (see Section [Optional Arguments]), the user should increase its value and rerun nag_opt_conj_grad (e04dgc). If the algorithm seems to be "bogged down", the user should check for incorrect gradients or ill-conditioning as described below under NW_NO_IMPROVEMENT.

	Accuracy
	On successful exit the accuracy of the solution will be as defined by the optional argument optional_settings[optim_tol].

Further Comments

	Timing
	Problems whose Hessian matrices at the solution contain sets of clustered eigenvalues are likely to be minimized in significantly fewer than iterations. Problems without this property may require anything between and iterations, with approximately iterations being a common figure for moderately difficult problems.

The optional_settings Parameter

Further information and examples on setting and using vectors of this type are available, see the documentation for NAG[SetOptions], NAG[GetOptions], NAG[FreeOptions] and NAG[Nag_E04_Opt].

list - boolean;

Default

On entry: if the argument settings in the call to nag_opt_conj_grad (e04dgc) will be printed.

print_level - String;

Default

On entry: the level of results printout produced by nag_opt_conj_grad (e04dgc). The following values are available:

"Nag_NoPrint" No output.

"Nag_Soln" The final solution.

"Nag_Iter" One line of output for each iteration.

"Nag_Soln_Iter" The final solution and one line of output for each iteration.

Constraint: "Nag_NoPrint", "Nag_Soln", "Nag_Iter" or "Nag_Soln_Iter". .

outfile - Vector(datatype=string);

On entry: The name of a file to which intermediate or diagnostic output should be appended. If a value is not provided for this parameter then the behaviour of this routine is platform dependent. Usually all output will be suppressed, however on some platforms output will be produced and will be displayed in the Maple session.

verify_grad - String;

Default

On entry: specifies the level of derivative checking to be performed by nag_opt_conj_grad (e04dgc) on the gradient elements defined in the user supplied function objfun.

verify_grad may have the following values:

"Nag_NoCheck" No derivative check is performed.

"Nag_SimpleCheck" Perform a simple check of the gradient.

"Nag_CheckObj" Perform a component check of the gradient elements.

If then a simple "cheap" test is performed, which requires only one call to objfun. If then a more reliable (but more expensive) test will be made on individual gradient components. This component check will be made in the range specified by optional_settings[obj_check_start] and optional_settings[obj_check_stop], default values being and n respectively. The procedure for the derivative check is based on finding an interval that produces an acceptable estimate of the second derivative, and then using that estimate to compute an interval that should produce a reasonable forward-difference approximation. The gradient element is then compared with the difference approximation. (The method of finite difference interval estimation is based on Gill et al. (1983b)). The result of the test is printed out by nag_opt_conj_grad (e04dgc) if .

Constraint: "Nag_NoCheck", "Nag_SimpleCheck" or "Nag_CheckObj". .

print_gcheck - boolean;

Default

On entry: if true the result of any derivative check (see optional_settings[verify_grad]) will be printed.

obj_check_start - integer;
obj_check_stop - integer;

Default

On entry: these options take effect only when . They may be used to control the verification of gradient elements computed by the function objfun. For example, if the first 30 variables appear linearly in the objective, so that the corresponding gradient elements are constant, then it is reasonable for optional_settings[obj_check_start] to be set to 31.

Constraint: . .

max_iter - integer;

Default

On entry: the limit on the number of iterations allowed before termination.

Constraint: . .

f_prec - Vector(datatype=float[8]);

Default

On entry: this argument defines , which is intended to be a measure of the accuracy with which the problem function can be computed. The value of should reflect the relative precision of ; i.e., acts as a relative precision when is large, and as an absolute precision when is small. For example, if is typically of order 1000 and the first six significant digits are known to be correct, an appropriate value for would be . In contrast, if is typically of order and the first six significant digits are known to be correct, an appropriate value for would be . The choice of can be quite complicated for badly scaled problems; see Chapter 8 of Gill et al. (1981), for a discussion of scaling techniques. The default value is appropriate for most simple functions that are computed with full accuracy. However when the accuracy of the computed function values is known to be significantly worse than full precision, the value of should be large enough so that nag_opt_conj_grad (e04dgc) will not attempt to distinguish between function values that differ by less than the error inherent in the calculation.

Constraint: . .

optim_tol - Vector(datatype=float[8]);

Default

On entry: specifies the accuracy to which the user wishes the final iterate to approximate a solution of the problem. Broadly speaking, optim_tol indicates the number of correct figures desired in the objective function at the solution. For example, if optim_tol is and nag_opt_conj_grad (e04dgc) terminates successfully, the final value of should have approximately six correct figures. nag_opt_conj_grad (e04dgc) will terminate successfully if the iterative sequence of -values is judged to have converged and the final point satisfies the termination criteria (see Section [Description], where represents optim_tol).

Constraint: . .

linesearch_tol - Vector(datatype=float[8]);

Default

On entry: controls the accuracy with which the step taken during each iteration approximates a minimum of the function along the search direction (the smaller the value of linesearch_tol, the more accurate the linesearch). The default value requests an inaccurate search, and is appropriate for most problems. A more accurate search may be appropriate when it is desirable to reduce the number of iterations – for example, if the objective function is cheap to evaluate.

Constraint: . .

max_line_step - Vector(datatype=float[8]);

Default

On entry: defines the maximum allowable step length for the line search.

Constraint: . .

f_est - float;

On entry: specifies the user-supplied guess of the optimum objective function value. This value is used by nag_opt_conj_grad (e04dgc) to calculate an initial step length (see Section [Description]). If no value is supplied then an initial step length of 1.0 will be used but it should be noted that for badly scaled functions a unit step along the steepest descent direction will often compute the function at very large values of .

iter - assignable;

Note: On exit the variable iter will have a value of type integer.

On exit: the number of iterations which have been performed in nag_opt_conj_grad (e04dgc).

nf - assignable;

Note: On exit the variable nf will have a value of type integer.

On exit: the number of times the objective function has been evaluated (i.e., number of calls of objfun). The total excludes the calls made to objfun for purposes of derivative checking.

Description of Printed Output

The level of printed output can be controlled with the structure members optional_settings[list], optional_settings[print_gcheck] and optional_settings[print_level] (see Section [The optional-settings Parameter]). If then the argument values to nag_opt_conj_grad (e04dgc) are listed, followed by the result of any derivative check if . The printout of the optimization results is governed by the value of optional_settings[print_level]. The default of provides a single line of output at each iteration and the final result. This section describes all of the possible levels of results printout available from nag_opt_conj_grad (e04dgc).

If a simple derivative check, , is requested then the directional derivative, , of the objective gradient and its finite difference approximation are printed out, where is a random vector of unit length.

When a component derivative check, , is requested then the following results are supplied for each component:

x[i] the element of .

dx[i] the optimal finite difference interval.

g[i] the gradient element.

Difference approxn. the finite difference approximation.

Itns the number of trials performed to find a suitable difference interval.

The indicator, OK or BAD?, states whether the gradient element and finite difference approximation are in agreement.

If the gradient is believed to be in error nag_opt_conj_grad (e04dgc) will exit with the error "NE_DERIV_ERRORS" is raised.

When "Nag_Iter" or "Nag_Soln_Iter" a single line of output is produced on completion of each iteration, this gives the following values:

Itn the current iteration number .

Nfun the cumulative number of calls to objfun. The evaluations needed for the estimation of the gradients by finite differences are not included in the total Nfun. The value of Nfun is a guide to the amount of work required for the linesearch. nag_opt_conj_grad (e04dgc) will perform at most 16 function evaluations per iteration.

Objective the current value of the objective function, .

Norm g the Euclidean norm of the gradient vector, .

Norm x the Euclidean norm of .

Norm(x(k-1)-x(k)) the Euclidean norm of .

Step the step taken along the computed search direction .

If "Nag_Soln" or "Nag_Soln_Iter", the final result is printed out. This consists of:

x the final point, .

g the final gradient vector, .

If then printout will be suppressed; the user can print the final solution when nag_opt_conj_grad (e04dgc) returns to the calling program.

Output of results via a user-defined printing function

The rest of this section can be skipped if the default printing facilities provide the required functionality.

When a user-defined function is assigned to optional_settings[print_fun] this will be called in preference to the internal print function of nag_opt_conj_grad (e04dgc). Calls to the user-defined function are again controlled by means of the optional_settings[print_gcheck] and optional_settings[print_level] members. Information is provided through st and comm the two structure arguments to optional_settings[print_fun].

If then the results from the last iteration of nag_opt_conj_grad (e04dgc) are in the following members of st:

n - integer

The number of variables.

x - Vector(datatype=float[8])

Points to the n memory locations holding the current point .

f - float

The value of the current objective function.

g - Vector(datatype=float[8])

Points to the n memory locations holding the first derivatives of at the current point .

step - float

The step taken along the search direction .

xk_norm - float

The Euclidean norm of .

iter - integer

The number of iterations performed by nag_opt_conj_grad (e04dgc).

nf - integer

The cumulative number of calls made to objfun.

If then the members

n - integer

The number of variables,

x - Vector(datatype=float[8])

Points to the n memory locations holding the initial point ,

g - Vector(datatype=float[8])

Points to the n memory locations holding the first derivatives of at the initial point ,

are set, and the details of any derivative check performed by nag_opt_conj_grad (e04dgc) are held in the following substructure of st:

gprint - table

Which in turn contains two substructures g_chk, f_sim and a pointer to an array of substructures, .

g_chk - table

The substructure g_chk contains the members:

type - table

The type of derivative check performed by nag_opt_conj_grad (e04dgc). This will be the same value as in optional_settings[verify_grad].

g_error - integer

This member will be equal to one of the error codes no error raised or NE_DERIV_ERRORS according to whether the derivatives were found to be correct or not.

obj_start - integer

Specifies the gradient element at which any component check started. This value will be equal to optional_settings[obj_check_start].

obj_stop - integer

Specifies the gradient element at which any component check ended. This value will be equal to optional_settings[obj_check_stop].

f_sim - table

The result of a simple derivative check, , will be held in this substructure which has members:

correct - boolean

If true then the objective gradient is consistent with the finite difference approximation according to a simple check.

dir_deriv - Vector(datatype=float[8])

The directional derivative where is a random vector of unit length with elements of approximately equal magnitude.

fd_approx - Vector(datatype=float[8])

The finite difference approximation, , to the directional derivative.

f_comp - table

The results of a component derivative check, , will be held in the array of n substructures of type pointed to by f_comp. The procedure for the derivative check is based on finding an interval that produces an acceptable estimate of the second derivative, and then using that estimate to compute an interval that should produce a reasonable forward-difference approximation. The gradient element is then compared with the difference approximation. (The method of finite difference interval estimation is based on Gill et al. (1983b)).

correct - boolean

If true then this objective gradient component is consistent with its finite difference approximation.

hopt - Vector(datatype=float[8])

The optimal finite difference interval. This is dx[i] in the NAG default printout.

gdiff - Vector(datatype=float[8])

The finite difference approximation for this gradient component.

iter - integer

The number of trials performed to find a suitable difference interval.

comment - character

A character string which describes the possible nature of the reason for which an estimation of the finite difference interval failed to produce a satisfactory relative condition error of the second-order difference. Possible strings are: "Constant?", "Linear or odd?", "Too nonlinear?" and "Small derivative?".

The relevant members of the structure comm are:

g_prt - boolean

Will be true only when the print function is called with the result of the derivative check of objfun.

it_prt - boolean

Will be true when the print function is called with the result of the current iteration.

sol_prt - boolean

Will be true when the print function is called with the final result.

p - Maple

Before calling nag_opt_conj_grad (e04dgc) this field may be initialized for use by when called from nag_opt_conj_grad (e04dgc).

Examples

objfun := proc(n, x, objf::evaln, g, comm)
  local ex1:
  ex1 := exp(x[1]):
  objf := ex1*(4*x[1]*x[1] + 2*x[2]*x[2] + 4*x[1]*x[2] + 2*x[2] + 1):
  g[1] := 4*ex1*(2*x[1] + x[2]) + eval(objf):
  g[2] := 2*ex1*(2*x[2] + 2*x[1] + 1):
end proc:
x := Vector([-1, 1], datatype=float[8]):
g := Vector(2, datatype=float[8]):
NAG:-e04dgc(objfun, x, objf, g):