Symbolic optimization and the SyOpt system: The application of symbolic mathematics to the design of mathematical optimization algorithms and systems.

摘要

This thesis explores the application of symbolic mathematics to nonlinear constrained mathematical optimization. Nonlinear programming (NLP) has been applied to a wide variety of business and scientific problems in such areas a chemical process engineering, electrical circuit design, inventory planning, financial portfolio optimization, parameter estimation, airline reservation planning, optimal control optimization, and many other areas. Symbolic mathematics is the application of computing technology to the manipulation of mathematical expressions and mathematical concepts. In recent years the techniques of symbolic mathematics have been popularized by the availability of software packages such as Mathematica and Maple. In contrast, numeric computing is the application of computing technology to the manipulation of numeric quantities (floating point representations) and has been used extensively for mathematical programming implementations. Symbolic mathematics extends the applicability of computing to such problems as: (1) Finding a mathematical expression for the gradient or Hessian of an expression. (2) Finding an expression or quantity for the limit of an expression as a variable approaches a given value from one or more directions. (3) Finding the greatest common denominator (GCD) expression of two polynomials which may be used to simplify the quotient of two polynomials. (4) Performing exact arithmetic in the rational polynomial domain Q to avoid numeric loss of accuracy from repeated computations. (5) Finding all solutions to a given system of nonlinear equations.;As part of this thesis the author has developed a specialized object-oriented symbolic optimization system called SyOpt which has the ability to do symbolic computations over both rational and real fields and is highly extensible to future symbolic optimization research efforts. The SyOpt implementation is focused on taro particular algorithms for symbolic optimization; (i) the development of a symbolic implementation of the barrier method of NLP, called the symbolic barrier algorithm for polynomial constrained global optimization and (ii) the application of symbolic techniques to preprocessing NLP formulations into equivalent but simplified forms. In both of these applications the key theoretical underpinning is Grobner basis theory developed in 1965 which, among its many applications, allows one to symbolically solve systems of polynomial equations.;A major contribution of this work is that the symbolic barrier method offers several advantages over numerical barrier algorithms. First, unlike a numerical barrier algorithm, the method generates all local optima to the problem (under certain assumptions) and thereby can determine the global optimal or multiple global optima for problems that are bounded. Furthermore, an initial feasible solution is not required. Computational results are given for some small, but difficult, nonlinear test problems and the symbolic method is contrasted with current state-of-the-art numeric global optimization techniques.*.;*This dissertation includes a compound CD which requires an ANSI standard CLOS runtime such as Allegro Common Lisp from Franz Inc.