HULDRA is a library of subroutines, callable from Fortran, C and C++, to carry out rotational- discrimination non-linear regression analysis (optimization.) This library of subroutines was written by John H. Letcher Professor of Computer Science of the University of Tulsa and President of Synergistic Consultants Incorporated
In Teutonic mythology, Huldra is the Goddess who is always aspiring to
the unattainable. SCI felt that this name was appropos for this tool.
HULDRA is a nonlinear optimizer enabling the user to determine an optimum
numerical solution to a problem. The user must quantitatively specify the
variables to be considered in the solution of the problem, the goals or
objectives that he wishes to achieve and the values of functions defined in
terms of the variables (objectives)
variables and the objectives must be defined. These are designated to the
system as ELEMENTS, OBJECTIVES, and the VALUE subroutine, respectively. The
system calculates the values of the elements to produce the best fit to the
specified objectives. The parameters to drive the calculation are given as a
set of concise commands.
The functional relationships are expressed by way of a FORTRAN-77 or C
subroutine, called VALUE. These may be as complicated as is required to state
the problem. The restriction must be obeyed that each objective must be
differentiable (in the mathematical sense); other than that single restriction
the evaluation may be extraordinarily complex even including calls to data base
access subroutines for supporting information.
The act of performing the optimization is an affair independent of the
statement of the problem as the choice of goals and the degree of constraint
on the elements is not known at the time of the statement of the problem.
Therefore, to use a previously defined problem, the user need not know FORTRAN
or any computer language. The terse HULDRA operating commands are easily
understood and used.
HULDRA operates in an interactive (conversational) mode as well as in
the batch mode so that planners can test different assumptions and approaches
and obtain results in real time.
General system features are:
1. The functional relationships between the elements and objectives
may be nonlinear. This removes a primary restriction of linear
programming systems and permits consideration of 'real world'
problems.
[. The chosen elements need not be linearly independent. In complicated
problems, it is seldom known at the onset the relationships, if any
between the 'independent variables' (elements).
3. The calculational procedure is independent of the elements upon
which optimization is to be performed. For example, the system could
be used for the optimization of land use and allocation of money in
separate programs with a common language and a common output format
to preclude any confusion in the interpretation of the results of
the optimization procedure.
4. The system user is able to define bounds on the magnitude of the value
of an element irrespective of the magnitude that would have been
calculated in an unconstrained optimization.
5. Relative weights are given to each objective to give priorities that
the calculational procedure obeys in case all of the defined
objectives cannot be realized.
6. HULDRA will not diverge; that is, it is impossible to formulate a
problem that will cause the final values to be further from the
specified objectives than their starting points.
7. The size of the problems considered is limited primarily by the
computer memory available. For a microcomputer, such as an IBM PC
a problem with [0 elements and 10 objectives can be specified.
For larger computers such as IBM 370 series or CDC 6000 series
problems of virtually unlimited size may be specified. The solution
algorithm is efficient in terms of calculation time.
8. The HULDRA System approaches a solution in steps. That is, after one
step (called an iteration) the values of all of the elements may
change and the calculated values of the objective functions are closer
to the desired values than in the previous step. That is, HULDRA
is said to be an iterative process. The results at each step may be
meaningful, per se. Iteration to completion need not be
accomplished to give useful information to the user.
The following sections discuss the mathematic formulation of the problem
within the system, problem specification to the system, system commands, error
messages, and a sample problem illustrating the techniques of system
utilization.
1. Mathematical Formulation
------------------------
The planning system is a solution technique for a problem well known
in the mathematical literature. In terms of a set of elements
X*, (X) = X , it is presumed that a set of objective functions F
~ ~ i i ~
(F)ð ä f can be defined with good accuracy in terms of the values of
~ ij
the elements, X. The purpose of the calculational procedure is to minimize
~
the difference between the calculated value of these objective functions and
the defined goals, G , by minimizing the calculated value of a total
~
objective function, Q, given in terms of the individual objective functions
goals, and weights by the following:
Q = 1/2 ä W (F -G ) .
j j j j
* The symbol X represents a sequence of values X , X , ..., X usually
~
represented as a column matrix. The symbol (X) represents the ith element
~ i
of the matrix values.
The weights, W, offer relative importance factors to each of the defined
~
objectives. An element is an entity characterized by a set of attributes:
its value is X ; the maximum value that this entity should be allowed to attain
i
is XMAX ; the minimum value that the quantity should attain is XMIN .
i i
The basic algorithm for the carrying out of this procedure is given in
Reference 1. This algorithm is extremely efficient; however, if used directly
it embodies all of the problems associated with numerical differentiation of
functions on a digital computer.
Sensitivity coefficients can be defined which give to the system user
a figure of merit of the anticipated change that one would expect in the
calculated value of a single objective function in terms of minor variations
of the calculated value of each X. Mathematically, these are the partial
derivatives of f with respect to X ( ëf/ëX ), and are shown as a part of the
derivation in Reference 1. ~
Two of the attributes associated with each element are the maximum and
minimum values that each element can attain within the course of the
calculation. This is true rigorously where indeed the value may not exceed
the bounds of these quantities to any extent (hard boundary conditions).
2. Problem Specification
---------------------
The specificaton of any problem for HULDRA requires only three types of
input parameters: ELEMENT, OBJECTIVE, and Objective function specification.
It is in the specification of these parameters that the planner's knowledge of
his particular problem is implemented. He must know what his real goals are
what techniques are to be considered to achieve these goals, and, perhaps most
importantly, the approximate relationship between the techniques and the goal.
To reiterate, the HULDRA System is designed to find the optimum combination of
many alternative techniques to achieve particular goals. However, the basic
relationship between the technique and the goal is the responsibility of the
planner. This relationship should be understood to solve the problem in any
manner, but use of the HULDRA system forces the planner to quantitatively
define the interaction. Since the relationships are easily changed and the
computer is very fast, a variety of assumptions can be tested in a few minutes
once the basic problem has been defined to the machine. In this manner the
degree of criticalness of the assumptions can be determined and primary
attention given to verifying the validity of the dominant ones.
2.1 ELEMENT
-------
Each problem is formulated as a set of independent variables called
elements.
In addition to its arbitrarily chosen element number, the starting value
as well as the maximum and minimum permissible values for each element must
be specified to the system. In complicated problems there is the possibility
of multiple peaks with different values for the objectives. To insure that
such a situation does not exist, it is 'good form' to start the solution at
several different points and verify that identical results are obtained.
Specification of maximum and minimum element values keeps the results
obtained physically realizable.
With the HULDRA programs the values of the objective functions F (X) are
evaluated. Furthermore, the partial derivative of each objective function
with respect to each independent variable X by the following expression:
ëF / ëX = (F(X = X +á ) - F(X =X -á ) / 2
j i i i i i i i i
The increment á must be explicitly specified for each X as the sixth word
i i
in the ELEMENT Command which is described later. The above states that the
technique of central differences is used in the evaluation of all partial
derivatives within HULDRA.
An optional specification to the HULDRA system is for particular elements
to be held constant. This can be done for any element, simply by specifying
a sixth word in the ELEMENT command.
2.2 OBJECTIVE
---------
Specification of the objectives to the system defines the goals of the
planning process. Three quantities must be specified for each objective - a
number, a value which is the 'goal', and a relative importance factor called
its weight. These are discussed in the following paragraphs.
The number is assigned for bookkeeping purposes, just as was done for
each element. There are no conventions or rules for the numbering sequence.
A particular element can have multiple objective values associated with
it.
Specification of a weight for each objective allows the planner to place
a judgement on its relative importance. However, this is not as
straightforward as it would at first appear. As is shown in Appendix B, the
HULDRA calculational procedure sums the products of the weight and the square
of the difference between the goal and the current value for each of the
objectives. The purpose of the HULDRA system is to minimize the value of this
total objective function, which is an inherently positive number. Obviously
if the goals are perfectly achieved, the quantity becomes zero. The reason
selection of the weight may not be so obvious is that the total objective
function contains the product of the weight and the square of the difference
from each of the goals. If the size of the objectives varies greatly
minimizing the total objective function favors the objectives with the largest
values. Thus, assigning each objective a weight of unity may in actuality
result in a large discrepancy in the relative importance of each goal. This is
particularly important when the goals cannot all be achieved. However, by
varying the relative weights of the objectives, achievement of a particular
goal can be easily emphasized.
3. Commands
--------
The commands to manipulate the HULDRA System are summarized in Table 1
and are discussed below. Examples of their use are given in Section 6.
3.1 ELEMENT
-------
This command is used to specify the element paramters to the system.
The entries after the word ELEMENT are in free field format, i.e. they may
be separated by spaces or commas. They may be expressed in fixed, floating
point, or integer format. The first entry (second word) is the element number
the second its initial or starting value, the third its minimum allowed value
the fourth its maximum allowed value, and the fifth word is the increment, .
If the element is to be held constant, the sixth entry is followed with a
space and an asterisk or any nonblank printing character. If a descriptive
label is desired one can be added at the end of the line.
3.2 OBJECTIVE
---------
This command is used to specify the objectives to be achieved in the
optimization. The entries after the word OBJECTIVE are the objective number
its value, and its weight. The same general considerations apply as those for
the ELEMENT command.
3.3 The VALUE Subroutine
--------------------
The functional relationships between the objective functions F and the
j
variables X are expressed by the user as a FORTRAN-77 Subroutine called
i
VALUE with the following structure:
SUBROUTINE VALUE(F,J)
COMMON/XVAL/X([0)
NOBJ=J
GO TO (1,2, ... ),NOBJ
1 F= (the value of objective function 1 in terms of X )
RETURN
2 F= (the value of objective function 2 in terms of X )
.
.
RETURN
END
The HULDRA System is supplied to the user as an object module with one
unsatisfied external with the name VALUE.
The user must compile and link edit his subroutine to produce the load
module HULDRA with its entry point into the HULDRA Driver (Command Processor).
HULDRA calls the subroutine VALUE in the act of solving the user's current
problem.
Even in the smallest microprocessors such as the IBM PC, the subroutine
(and the set of user supplied subroutines called VALUE, if desired) may
employ as much as 400K bytes of memory (in a 640K byte machine)
very large problems indeed may be posed.
3.4 ACTIVATE INPUT [filename]
-------------------------
This command specifies a previously defined problem file to the HULDRA
System. The file will normally include specification of all the elements and
objectives, and it may also include ITERATE and REPORT commands to allow a
predetermined sequence of computations.
The basic usefulness of the command is to minimize the problem definition
time. Modification to elements, objectives, or functions is accomplished by
simply redefining them with new statement.
3.5 ACTIVATE OUTPUT [filename]
--------------------------
Whenever the normal output is to be stored for future use, the ACTIVATE
OUTPUT command is used to store in the file called filename whatever would
have been displayed on the operator's console. To stop this process the user
may issue the command:
ACTIVATE OUTPUT NUL
3.6 ITERATE [N1] [N2] [N3]
----------------------
The ITERATE command causes the HULDRA System to perform the optimization
process, carrying it through N1 iteration cycles, starting with an initial value
for h (see Reference 1) of N2 , and displaying information in accordance with
code N3 at the end of each cycle. During each cycle the system varies the
element values to obtain closer and closer fits to the desired objectives. The
number 0 is a valid entry for N1. When it is specified, no optimization is
performed, but information may be displayed by use of appropriate codes for N3.
This is useful because a minimum of information is usually desired during the
iteration process. However, when a solution has apparently been reached
complete information is usually desired and can be obtained.
The value for h is approximately 1.0 when a solution is reached. However
its value varies with the scaling of the problem and experimentation may be
required to find the optimal solution. As a general rule, the value of 0.125
should be given.
Table 2 summarizes the output data obtainable with the various codes for
N3. These will all be illustrated in the sample problem in Section 6. In
addition to the code numbers shown, the sum of any of these numbers may also
be specified. In that case the information obtained with each number forming
the sum is displayed. For example, entering 3 results in the values of the
total objective function, its change during the last iteration and its current
value being printed. By the construction of the code, any number from 0 to 255
may be entered, and each will result in an information display unique to that
number. The data obtained with code numbers 2 and 16 are dynamic data and are
obtained only during the iteration cycles. The data obtained with the
remaining codes may be obtained at any time during the calculations. Figure 1
shows the sample output of a HULDRA run.
3.7 REPORT [N1]
-----------
To determine the values of any of the significant factors known to the
system, the REPORT command causes them to be printed. Which factors are printed
is determined by the value of N1 which is an Output Specification Code as given
in Table 2. Zero values are not usually printed to make the reports more
concise.
3.8 RESET
-----
The RESET verb prepares the system to accept a new value for its
numerical precision. This factor, called SIGNIF is set at the numerical
precision of the computer upon installation of the HULDRA System. This is the
smallest value (with respect to unity) that is considered to have numerical
significance (1.0E-08)
entered and the system responds:
ENTER SIGNIF .
The new value is then entered, and this value is used in the calculations until
the system is exited. SIGNIF then reverts to its preset value.
3.9 EXIT
----
EXIT removes the planner from the HULDRA System so that a new system
may be defined to the computer, or operation may be terminated.
4. Error Messages
--------------
Two types of error messages may be received. When an entry error is
detected by the HULDRA System, the message
AN ERROR WAS FOUND IN WORD - (word)
is printed. The output (word) is the element of the command in which an error
was first discovered. The error may be due to any of the following:
1. Misspelled, missing, or illegal verb
[. Problem specifier (ELEMENT or OBJECTIVE) misspelled
3. Problem data incorrectly entered or missing
4. Problem file invalid or incorrectly entered
5. Data transmission error
6. An attempt is made to specify too many ELEMENTS or OBJECTIVES
Table 1
THE HULDRA COMMANDS
-------------------
Command Action
ELEMENT [N1][N[][N3][N4][N5] Specifies element N1, starting value N2
minimum value N3, maximum value N4, and á = N5.
(specifying seven words holds this variable
constant).
OBJECTIVE [N1][N2][N3] Specified objective N1 with N2 and weight N3 .
ACTIVATE INPUT [filename] Specifies previously defined problem file.
ACTIVATE OUTPUT [filename] Saves the report for future use.
ITERATE [N1][N[][N3] Causes optimization to be performed for N1 cycle
with an initial value of h (see Reference 1) given
as N2, and with results displayed in accordance
with a code number N3 (see Table [).
REPORT {N1} Generates an output Report in accordance with
code number N1 or 63, if not specified.
RESET Prepares the system to receive a new value for
SIGNIF, the numerical accuracy of the calculations.
EXIT Causes access to the system to be terminated.
Notes:
{ } Optional entry.
[ ] Defines single entry.
Table [
THE OUTPUT SPECIFICATION CODES*
------------------------------
Code Number Information
1 Total objective function, Q.
2 Change during last iteration of total objective
function, current value of Q.
4 Element values, derivative of total objective
function with respect to each element, minimum
element values, minimum value, maximum element
values.
8 Function (objective) values with corresponding
goals and weights.
16 Change during last iteration of element values
and Eigenvalues of the appropriate Hessian
matrix (see Reference 1).
32 Sensitivity (derivative) of each function to
each element. ëF /ëX
j i
64 The nonzero values of the Hessian matrix.
128 The nonzero values of the Eigenfunction matrix.
* To select those options desired, the user sums the code numbers listed
and gives this numbers as the value of N3 in the ITERATE command.
REPORT COMMAND NUMBER
---------------------
Value Items Reported
1 Q =
2 DQ = Q =
4 I X(I) DQ/DX(I) MINIMUM VALUE MAXIMUM VALUE
8 J F(J) G(J) W(J)
16 I DX(J) EIVS(I)
32 I DF(J)/DX(I)
64 S(I,K) =
128 EIFS(I,K) =