Witwatersrand Global Optimization Short Course Outline

(R. Baker Kearfott, June, 2004)

The course will consist of 8 to 12 hour lectures and discussion or question and answer sessions over two days. Materials will include a bibliography, preprints and reprints of the author and his colleagues, as well as web material from various sources.  For the introductory part of the course, we will rely significantly on Rigorous Global Search: Continuous Problems, Kluwer Academic Publishers, Dordrecht, 1996.  Although not explicitly referenced here, there are numerous general references on global optimization that can be provided to short course participants upon request.
  1. Overview of the Course and Goals
  2. Some Underlying Techniques
    1. Principles of Interval Arithmetic and Interval-Based Branch and Bound methods

      2. References:
    2. Principles of Automatic Differentiation
      1. The Forward Mode

        2. References:
      2. The Reverse Mode

        3. Reference:
      3. Code Lists and Code List Generation

        4. References:
      4. Interval Newton Methods

        5. References:
  3. Branch and Bound Algorithms for Global Optimization
    1. General Principles for All Deterministic Algorithms

      2. Reference:
    2. Complete Versus Incomplete Algorithms
    3. Validated Versus Unvalidated Algorithms
  4. Our View of Constraint propagation

    5. References:


    The GlobSol Package
    Reference:

    1. Development History and Components
    2. Overall Algorithm
    3. Examples of Use
    4. The Self-Contained and Freely Distributed Philosophy
    5. Limitations of the Present Algorithm
      1. Unconstrained versus constrained problems

        2. Reference:
      2. On the Fritz--John equations
      3. An equality constraint example

        4. Reference:
        • For various examples: Validated Constraint Solving -- Practicalities, Pitfalls,

          • and New Developments, talk to be given June, 2004 at isiCAD, Akademgorodok, Novosibirsk, Russia.
  5. Linear Relaxations

    6. References:
    1. Principles of Relaxations
      1. The basic idea
      2. Relaxation arithmetic of McCormick
      3. A review of the literature
      4. Some details of linear relaxations
    2. Successful Commercial Packages Based on Complete but Unvalidated Algorithms
      1. Baron (A version is distributed by GAMS)
      2. From LINDO (under development)
    3. Validation and Linear Relaxations
      1. The expanded problem, symbolic analysis, and equivalences
      2. Validated versions of the elementary operations and library functions

        3. Reference:
      3. Incorporation of linear relaxations into validated algorithms
  6. Linear Relaxations and GlobSol

    7. Reference:
    1. Incorporation into the overall algorithm
    2. Empirical results on the effectiveness of these techniques
    3. Ideas for the future
      1. Effective incorporation of randomness to handle uncertainty in a validated way
      2. Practical applications
    Some overall references:
    1. A. Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, to appear in: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.
    2. R. B. Kearfott's preprint / reprint page.
    3. M. Tawarmalani and N. V. Sahinidis. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory,  Algoritthms, Software, and Applications. Kluwer, Dordrecht, Netherlands, 2002.
    4. Ch. Floudas, Deterministic Global Optimization: Theory, Methods and Applications.  Kluwer, Dordrecht, Netherlands, 1999.

      5.