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

Math. 655 Course Outline

The main goals of this course are to focus on present shortcomings in validated constrained global optimization, and to analyze both our efforts and the present efforts of others in overcoming these shortcomings.  The basic principles of validated computations and of optimization will be briefly reviewed during the first week, but the course will not focus on these. More advanced students in the course will be expected to collaborate with the newer students, and visa versa, to share ideas.
As of August 14, this page is still under development.  Further details will be added soon.  (I promise.)  RBK
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.

Note: Some of the material referenced below may be copyrighted, and hence is not generally available by clicking on it. Please email me, rbk@louisiana.edu, and I will email you either a Postscript or a PDF copy of the appropriate excerpts, according to the ``fair use" provision of the copyright law.

Home page for the course
Bibliography for the course in PDF format
Recommended references for the first part of the course: The first two chapters of Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Mohit Tawarmalani and Nikolaos Sahinidis, Kluwer Academic Publishers, 2002 will be used, as well as C. A. Floudas, Detyerministic Global Optimization: Theory, Methods, and Applications, Kluwer Academic Publishers, 2000.

 
Topic no.  Description Explanation / References / Projects
1. Overview of the course and a review of global optimization principles
  1. Overall branch and bound algorithms
  2. Constraints and constrained global optimization
  3. The Fritz-John equations and problems with them.
  • Math. 655 Fall 2001 course outline review
  • Arnold Neumaier's Global Optimization web site
  • Chapter 5 of Rigorous Global Search: Continuous Problems (Kearfott, Kluwer Academic, 1996)
    		•
    2. A review of validated computation principles
  • Kearfott's Euromath Bulletin article
  • Kreinovich's web page, 
    		•
    3. A problem: Interaction of constraints, objective, and global estimates.
  • Section 4 of Libraries, Tools, and Interactive Systems for Verified Computations: Four Case Studies, to appear in the proceedings of Dagstuhl Seminar 03041, January 2003. This is available offline (at present).
    		•
    4. Comparison of various linear underestimators, interval evaluations, and Taylor models The introductory sections of the Tawarmalani and the Floudas books, as well as class notes. Several techniques are exhaustively applied to an illustrative example.
    5. Solving the resulting quadratic programming problem See the web book, Linear Complementarity, Linear and Nonlinear Programming: Internet Edition
    6 Validating the solution of the linear programming problem
  •  See the work by Neumaier and Shcherbina, and the work by Jansson
    		•
    7. An overestimation / underestimation arithmetic
    8. A study of duality in linear programming  
    9. Refinement of relaxations with the "sandwich" algorithm, etc.
    10. Possible LP solvers for the relaxed problem
  • General information
  • Free solvers
    1. CLP from the COIN project. (This is an open-source C++ code that is supposed to be competitive with the best commercial solvers.)
    2. SPLP from the SLATEC library.  (This is an older Fortran code, but handles sparse problems, as we obtain from the linear relaxations. This will probably be the easiest to interface with GlobSol, but we may need to search for something more efficient later.)  I have installed SLATEC on our Sparc machines at /mathpkgs/SLATEC/slatec.a.  (This is a library for linking using Sun's Fortran 95 compiler.)
  • Major commercial solvers others have used to solve relaxations
    1. CPLEX 
    2. LINDO (Not only can the linear programming solver be used, but LINDO systems is presently developing a global optimization package based on linear relaxations.)
    11. Languages for modeling
  • GAMS
  • AMPL
  • MPS

    • Problems of interest are commonly expressed in these languages.
    12. Experimentation over the web
      The NEOS interface
    13. The alpha-BB approach
  •  Floudas' COCOS-02 presentation (Caution:  This is a very large file. Do not attempt to receive it over a slow internet connection.) 
  • A Glossary of Mathematical Programming Terms
    		•
    12.
    13.
    14.
    15.
    16.  
    17.  
    18.
    19
    20.
    21.
    22.
    23.
    24.
    25.
    26.
    27.
    28.
    29.
    30.
    31.
    32.
    33.
    35.
    36.
    37.
    38.
    39.
    40.
    41.
    42.
    43.