CRPC-TR99786-S						March 1999


Title: A Class of General Trust-Region Multilevel Algorithms for Nonlinear
Constrained Optimization: Global Convergence Analysis
Authors: Natalia M. Alexandrov and J.E. Dennis, Jr.

Submitted March 1999

Abstract:
	This paper presents a broad class of trust-region multilevel
algorithms for solving large, nonlinear, equqlity constrained optimization
problems, as well as a global convergence analysis of the class. The work
is motivated by engineering optimization problems with naturally
occurring, densely or fully-coupled subproblem structure.
	The constraints are partitioned into blocks, the number and
composition of which are determined by the application. At every
iteration, a multilevel algorithm minimizes models of the reduced
constraint blocks, followed by a reduced model of the objective function,
in a sequence of subproblems, each of which yields a substep. The trial
step is the sum of these substeps. The salient feature of the multilevel
class is that there is no prescription on how the substeps must be
computed. Instead, each substep is required to satisfy mild sufficient
decrease and boundedness conditions on the restricted model that it
minimizes. Within a single trial step computation, all substeps can be
computed by different methods appropriate to the nature of each
subproblem. This feature is important for the applications of interest in
that it allows for a wide variety of step-choice rules.
	The trial step is evaluated via one of two merit functions that
take into account the autonomy of subproblem processing.
	The multilevel procedure presented in this work is sequential. If
a problem exhibits full or partial separability, or if separability is
induced by introducing auxiliary variables, then the multilevel algorithms
can easily be stated in parallel form. However, since this work is devoted
to analysis, we consider the most general case - that of a fully coupled
problem.

Key words: Constrained optimization, nonlinear programming, multilevel
algorithms, global convergence, trust region, equality constrained,
multidisciplinary design optimization

AMS subject classifications: 65K05, 49D37

------------------------------------------------------------------------------
Natalia M. Alexandrov
n.alexandrov@larc.nasa.gov
Multidisciplinary Optimization Branch
NASA Langley Research Center

J.E. Dennis, Jr.
dennis@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University