share/calculus/optmiz_3.dem

   1 load('optmiz);
   2 /*
   3 Now let's try the famous post-office parcel problem:  maximize the
   4 volume of a rectangular parallelopiped parcel, subject to the
   5 constraints that the length plus the girth can't exceed 72,
   6 and that the length, width, and depth cannot be negative or
   7 exceed 42. */
   8 vol: l*w*d ;
   9 eqcon: l + 2*w + 2*d - 72 ;
  10 /* However, we may simplify the problem further, saving
  11 additional time, by making the change of variable L=42-S**2, which
  12 automatically satisfies  the upper bound on L; and we may solve the
  13 equality constraint for either W or D, then eliminate it from the
  14 objective These changes reduce the problem to two simultaneous
  15 nonlinear equations: */
  16 solve(eqcon,w);
  17 volsub: ev(vol,%);
  18 ev(%, l=42-s**2);
  19 stapoints(%) ;
  20 /* It is almost always worth solving the largest possible subset
  21 of the equality constraints for variables that enter them linearly,
  22 then using this solution to eliminate these variables from the
  23 remaining constraints and from the objective.  This is also worth
  24 doing for variables that enter nonlinearly, provided it introduces no
  25 fractional powers in the objective or remaining constraints.
  26 For example, to find the stationary points of  X + 3*Y - 6*Z**2,
  27 subject to  X**2 + Y**2 + Z**2 = 1, it is well worth eliminating Z.
  28
  29 The change of variable for eliminating the inequality constraint
  30 L <= 42, is equivalent to converting the inequality to an equality by
  31 introducing a squared slack variable, solving for L, then eliminating
  32 L from VOLSUB.  From this viewpoint, the "change of variable"
  33 technique is seen to be applicable to a great variety of inequality
  34 constraints, not merely upper and lower bounds as is implied in most
  35 textbooks.  Together with applicable equality constraints, it is
  36 generally worth including in the elimination the largest possible
  37 subset of inequality constraints for which the eliminated variables
  38 enter linearly, up to the number of decision variables minus the number
  39 of equality constraints.
  40
  41 Another technique for treating an inequality constraint is to
  42 solve the problem with the constraint assumed active, and also with
  43 the constraint ignored, checking any stationary points for violation
  44 of the constraint in the latter case: */
  45 stapoints(ev(volsub,l=42)) ;
  46 stapoints(volsub) ;
  47 /* The second-order test is inadequate when
  48 constraints have been artificially activated.  For example, the one
  49 eigenvalue for the case  D = 15/2 above is negative, but this
  50 stationary point is actually a saddle.  To see this, we must check the
  51 unactivated gradient at this point to see if it points into or out of
  52 the feasible region: */
  53 ev(grad, d=15/2, l=42);
  54 decslkmults;
  55 /*  GRAD is a global varible bound by STAP to the
  56 symbolic expression for the gradient, and DECSLKMULTS is bound to the
  57 variables that the gradient is taken with respect to, in the order
  58 of their components in GRAD.  Thus, -405/4 points in, making the
  59 point a saddle.
  60
  61 The report referenced at the beginning of this demonstration
  62 explains how to generalize this test to more than one constraint.
  63
  64 When there is more than one inequality constraint, each feasible
  65 combination must be activated, unless some additional convexity
  66 requirements are satisfied.  Nevertheless, this combinatorial
  67 activation technique is probably capable of treating
  68 larger problems than either the change-of-variable or the squared-
  69 slack-variable-with-multiplier techniques of treating inequality
  70 constraints.
  71
  72 We have already seen how STAP finds poles of the objective or gradient
  73 only by accident.  The following examples are included as reminders
  74 about other limitations of using calculus to find extrema:*/
  75 stapoints(x, [], x**3-y**2) ;
  76 /* Lagrange multipliers require the constraints to have con-
  77 tinuous tangents, and this is violated for the above example at X=0,
  78 Y=0, where the objective is a minimum.  A direct use of elimination
  79 would fail too, because it results in an undefined derivative at the
  80 minimum.  In such cases, each piece between discontinuities must be
  81 considered a separate constraint.
  82
  83 The next example has a minimum at X=0, Y=0, where the two
  84 active constraints are parallel, making them linearly dependent.
  85 Such cusps or "wiskers" on the feasible region violate the so-called
  86 "constraint-qualification" requirement; so the extremum is not found:*/
  87 stapoints(x, [-y, y-x**3]) ;
  88 /* The following example doesn't have a strictly feasible point;
  89 so it violates Slater's condition; and the extremum at X=0 is not
  90 found: */
  91 stapoints(x, x**2) ;
  92 /* Finally, it is important to remember that unbounded regions
  93 may have nonstationary or asymptotically stationary points
  94 at infinity, which STAP will not find.  Such situations are usually
  95 obvious from qualitative considerations, provided the objective and
  96 constraints are not too complicated and numerous, but the macsyma LIMIT
  97 function can be of help.  However, it is important to remember that a
  98 multivariate limit depends upon the way it is taken.  This is
  99 illustrated by the following example, where you will have to type
 100 NONZERO; in response to two interrupts: */
 101 peano:  (y - c - (a*x)**2)*(y - c - (b*x)**2) ;
 102 limit(peano, y, inf);
 103 limit(peano, x, inf);
 104 radcan(ev(peano, y=c+(a**2+b**2)*x**2/2));
 105 limit(%, x, inf);