UFO
UFO is an interactive system for universal functional
optimization that serves for solving both dense medium-size and
sparse large-scale optimization problems. The UFO system can be
used for the following applications:
- Formulation and solution of particular optimization
problems.
- Preparation of specialized optimization routines (or
subroutines).
- Designing and testing new optimization methods. The UFO
system is a very useful tool for optimization algorithms
development.
The UFO system is an open software system for solving a broad
class of optimization problems. An optimization problem solution
is processed in four phases. In the first phase the optimization
problem is specified and an optimization method is selected. This
can be made in three different ways:
- Full dialogue mode. The problem specification and the
method selection are realized by using a conversation
between the user and the UFO system.
- Batch mode. The problem specification and the method
selection are realized by using the UFO control language.
An input file written in the UFO control language has to
be prepared.
- Combined mode. Only a part of the specification is
written in the input file. The rest of the specification
is obtained as in the dialogue mode. This possibility is
usually the best one since the problem functions can be
defined beforehand by using a convenient text editor.
The second phase is realized by using the UFO preprocessor.
This preprocessor is written in the Fortran 77 language and its
output is a Fortran 77 control program. In the third phase, the
control program is translated by using a Fortran 77 compiler and
a final program is linked by using library modules. In the fourth
phase, the final program is executed and thus results which can
be viewed by using extensive output means are obtained. A
detailed description of the UFO system is contained in research
report
V1252-17.pdf.
The UFO system can be used for solving various dense or sparse
optimization problems:
- Unconstrained or box constrained optimization.
- Optimization with general linear constraints.
- Optimization with general nonlinear constraints.
- Nonsmooth optimization.
- Global optimization.
- Solution to systems of nonlinear functional equations.
- Solution to systems of ordinary differential equations.
Moreover, the objective function can assume various forms:
- General objective function.
- Linear or quadratic objective function.
- Sum of squares (or powers) criterion.
- Minimax criterion.
- Integral criterion containing solution to ordinary
differential equations.
The UFO system contains optimization methods that can be
divided into the following classes:
- Heuristic methods for small-size problems. This class
contains the pattern search method and the simplex method
of Nelder and Mead.
- Conjugate gradient methods for large-scale problems.
- Variable metric methods which use an approximation of the
Hessian matrix updated in each iteration.
- Variable metric methods with limited memory for large-scale
problems.
- Variable metric methods for large-scale sparse and partially
separable problems.
- Modified Newton methods which use the Hessian matrix
computed either analytically or numerically.
- Modified Newton methods for large-scale sparse and partially
separable problems.
- Truncated Newton methods for large-scale problems based on
difference approximations of directional derivatives.
- Modified Gauss-Newton methods for nonlinear least squares
which use the Jacobian matrix or the normal equation
matrix.
- Modified Gauss-Newton methods for large-scale partially
separable nonlinear least squares.
- Quasi-Newton methods for nonlinear least squares and
nonlinear equations which use an approximation of the
Jacobian matrix updated in each iteration.
- Quasi-Newton methods with limited memory for large-scale
nonlinear least squares and nonlinear equations.
- Quasi-Newton methods for large-scale partially separable
nonlinear least squares and nonlinear equations.
- Simplex type methods for linear programming problems.
- Interior point methods for linear programming problems.
- Simplex type methods for quadratic programming problems.
- Interior point methods for quadratic programming problems.
- Proximal bundle methods for nonsmooth optimization.
- Bundle-Newton methods for nonsmooth optimization.
- Variable metric bundle methods for nonsmooth optimization.
- Recursive quadratic programming methods for dense minimax
problems.
- Recursive quadratic programming methods for dense nonlinear
programming problems.
- Recursive quadratic programming methods for sparse equality
constrained problems.
- Interior point methods for sparse minimax problems.
- Interior point methods for sparse nonlinear programming
problems.
- Nonsmooth equation methods for sparse nonlinear programming
problems.
- Random search methods for global optimization.
- Continuation methods for global optimization. This class
contains tunneling function methods and filled function
methods.
- Clustering methods for global optimization. This class
contains a density clustering method and a single linkage
clustering method.
- Multi-level methods for global optimization. Thiss class
contains a multi-level single linkage clustering method
and a multi-level mode analysis method.
These methods can be realized in various forms depending on
the stepsize selection:
- Line search methods.
- General trust region methods.
- Special trust region methods for nonlinear least squares
problems.
- Modified Marquardt methods for nonlinear least squares
problems.
- SQP filter methods for nonlinear programing problems.
Moreover, various preconditioned iterative methods can be
chosen for the direction determination.
The UFO system contains useful input and output possibilities:
- The UFO control language for batch inputs.
- Text dialogue for UNIX workstations.
- Graphic dialogue for PC computers.
- Basic and extended screen output.
- Graphic screen output for PC computers.
- Text file output.
The following figure shows an example of graphic screen output: