GLOBSOL, A Fortran 90 Package for Rigorous Global

Search

This talk will present

1. a reminder of what verified global optimization is;

2. a brief introduction to INTOPT 90;

3. goals of a project to develop INTOPT 90 into a commercial quality package;

4. our overall development plan in the project;

5. specific improvements to INTOPT 90.

comput. diff. in global opt. August 1997 ISMP–1

Verified Global Optimization

Given ϕ : X → ℝ and constraints

C(X) = (c_{1}(X), …, c_{m}(X))^{T} : ℝ^{n} → ℝ^{m},
G(X) = (g_{1}(X), …, g_{m}(X))^{T} : ℝ^{n} → ℝ^{p}

rigorously find upper and lower bounds to the values of ϕ that solve

minimize ϕ(X)

subject to c_{i}(X) = 0, i = 1, …, m,
g_{i}(X) <= 0, i = 1, …, p,

and find bounds [a_{i}, b_{i}] such that

• b_{i} − a_{i} is small, 1 ≤ i ≤ n, and

• it is automatically proven that there is a unique critical point of ϕ within each

\begin{matrix}X̌ = \{X = (x_{1}, …, x_{n})| \\ a_{i} ≤ x_{i} ≤ b_{i}, 1 ≤ i ≤ n\}. \end{matrix}

The INTOPT 90 Package

Present Capabilities

• An interval data type

• Automatic differentiation; need only to program a single objective function • Accessible building blocks

• General nonlinear systems solver

• General unconstrained and equality-and-bound-constrained optimizer

• Algorithms configurable with flags

• Style and amount of printing configurable with flags

How to Solve a Problem

1. Write a Fortran 90 program that defines the equations, or the objective function and constraints.

2. Run that program to produce a code list.

3. If it is an optimization problem, differentiate the code list to produce a gradient code list.

4. Supply a data file with initial box coordinates, stopping tolerance, any bound constraints, and possible initial guess point.

5. Adjust algorithm configuration files.

6. Run the system solver or optimizer.

7. Examine the output file.

comput. diff. in global opt. August 1997 ISMP–4

An Example

The following file defines the objective function

ϕ(X) = (x_{1} − 1)^{4} + (x_{2} − 1)^{4} + (x_{3} − 2)^{4}

subject to constraints

x_{1}^{2} + x_{2}^{2} + x_{3}^{2} − 6 = 0
x_{1}^{2} + x_{2}^{2} − 3 = 0

PROGRAM WOLFE3
USE OVERLOAD
PARAMETER (NN=3)
PARAMETER (NSLACK=0)
TYPE(CDLVAR), DIMENSION(NN+NSLACK):: X
TYPE(CDLLHS), DIMENSION(1):: PHI
TYPE(CDLINEQ), DIMENSION(2):: G
OUTPUT_FILE_NAME='WOLFE3.CDL'
CALL INITIALIZE_CODELIST(X)
PHI(1) = (X(1)-1)**4 + (X(2)-1)**4 + (X(3)-2)**4
G(1) = X(1)**2 + X(2)**2 + X(3)**2 - 6
G(2) = X(1)**2 + X(2)**2 - 3
CALL FINISH_CODELIST
END PROGRAM WOLFE3

comput. diff. in global opt. August 1997 ISMP–5

    INTOPT 90 Example

(continued)

1. Running the above program produces an internal representation, or code list.

2. The optimization code interprets the code list at run time to produce floating point and interval evaluations of the objective function, gradient, and Hessian matrix.

3. A separate data file defines the initial search box, the bound constraints, and the initial guess, if any.

4. Separate data files supply algorithm options, such as which interval Newton method to use and how to precondition the linear systems.

5. Excerpts from the output file follow.

comput. diff. in global opt. August 1997 ISMP–6

      INTOPT 90 Example

Excerpts from the Output File

Output from RUN_GLOBAL_OPTIMIZATION on  06/19/1996 at 18:35:44.
DATA WAS TAKEN FROM DATA FILE: wolfe3.DT1
(lines deleted)
LIST OF BOXES CONTAINING VERIFIED FEASIBLE POINTS:
Box no.:          1
Box coordinates:
    .1225D+01    .1225D+01     .1225D+01    .1225D+01
    .1732D+01    .1732D+01
PHI:
    .1026D-01    .1026D-01
(lines deleted)
Box contains the following approximate root:
    .1225D+01    .1225D+01    .1732D+01
OBJECTIVE ENCLOSURE AT APPROXIMATE ROOT:
    .1026D-01    .1026D-01
(lines deleted)
Total number of dense slope matrix evaluations:        116
Total number second-order interval evaluations of the
original function:         29
Total number dense interval constraint evaluations:        188
(lines deleted)
 Total number of boxes processed in loop:         13
Overall CPU time:    .3000D+01

INTOPT 90 Reference

Rigorous Global Search: Continuous Problems, R. B. Kearfott, Kluwer Academic Publishers, 1996.

Commericalization of INTOPT 90

Goals

• To establish verified global optimization and, more generally, interval computations in the mainstream of scientific computing practice.

• To make verified global optimization technology and interval computations more widely “available to the masses” than before.

This is done through a Sun Microsystems Cooperative Research contract, with participants with varied backgrounds from different universities.

comput. diff. in global opt. August 1997 ISMP–9

Commericalization of INTOPT 90

Overall Plan

1. Test, expand, and improve INTOPT 90

2. Use the resulting package (GLOBSOL) to solve important industrial problems that have not been solved by other means – get testimonial letters from the industries that these solutions are valuable.

3. GLOBSOL will be made available free of charge.

4. Develop an interval data type in the gnu Fortran 77 compiler and in Sun Microsystems’ Fortran 90 compiler.

GLOBSOL Development

Some Specifics

• Better packaging.

• Coarse-Grained Parallelization

• Algorithmic Improvements

• Capability Improvements

Better Packaging

• Refine and test installation on different platforms

• Thoroughly test individual routines

• Develop a comprehensive and accurate user guide (beyond the material in the book Rigorous Global Search: Continuous Problems)

Parallelization

• Coarse-grain parallelization (at the level of processing boxes), initially.

• A master-slave model.

• MPI

• First on a system of Sparc Ultra’s, then more generally.

Algorithmic Improvements • Better use of slopes

• Better handling of constraints

• Better local root-finders / optimizers • Miscellaneous low-level improvements in efficiency

Capability Improvements

• Handling of interval coefficients and parameters

• Efficient handling of both equality and inequality constraints

• Handling of constrained nonlinear equations

• Enhanced automatic differentiation facilities

Request for Information

Please inform us new developments and techniques, and send us your preprints / reprints, especially concerning techniques beyond those described in Rigorous Global Search: Continuous Problems. You will be properly cited, and the subject area will be advanced.