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.

Overview of the Course and Goals

Some Underlying Techniques

Principles of Interval Arithmetic and IntervalBased Branch and Bound methods
References:

Principles of Automatic Differentiation

The Forward Mode
References:

The Reverse Mode
Reference:

Code Lists and Code List Generation
References:

Interval Newton Methods
References:

"Interval
Analysis: Interval Newton Methods," Encyclopedia
of Optimization, Kluwer, Dordrecht, Netherlands, 2001, (vol.
3, pp. 7678).

"Interval
Analysis: Interval Fixed Point Theory," Encyclopedia
of Optimization, Kluwer, Dordrecht, Netherlands, 2001, (vol.
3, pp. 4851).

§6.2.2, page 219ff of Rigorous
Global Search: Continuous Problems, for analysis of when it works.

Branch and Bound Algorithms for Global Optimization

General Principles for All Deterministic Algorithms
Reference:

Complete Versus Incomplete Algorithms

Validated Versus Unvalidated Algorithms

Our View of Constraint propagation
References:

Decomposition
of Arithmetic Expressions to Improve the Behavior of Interval Iteration
for Nonlinear Systems, preprint of an article that appeared in
Computing 47 (2), pp. 169191 (1991).

Second to fourth pages of "Interval
Analysis: Intermediate Terms," Encyclopedia of Optimization,
Kluwer, Dordrecht, Netherlands, 2001, (vol. 3, pp. 1821).

Chapter 7, page 227ff of Rigorous
Global Search: Continuous Problems.
The GlobSol Package
Reference:

GlobSol: History, Composition, Advice on Use, and Future, talk given
at COCOS'02, first COCONUT International Workshop on global optimization
and constraint propagation, Sophia Antipolis, October 4, 2002, in Lecture
Notes in Computer Science no. 2861, Springer Verlag, pp. 1731 (2003).

Development History and Components

Overall Algorithm

Examples of Use

The SelfContained and Freely Distributed Philosophy

Limitations of the Present Algorithm

Unconstrained versus constrained problems
Reference:

Excerpt
from R. B. Kearfott, M. Neher, S. Oishi, and F. Rico, Libraries,
Tools, and Interactive Systems for Verified Computations: Four Case Studies,
in Numerical Software with Result Verification, Lecture Notes in
Computer Science no. 2991, ed. R. Alt, A. Frommer, R. B. Kearfott, and
W. Luther, Springer Verlag, Heidelberg, 2004.

On the FritzJohn equations

An equality constraint example
Reference:

For various examples: Validated Constraint Solving  Practicalities,
Pitfalls,
and New Developments, talk to be given June, 2004 at isiCAD,
Akademgorodok, Novosibirsk, Russia.

Linear Relaxations
References:

Principles of Relaxations

The basic idea

Relaxation arithmetic of McCormick

A review of the literature

Some details of linear relaxations

Successful Commercial Packages Based on Complete but Unvalidated Algorithms

Baron (A
version is distributed by GAMS)

From LINDO (under development)

Validation and Linear Relaxations

The expanded problem, symbolic analysis, and equivalences

Validated versions of the elementary operations and library functions
Reference:

Incorporation of linear relaxations into validated algorithms

Linear Relaxations and GlobSol
Reference:

Incorporation into the overall algorithm

Empirical results on the effectiveness of these techniques

Ideas for the future

Effective incorporation of randomness to handle uncertainty in a validated
way

Practical applications
Some overall references:

A. Neumaier, Complete
Search in Continuous Global Optimization and Constraint Satisfaction,
to appear in: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University
Press 2004.

R. B. Kearfott's
preprint / reprint page.

M. Tawarmalani and N. V. Sahinidis. Convexification
and Global Optimization in Continuous and MixedInteger Nonlinear Programming:
Theory, Algoritthms, Software, and Applications. Kluwer,
Dordrecht, Netherlands, 2002.

Ch. Floudas, Deterministic
Global Optimization: Theory, Methods and Applications. Kluwer,
Dordrecht, Netherlands, 1999.