share/calculus/optmiz.usg

   1
   2 This file describes how to use a MACSYMA analytic optimization package
   3 written by David R. Stoutemyer, (login name: STOUTE), Electrical
   4 Engineering Department, University of Hawaii, April, 1974. The package
   5 is designed to find the stationary points of a multivariate objective
   6 function, either unconstrained or subject to equality &/or inequality
   7 constraints.  Suggestions, questions, and interesting successful or
   8 unsuccessful examples are welcome.
   9
  10                          OTHER RELEVANT FILES:
  11    OPTMIZ >  is a MACSYMA batch file containing the functions and
  12       option settings for optimization.
  13    OPTMIZ DEMO  is a MACSYMA batch file demonstrating various ways
  14       of using the optimization functions.
  15    OPTMIZ OUTPUT  is a text file listing  OPTMIZ DEMO together with the
  16       output that it produces when executed.
  17
  18                                 USAGE:
  19 In MACSYMA, first type
  20
  21                BATCH(OPTMIZ, ">", DSK, SHARE2);
  22
  23 Next, if interested in executing the demonstration with
  24 opportunities for interaction, type
  25
  26                DEMO(OPTMIZ, DEMO, DSK, SHARE2);
  27
  28 or if interested in executing the demonstration without
  29 opportunities for interaction, type
  30
  31                BATCH(OPTMIZ, DEMO, DSK, SHARE2);
  32
  33 Alternatively, or afterward, to try an example of your own, type
  34
  35                STAP(OBJECTIVE, LEZEROS, EQZEROS, DECISIONVARS);
  36
  37 OBJECTIVE is an expression denoting the objective function or the
  38    label of such an expression.
  39 LEZEROS is a list of expressions which are constrained to be less
  40    than or equal to zero.  Use [] if no such constraints.
  41 EQZEROS is a list of expressions which are constrained to equal zero, or
  42    the label of such a list.  Use [] if there are no such constraints.
  43 DECISIONVARS is a list of the decision variables or the label of
  44    such a list.  May use [] if all variables in objective and
  45    constraints are decision variables.
  46
  47 For convenience, brackets may be omitted from one-expression lists, and
  48    trailing [] arguments may be omitted.
  49
  50 Global variables that you may wish to inspect, particularly in the
  51    event of an error interrupt, or if a suspected stationary point
  52    is not found, or if you have interrupted an analysis that is
  53    taking an unexpectedly long time to execute:
  54       LAGRANGIAN  is the Lagrangian expression,
  55       GRAD  is a list of components of the gradient of the Lagrangian,
  56       GRADSUB  is GRAD evaluated at a stationary point.
  57       STAPTS is a list of lists of equations, with each
  58          equation representing one component of a solution in the form
  59          decisionvariable = expression.
  60       BHESS  is the Hessian matrix  with respect to the decision and
  61          slack variables, minus EIGEN times the
  62          identity matrix, bordered to the right with columns consisting
  63          of gradients of the expressions constrained to be less than
  64          or equal to zero, then gradients of the expressions constrained
  65          to equal zero, bordered symmetrically below with the
  66          transpose of these gradients, and bordered diagonally below
  67          to the right with a zero matrix.  (reference:  Paul A.
  68          Samuelson, Foundations of
  69          Economic Analysis, Harvard University Press, Cambridge,
  70          Massachusetts, 1953, pp. 362-365, 376-378; or Caratheodory,
  71          Variationsrechnung und partielle Differentialgleichungen
  72          Erster Ordnung, Leipzig und Berlin, 1935, pp. 164-189.)
  73       BHESSSUB  is BHESS evaluated at a stationary point.
  74       CPOLYSUB  is the polynomial in EIGEN formed by evaluating the
  75          determinant of BHESSSUB.
  76       EIGENS  is a list of the labels of the solutions to CPOLYSUB = 0.
  77          The stationary point is a minimum if all of the solutions
  78          are positive, a saddlepoint if some are positive and some are
  79          negative, a MACSYMUM if all are negative, a non-minimum if some
  80          are zero and the rest are negative, a non-maximum if some are
  81          zero and the rest are positive, and completely undetermined if
  82          all are zero.
  83       DECSLKMULTS is a list of the decision variables, slack variables,
  84          and lagrange multipliers.
  85       NDEC  is the number of decision variables.
  86       NEQZ  is the number of equality constraints.
  87       NLEZ  is the number of inequality constraints, which is also the
  88          number of slack variables.
  89       NTOT  is the order of the bordered Hessian matrix.
  90
  91 ROOTSEPSILON may affect the accuracy of results computed by  SOLVE
  92    and REALROOTS  within STAP.  The default value of 1.0E-7 for this
  93    macsyma global variable is as small as practical for pdp-10 single-
  94    precision floating-point arithmetic.  Larger values save cpu time.
  95
  96                        LIMITATIONS:
  97 The class of functions that may be used and the practical limitations
  98 on the number of decision variables and constraints is primarily
  99 dependent upon the capabilities of the built-in SOLVE function,  which
 100 is still under development.  As of April, 1974, SOLVE attempts to find
 101    1.  all of the exact closed-form solutions to a single equation,
 102 which may involve the elementary transcendental functions, or
 103    2. the exact solution to full-rank simultaneous equations in which
 104 the unknowns enter linearly, or
 105    3.  all of the real solutions to simultaneous multivariate
 106 polynomial equations.
 107
 108    The third case involves elimination, followed by the solution of a
 109 single polynomial equation and back substitution.  When the single
 110 polynomial equation is univariate, it is solved by an iterative
 111 floating-point algorithm, which will usually introduce some roundoff
 112 error, as revealed by slightly non-zero components in GRADSUB.  This
 113 roundoff error could cause ill-conditioned solutions to be missed.
 114 However, integer roots are found exactly provided ROOTSEPSILON is less
 115 than 1.  Also, the back substitution may introduce some complex
 116 solutions even though only real roots of the single polynomial
 117 equation are computed.
 118    As explained in OPTMIZ DEMO or OPTMIZ OUTPUT, SOLVE sometimes works
 119 for problems with rational gradients, and many problems with fractional
 120 powers exponential, trigonometric, or hyperbolic functions may be
 121 converted to the proper form.
 122    SOLVE has succeeded on systems as complicated as 5 dense fully
 123 quadratic equations in 5 unknowns, such as would come from an
 124 unconstrained 5-variable cubic objective that contained most of the
 125 possible terms.