LIN_CON_TRUST

NPT – The number of interpolation conditions, which is required to be in the interval [N+2,(N+1)*(N+2)/2]. Typical choices are NPT=N+6 and NPT=2*N+1. Larger values tend to be highly inefficient when the number of variables is substantial, due to the amount of work and extra difficulty of adjusting more points. (Input)

A – Array of size M by N containing the constraints. The constraints are of the form

where

denotes the i-th constraint. (Input)

B – Array of size M containing the right-hand sides of the constraints. (Input)

RHOBEG – The initial value of a trust region radius, 0 < RHOEND <= RHOBEG. Typically, RHOBEG should be about 1/10 of the greatest expected change to a variable. (Input)

RHOEND – The final value of a trust region radius, 0 < RHOEND <= RHOBEG. Variable RHOEND should indicate the accuracy that is required in the final values of the variables. (Input)

X – Array of size N containing the computed solution. (Output)

Optional Arguments

M – Number of constraints. (Input)
Default: M = SIZE (A,1).

N – Number of variables. (Input)
Default: N = SIZE (X,1).

IPRINT – Parameter indicating the desired output level. (Input)

IPRINT	Action
0	No output printed
1	Output printed only upon return from LIN_CON_TRUST_REGION.
2	The best feasible vector of variables so far and the corresponding value of the objective function are printed whenever RHO is re-duced, where RHO is the current lower bound on the trust region radius.
3	Output each new value of FVALUE with its variables.

Default: IPRINT = 0.

XGUESS – Array of size N that contains an initial guess to the minimum. If the initial guess is not feasible, then it is replaced by a feasible starting point determined as the solution of a constrained linear least-squares problem. (Input)
Default: XGUESS = 0.0.

MAXFCN – On input, maximum allowed number of function evaluations. (Input/Output)
On output, actual number of function evaluations needed.
Default: MAXFCN = 200.

FVALUE – Function value at the computed solution. (Output)

FORTRAN 90 Interface

Generic: CALL LIN_CON_TRUST_REGION (FCN, NPT, A, B, RHOBEG, RHOEND, X [, …])

Specific: The specific interface name is D_LIN_CON_TRUST_REGION. This subroutine is available in double precision only.

Description

The routine LIN_CON_TRUST_REGION implements a trust-region method that forms quadratic models by interpolation to solve linearly constrained optimization problems of the form

where

is a function of n variables,

is the constraint matrix,

and

Usually, many degrees of freedom remain in each new model after satisfying the interpolation conditions. These remaining degrees of freedom are taken up by minimizing the Frobenius norm of the change to the second derivative matrix of the model, see Powell (2004).

One new function value is calculated at each iteration, usually at a point where the current model predicts a reduction in the least value so far reached by the objective function subject to the linear constraints. Alternatively, the algorithm may choose a new vector of variables to replace an interpolation point that is too far away for reliability, in which case this new point need not satisfy the linear constraints.

Routine LIN_CON_TRUST_REGION is based on the LINCOA algorithm by Michael J.D. Powell (2014).

Comments

1. Informational errors

Type	Code	Description
4	1	A row of input matrix A is equal to zero.
4	2	The problem is infeasible.
4	3	The maximum number of function evaluations is exceeded.
4	4	Computer rounding errors prevent further refinement of X.
4	5	Algorithm has stopped because the denominator of the updating formula is zero.

2. Since LIN_CON_TRUST_REGION uses only function-value information at each step to determine a new approximate minimum, it could be quite inefficient on smooth problems compared to other methods, such as those implemented in routine LCONF, which takes into account derivative information at each iteration. Hence, routine LIN_CON_TRUST_REGION should be used only as a last resort if derivatives are available.

Example

In this example, Rosenbrock’s post office problem,

subject to

is solved with an initial feasible guess (10.0, 10.0, 10.0), and the solution is printed.

USE LIN_CON_TRUST_REGION_INT

USE UMACH_INT

IMPLICIT NONE

! Variable declarations

INTEGER, PARAMETER :: M = 8, N = 3, NPT = 7

INTEGER :: K, NOUT

DOUBLE PRECISION :: RHOBEG, RHOEND, FVALUE

DOUBLE PRECISION :: A(M,N), B(M), X(N)

! Initialization (feasible starting point)

! XGUESS = (10.0, 10.0, 10.0)

DOUBLE PRECISION :: XGUESS(N) = (/ 10.0, 10.0, 10.0 /)

EXTERNAL FCN

RHOBEG = 1.0D0

RHOEND = 1.0D-9

A(:,1) = (/ 1.0, -1.0, 1.0, -1.0, 0.0, 0.0, 0.0, 0.0 /)

A(:,2) = (/ 2.0, -2.0, 0.0, 0.0, 1.0, -1.0, 0.0, 0.0 /)

A(:,3) = (/ 2.0, -2.0, 0.0, 0.0, 0.0, 0.0, 1.0, -1.0 /)

B(:) = (/ 72.0, 0.0, 42.0, 0.0, 42.0, 0.0, 42.0, 0.0 /)

CALL LIN_CON_TRUST_REGION (FCN, NPT, A, B, RHOBEG, RHOEND, X, &

XGUESS=XGUESS, FVALUE=FVALUE)

CALL UMACH (2, NOUT)

WRITE (NOUT, 99999) (X(K),K=1,N), FVALUE

99999 FORMAT (' The best estimate for the minimum value of the', /, &

' function is X = (', 3(2X,F5.2), ')', /, ' with ', &

'function value FVALUE = ', E13.6)

END

! External function to be minimized

SUBROUTINE FCN (N, X, F)

INTEGER :: N

DOUBLE PRECISION :: X(N), F

F = -X(1) * X(2) * X(3)

RETURN

END

Output

The best estimate for the minimum value of the

function is X = ( 24.00 12.00 12.00)

with function value FVALUE = -0.345600E+04