The CONSTRAINED_MIN procedure solves nonlinear optimization problems of the following form:
Minimize or maximize gp(X), subject to:
glb_{i} ≤ g_{i}(X) ≤ gub_{i} for i = 0,...,nfuns-1, i ≠ p
xlb_{j} ≤ x_{j} ≤ xub_{j} for j = 0,...,nvars-1
X is a vector of nvars variables, x_{0} ,...,x_{nvars}-1, and G is a vector of nfuns functions g_{0 },...,g_{nfuns}-1, which all depend on X. Any of these functions may be nonlinear. Any of the bounds may be infinite and any of the constraints may be absent. If there are no constraints, the problem is solved as an unconstrained optimization problem. The program solves problems of this form by the Generalized Reduced Gradient Method. See References 1-4.
CONSTRAINED_MIN uses first partial derivatives of each function g_{i} with respect to each variable x_{j}. These are automatically computed by finite difference approximation (either forward or central differences).
CONSTRAINED_MIN is based on an implementation of the GRG algorithm supplied by Windward Technologies, Inc. See Reference 11.
Example
This example has 5 variables {X0, X1, ..., X4}, bounded above and below, a quadratic objective function {G3}, and three quadratic constraints {G0, G1, G2}, with both upper and lower bounds. See the Himmelblau text [7], problem 11.
Minimize:
G3 = 5.3578547X2X2 + 0.8356891X0X4 + 37.293239X0 - 40792.141
Subject to:
0 < G0 = 85.334407 + 0.0056858X1X4 + 0.0006262X0X3 - 0.0022053X2X4 < 92
90 < G1 = 80.51249 + 0.0071317X1X4 + 0.0029955X0X1 + 0.0021813X2X2 <110
20 < G2 = 9.300961 + 0.0047026X2X4 + 0.0012547X0X2 + 0.0019085X2X3 < 25
and,
78 < X0 < 102
33 < X1 < 45
27 < X2 < 45
27 < X3 < 45
27 < X4 < 45
This problem is solved starting from X = {78, 33, 27, 27, 27} which is infeasible because constraint G2 is not satisfied at this point.
The constraint functions and objective function are evaluated by HMBL11:
; Himmelblau Problem 11
; 5 variables and 4 functions
FUNCTION HMBL11, x
g = DBLARR(4)
g[0] = 85.334407 + 0.0056858*x[1]*x[4] + 0.0006262*x[0] $
*x[3] - 0.0022053*x[2]*x[4]
g[1] = 80.51249 + 0.0071317*x[1]*x[4] + 0.0029955*x[0] $
*x[1] + 0.0021813*x[2]*x[2]
g[2] = 9.300961 + 0.0047026*x[2]*x[4] + 0.0012547*x[0]* $
x[2] + 0.0019085*x[2]*x[3]
g[3] = 5.3578547*x[2]*x[2] + 0.8356891*x[0]*x[4] $
+ 37.293239*x[0] - 40792.141
RETURN, g
END
; Example problem for CONSTRAINED_MIN
; Himmelblau Problem 11
; 5 variables and 3 constraints
; Constraints and objective defined in HMBL11
xbnd = [[78, 33, 27, 27, 27], [102, 45, 45, 45, 45]]
gbnd = [[0, 90, 20, 0], [92, 110, 25, 0 ]]
nobj = 3
gcomp = 'HMBL11'
title = 'IDL: Himmelblau 11'
report = 'hmbl11.txt'
x = [78, 33, 27, 27, 27]
CONSTRAINED_MIN, x, xbnd, gbnd, nobj, gcomp, inform, $
REPORT = report, TITLE = title
g = HMBL11(x)
; Print minimized objective function for HMBL11 problem:
PRINT, g[nobj]
Syntax
CONSTRAINED_MIN, X, Xbnd, Gbnd, Nobj, Gcomp, Inform [, EPSTOP=value] [, LIMSER=value] [, /MAXIMIZE] [, NSTOP=value] [, REPORT=filename] [, TITLE=string]
Arguments
X
An nvars-element vector. On input, X contains initial values for the variables. On output, X contains final values of the variable settings determined by CONSTRAINED_MIN.
Xbnd
Bounds on variables. Xbnd is an nvars x 2 element array.
- Xbnd[j,0] is the lower bound for variable x[j].
- Xbnd[j,1] is the upper bound for variable x[j].
- Use -1.0e30 to denote no lower bound and 1.0e30 for no upper bound.
Gbnd
Bounds on constraint functions. Gbnd is an nfuns x 2 element array.
- Gbnd[i,0] is the lower bound for function g[i].
- Gbnd[i,1] is the upper bound for function g[i].
- use -1.0e30 to denote no lower bound and 1.0e30 for no upper bound.
Bounds on the objective function are ignored; set them to 0.
Nobj
Index of the objective function.
Gcomp
A scalar string specifying the name of a user-supplied IDL function. This function must accept an nvars-element vector argument x of variable values and return an nfuns-element vector G of function values.
Inform
Termination status returned from CONSTRAINED_MIN.
Inform value |
Message |
0 |
Kuhn-Tucker conditions satisfied. |
1 |
Fractional change in objective less than EPSTOP for NSTOP consecutive iterations. See Keywords below. |
2 |
All remedies have failed to find a better point. |
3 |
Number of completed 1-dimensional searches exceeded LIMSER. See Keywords below. |
4 |
Objective function is unbounded. CONSTRAINED_MIN has observed dramatic change in the objective function over several steps. This is a good indication that the objective function is unbounded. If this is not the case, the user should check functions and bounds for consistency. |
5 |
Feasible point not found. |
6 |
Degeneracy has been encountered. |
7 |
Noisy and nonsmooth function values. Possible singularity or error in the function evaluations. |
8 |
Optimization process terminated by user request. |
9 |
Maximum number of function evaluations exceeded. |
–1 |
Fatal Error. Some condition, such as nvars < 0, was encountered. CONSTRAINED_MIN documented the condition in the report and terminated. In this case, the user needs to correct the input and rerun CONSTRAINED_MIN. |
–2 |
Fatal Error. The report file could not be opened. Check the filename specified via the REPORT keyword, and make sure you have write privileges to the specified path. |
–3 |
Fatal Error. Same as Inform = –1. In this case, the REPORT keyword was not specified. Specify the REPORT keyword and rerun CONSTRAINED_MIN, then check the report file for more detail on the error. |
Keywords
EPSTOP
Set this keyword to specify the CONSTRAINED_MIN convergence criteria. If the fractional change in the objective function is less than EPSTOP for NSTOP consecutive iterations, the program will accept the current point as optimal. CONSTRAINED_MIN will accept the current point as optimal if the Kuhn-Tucker optimality conditions are satisfied to EPSTOP. By default, EPSTOP = 1.0e-4.
LIMSER
If the number of completed one dimensional searches exceeds LIMSER, CONSTRAINED_MIN terminates and returns inform = 3. By default: LIMSER = 10000.
MAXIMIZE
By default, the CONSTRAINED_MIN procedure performs a minimization. Set the MAXIMIZE keyword to perform a maximization instead.
NSTOP
Set this keyword to specify the CONSTRAINED_MIN convergence criteria. If the fractional change in the objective function is less than EPSTOP for NSTOP consecutive iterations, CONSTRAINED_MIN will accept the current point as optimal. By default, NSTOP = 3.
REPORT
Set this keyword to specify a name for the CONSTRAINED_MIN report file. If the specified file does not exist, it will be created. Note that if the file cannot be created, no error message will be generated. If the specified file already exists, it will be overwritten. By default, CONSTRAINED_MIN does not create a report file.
TITLE
Set this keyword to specify a title for the problem in the CONSTRAINED_MIN report.
References
1. Lasdon, L.S., Waren, A.D., Jain, A., and Ratner, M., “Design and Testing of a Generalized Reduced Gradient Code for Nonlinear Programming”, ACM Transactions on Mathematical Software, Vol. 4, No. 1, March 1978, pp. 34-50.
2. Lasdon, L.S. and Waren, A.D., “Generalized Reduced Gradient Software for Linearly and Nonlinearly Constrained Problems”, in “Design and Implementation of Optimization Software”, H. Greenberg, ed., Sijthoff and Noordhoff, pubs, 1979.
3. Abadie, J. and Carpentier, J. “Generalization of the Wolfe Reduced Gradient Method to the Case of Nonlinear Constraints”, in Optimization, R. Fletcher (ed.), Academic Press London; 1969, pp. 37-47.
4. Murtagh, B.A. and Saunders, M.A. “Large-scale Linearly Constrained Optimization”, Mathematical Programming, Vol. 14, No. 1, January 1978, pp. 41-72.
5. Powell, M.J.D., “Restart Procedures for the Conjugate Gradient Method,” Mathematical Programming, Vol. 12, No. 2, April 1977, pp. 241-255.
6. Colville, A.R., “A Comparative Study of Nonlinear Programming Codes,” I.B.M. T.R. no. 320-2949 (1968).
7. Himmelblau, D.M., Applied Nonlinear Programming, McGraw-Hill Book Co., New York, 1972.
8. Fletcher, R., “A New Approach to Variable Metric Algorithms”, Computer Journal, Vol. 13, 1970, pp. 317-322.
9. Smith, S. and Lasdon, L.S., Solving Large Sparse Nonlinear Programs Using GRG, ORSA Journal on Computing, Vol. 4, No. 1,Winter 1992, pp. 1-15.
10. Luenbuerger, David G., Linear and Nonlinear Programming, Second Edition, Addison-Wesley, Reading Massachusetts, 1984.
11. Windward Technologies, GRG2 Users’s Guide, 1997.
Version History
5.1 |
Introduced |