min_con_lin_trust_region
Minimizes a function of n variables subject to linear constraints using a derivative-free, interpolation-based trust-region method.
NOTE: Function min_con_lin_trust_region is available in double precision only. |
Synopsis
#include <imsl.h>
double *imsl_d_min_con_lin_trust_region (void fcn(), int n, int npt,int m,double a[],double b[],double rhobeg,double rhoend,…, 0)
Required Arguments
void fcn (int n, double x[], double *f) (Input/Output)
User-supplied function to evaluate the function to be minimized.
User-supplied function to evaluate the function to be minimized.
Arguments
int n (Input)
Length of x.
Length of x.
double x[] (Input)
Array of length n, the point at which the function is evaluated.
Array of length n, the point at which the function is evaluated.
double *f (Output)
The computed function value at the point.
The computed function value at the point.
int n (Input)
Number of variables, n ≥ 2.
Number of variables, n ≥ 2.
int npt (Input)
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.
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.
int m (Input)
Number of constraints.
Number of constraints.
double a[] (Input)
Array of size m by n containing the constraints. The constraints are of the form
,
where denotes the i-th constraint.
Array of size m by n containing the constraints. The constraints are of the form
,
where denotes the i-th constraint.
double b[] (Input)
An array of size m containing the right-hand sides of the constraints.
An array of size m containing the right-hand sides of the constraints.
double rhobeg (Input)
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.
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.
double rhoend (Input)
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.
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.
Return Value
An array of length n containing the best estimate for the minimum. To release this space, use imsl_free. If no solution was computed, then NULL is returned.
Synopsis with Optional Arguments
#include <imsl.h>
double * imsl_d_min_con_lin_trust_region (void fcn(), int n, int npt, int m,double a[],double b[],double rhobeg,double rhoend,
IMSL_XGUESS, double xguess[],
IMSL_PRINT, int iprint,
IMSL_MAX_FCN, int *maxfcn,
IMSL_FVALUE, double *fvalue,
IMSL_RETURN_USER, double x[],
IMSL_FCN_W_DATA, double fcn(),void *data,
0)
Optional Arguments
IMSL_XGUESS, double xguess[] (Input)
An array of length 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.
Default: xguess = 0.0
An array of length 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.
Default: xguess = 0.0
IMSL_MAX_FCN, int *maxfcn (Input/Output)
On input, maximum allowed number of function evaluations. On output, actual number of function evaluations needed.
Default: maxfcn = 200
On input, maximum allowed number of function evaluations. On output, actual number of function evaluations needed.
Default: maxfcn = 200
IMSL_PRINT, int iprint (Input)
Parameter indicating the desired output level.
Parameter indicating the desired output level.
iprint | Action |
|---|---|
0 | No output printed |
1 | Output only upon return from imsl_d_min_con_lin_trust_region. |
2 | The best feasible vector of variables so far and the corresponding value of the objective function are printed whenever rho is reduced, where rho is the current lower bound on the trust region radius. |
3 | Output each new value of F with its variables. |
Default: iprint = 0
IMSL_FVALUE, double *fvalue (Output)
Function value at the computed solution.
Function value at the computed solution.
IMSL_RETURN_USER, double x[] (Output)
User-supplied array of length n containing the computed solution.
User-supplied array of length n containing the computed solution.
IMSL_FCN_W_DATA, void fcn (int n, double x[], double *f, void *data) (Input)
void fcn (int n, double x[],double *f, void *data) (Input)
User supplied function to evaluate the function to be minimized. This function also accepts a pointer to data supplied by the user. data is a pointer to the data to be passed to the user-supplied function. See Passing Data to User-Supplied Functions in this manual’s introduction for more details.
User supplied function to evaluate the function to be minimized. This function also accepts a pointer to data supplied by the user. data is a pointer to the data to be passed to the user-supplied function. See Passing Data to User-Supplied Functions in this manual’s introduction for more details.
Arguments
int n (Input)
Length of x.
Length of x.
double x[] (Input)
Array of length n, the point at which the function is evaluated.
Array of length n, the point at which the function is evaluated.
double *f (Output)
The computed function value at the point.
The computed function value at the point.
void *data (Input)
A pointer to the data to be passed to the user-supplied function.
A pointer to the data to be passed to the user-supplied function.
Description
The function imsl_d_min_con_lin_trust_region implements a trust region method that forms quadratic models by interpolation to minimize a multivariate function, subject to general linear inequality constraints.
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.
Function imsl_d_min_con_lin_trust_region is based on the LINCOA algorithm by Michael J.D. Powell (2014).
Example
In this example, Rosenbrock’s post office problem,
subject to
is solved using an initial guess of . The solution and optimal value are printed.
#include <imsl.h>
#include <stdio.h>
int main()
{
void fcn_post_office(int, double *, double *);
int n = 3, npt = 7, m = 8;
double rhobeg = 1.0, rhoend = 1.e-9, fvalue;
double *x = NULL;
double a[] = { 1.0, 2.0, 2.0,
-1.0, -2.0, -2.0,
1.0, 0.0, 0.0,
-1.0, 0.0, 0.0,
0.0, 1.0, 0.0,
0.0, -1.0, 0.0,
0.0, 0.0, 1.0,
0.0, 0.0, -1.0 };
double xguess[] = { 10.0, 10.0, 10.0 };
double b[] = { 72.0, 0.0, 42.0, 0.0, 42.0, 0.0, 42.0, 0.0 };
x = imsl_d_min_con_lin_trust_region(fcn_post_office, n, npt, m, a, b,
rhobeg, rhoend,
IMSL_FVALUE, &fvalue,
IMSL_XGUESS, xguess,
0);
imsl_d_write_matrix("Solution", 1, n, x, 0);
printf("\nObjective value = %f\n", fvalue);
if (x) imsl_free(x);
}
void fcn_post_office(int n, double *x, double *f)
{
*f = -x[0] * x[1] * x[2];
}
Output
Solution
1 2 3
24 12 12
Objective value = -3456.000000
Fatal Errors
IMSL_FCN_EVAL_EXCEEDED_MAXFCN | Maximum number of function evaluations exceeded. |
IMSL_PROB_INFEASIBLE | The problem is infeasible. |
IMSL_CONSTR_GRAD_ZERO | Algorithm has stopped because the gradient of a constraint is zero. |
IMSL_ROUNDING_ERRORS_IN_X | Computer rounding errors prevent further refinement of "x". |
IMSL_DENOMINATOR_ZERO | Algorithm has stopped because the denominator of the updating formula is zero. |
IMSL_STOP_USER_FCN | Request from user-supplied function to stop algorithm. User flag = "#". |
