Analytical Optimization Using Computer Algebraic Manipulation

Publisher Website
Google Scholar
Abstract
This paper describes how a computer algebraic manipulation language, such as MACSYMA, may be used to determine analytically all the stationary points of a function of several variables, either unconstrained or subject to equality and/or inequality constraints. By using the optimization function described, the user may simply supply symbolic expressions for the objective function and constraints. The function then automatically (1) converts inequality constraints to equality constraints by the addition of squared slack variables; (2) uses Lagrange multipliers and symbolic differentiation to form simultaneous equations satisfied by all stationary points; and (3) uses algebraic manipulation to attempt solution of these possibly nonlinear equations. If solutions are found, the function uses algebraic manipulation to derive a symbolic Hessian matrix, which is used in a second-order test to determine whether the stationary point is a minimum, a saddle, or a maximum. Alternatively, the user may first reduce the size of the problem by using built-in functions (4) to make changes of the variable to eliminate certain inequality constraints; (5) to analyze a set of problems where each possible active set of inequality constraints is treated as equality constraints, with the other inequality constraints ignored, checking each stationary point for violation of the ignored constraints; (6) to use some or all of the equality constraints to eliminate some of the unbounded variables from the other constraints and from the objective function. The effectiveness of these techniques is compared, and results are presented for some of the standard test cases used for numerical optimization programs.