http://interval.louisiana.edu/courses/655/655-fall-2010-outline.html

Math. 655, Fall, 2010 Course Outline

This outline is a tentative guide, and will be updated as the course progresses.  Time will be allocated as appropriate for student presentations and discussion.  The topics will not necessarily be covered in the order in which they are presented here.

Note: Some of the material referenced below may be copyrighted, and hence is not generally available by clicking on it. That material is posted on the Moodle site for our course.

Home page for the course 

Outline for a somewhat related course from Fall, 2006
Bibliography for the 2006 course in PDF format
Outline for the somewhat related course from Fall, 2003
Bibliography for the 2003 course in PDF format


 
Description Explanation / References / Projects
A review of basic concepts in linear, convex, and and non-convex optimization
  • Chapter 9 of  Classical and Modern Numerical Analysis: Theory, Methods, and Pracice, especially the sections on linear programming and branch and bound methods.
  • Exploration of the optimization methods on the NEOS server.
A review of basic properties and theorems from interval arithmetic Excerpts from Classical and Modern Numerical Analysis: Theory, Methods, and Practice.
The GlobSol software system
 We will focus on the following:
  1. Basic installation and use of GlobSol.
  2. The structure of GlobSol and GlobSol's components.
  3. Use of GlobSol's components in future research and software development.
Our initial reference will be the GlobSol User Guide, Optimization Methods and Software 24 (4-5), pp. 687--708 (August, 2009).

(Pursuit of this topic initially requires access to a linux-based system with a sufficiently recent installation of  the gnu compiler suite.  Time will be spent discussing this environment, as necessary.)
Relaxations in non-convex optimization, and solution of non-convex problems without branching in the original space.
Initial references will be
  1. R. B. Kearfott and S. Hongthong, Validated Linear Relaxations and Preprocessing: Some Experiments,  SIAM Journal on Optimization  16 (2), pp. 418--433 (2005).
  2. Interval Computations, Rigor and Non-Rigor in Deterministic Continuous Global Optimization, accepted for publication in Optimization Methods and Software.
  3. R. B. Kearfott and S. Hongthong, Rigorous Linear Overestimators and Underestimators, technical report.
  4. Arnold Neumaier, Safe bounds in linear and mixed-integer linear programming, Mathematical Programming 99, 2, 2004.
Handling disconnected images in branch and bound algorithms
 Note: This topic involves constraint propagation, which we will introduce first. An example of constraint propagation is
An early and now somewhat elementary treatment, but with our point of view, is in
  • 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. 169-191 (1991).  A preprint is available here:
    • Postscript file; DVI file; PDF file
  1. On Utilizing Disconnected Images within GlobSol's Constraint Propagation Software, talk given at SCAN 2010, Lyon, France, September 27-30, 2010. 
    Slides from the talk: PDF file.
    (See also the more extensive writeup posted on Moodle.)
  2. Heikel Batnini, Claude Michel, and Michel Rueher, Mind the Gaps: A New Splitting Strategy for Consistency Techniques, in Principles and Practice of Constraint Programming -- CP 2005,  Peter van Beek (Ed.), Lecture Notes in Computer Science no. 3709, Springer Verlag, 2005.
The following topics will be pursued to the extent they complement and enhance the above topics.


Parallelization of branch and bound algorithms and MPI.
 A good introduction to use of MPI in parallel computing is Parallel Scientific Computing in C++ and MPI, George  Karniadakis and Robert M. Kirby II, Cambridge Univ. Press, QA76.58 K37 2003, ISBN 0-521-81754-4.

Beyond the basics of parallel programming, we may cover parallelization of branch and bound algorithms, following the agenda in 655-656 in 2007-2008.  References will be posted on the moodle course.