Optimization Using Surrogate Objectives on a Helicopter Test Example

This paper presents results for a 31 variable helicopter rotor design example. Results are given for several numerical methods. This is a brief description of a portion of the Boeing/IBM/Rice University collaboration whose purpose is to develop effective numerical methods for managing the use of approximation concepts or response surface methodology in design optimization.

December 1997

[(Arlington, VA, 1997), 49-58, Progr. Systems Control Theory, 24, Birkäuser Boston, Boston, MA, 1998.]

Superlinear and Quadratic Convergence of Affine-Scaling Interior-Point Newton Methods for Problems with Simple Bounds without Strict Complementarity Assumption

A class of affine-scaling interior-point methods for bound constrained optimization problems is introduced which are locally q-superlinear or q-quadratic convergent. It is assumed that the strong second order sufficient optimality conditions at the solution are satisfied, but strict complementarity is not required. The methods are modifications of the affine-scaling interior-point Newton methods introduced by T. F. Coleman and Y. Li (Math. Programming, 67:189-224, 1994). There are two modifications. One is a modification of the scaling matrix, the other one is the use of a projection of the step to maintain strict feasibility rather than a simple scaling of the step. A comprehensive local convergence analysis is given. A few simple examples are presented to illustrate the pitfalls of the original approach by Coleman and Li in the degenerate case and to demonstrate the performance of the fast converging modifications developed in this paper.

December 1997

Accelerating the Lanczos Algorithm via Polynomial Spectral Transformations

We consider the problem of computing a few clustered and/or interior eigenvalues of a symmetric matrix A without using a matrix factorization. This can be done by applying the Lanczos algorithm to p(A), where p(lambda) is a polynomial that maps the clustered and/or interior eigenvalues of A to extremal and well separated eigenvalues of p(A). We will demonstrate and compare several techniques of constructing these polynomials. Numerical examples are presented to illustrate the effectiveness of using these polynomial to accelerate the Lanczos process.

November 1997

Computational Experience with a Preconditioner for Interior Point Methods for Linear Programming

In this paper, we discuss efficient implementation of a new class of preconditioners for linear systems arising from interior point methods. These new preconditioners give superior performance near the solution of a linear programming problem where the linear systems are typically highly ill-conditioned. They rely upon the computation of an LU factorization of a subset of columns of the matrix of constraints. The implementation of these new techniques requires some sophistication since the subset of selected columns is not known a priori. The conjugate gradient method using this new preconditioner compares favorably with the Cholesky factorization approach. The new approach is clearly superior for large scale problems where the Cholesky factorization produces intractable fill-in. Numerical experiments on several representative classes of linear programming problems are presented to demonstrate the promise of the new preconditioner.

November 1997

A New Class of Preconditioners for Large-Scale Linear Systems from Interior Point Methods for Linear Programmming

A new class of preconditioners is proposed for the iterative solution of linear systems arising from interior point methods. In many cases, these linear systems are symmetric and indefinite. Typically, these indefinite systems can be reduced to an equivalent Schur complement system which is positive definite. We show that all preconditioners for the Schur complement system have an equivalent for the augmented system while the opposite is not true. This suggests it may be better to work with the augmented system. We develop some theoretical properties of the new preconditioners to support this. Computationally, we have verified that this class works better near a solution of the linear programming problem when the linear systems are highly ill-conditioned. Preliminary experiments which illustrate these features are presented. The techniques developed for a competitive implementation are presented in a follow-up paper along with numerical experiments on several classes of linear programming problems.

November 1997

Improved Common Line-Based Icosahedral Particle Image Orientation Estimation Algorithms

Modifications are described for the center and angular parameter estimation algorithms of common line-based particle image orientation determination which is an essential step in the three-dimensional reconstruction of icosahedral virus particles. The modifications incorporate a variety of image processing, pattern recognition, and statistical tools resulting in objective and automated orientation estimation algorithms. The modified algorithms were tested using electron cryo-microscopic particle images of three different virus specimens, with sizes 400-1250 \AA\ in diameter, covering a broad range of defocus values. Evaluation of these modified algorithms shows significant improvement over the previous algorithms. The center and angular parameters were estimated with higher accuracy allowing the identification of a larger number of particle orientations. Usage of the modified estimation algorithms resulted in the identification of particle orientations which could not be identified using the algorithms before modification. Furthermore, these improvements have resulted in the determination of a better quality and a higher resolution three-dimensional reconstruction. The improved algorithms have been developed into a software package.

[Ultramicroscopy 68 (1997), no. 2, 231-255.]

October 1997

A New Trust-Region Algorithm for General Nonlinear Programming

A new trust-region algorithm for solving the general nonlinear programming problem is introduced. In this algorithm, an active set strategy is used together with a projected Hessian technique to convert the computation of the trial step to two easy trust-region subproblems similar to those for the unconstrained case. To force global convergence, the augmented Lagrangian for general nonlinear programming is used as a merit function.

A convergence theory for this algorithm is presented. Under reasonable assumptions, it is shown that the algorithm is globally convergent.

Numerical experiment on the algorithm is presented. The performance of the algorithm is reported. The numerical results show that our approach is of value and merits further investigation.

October 1997

Computing Minimum-Weight Perfect Matchings

We make several observations on the implementation of Edmonds' blossom algorithm for solving minimum-weight perfect-matching problems and we present computational results for geometric problem instances ranging in size from 1,000 nodes up to 5,000,000 nodes. A key feature in our implementation is the use of multiple search trees with an individual dual-change epsilon for each tree. As a benchmark of the algorithm's performance, solving a 100,000 node geometric instance on a 200 Mhz Pentium-Pro computer takes approximately 3 minutes.

October 1997

[INFORMS J. Comput. 11 (1999), no. 2, 138-148.]

A Faster Galerkin Boundary Integral Algorithm

The symmetry present in Green's functions is exploited to significantly reduce the matrix assembly time for a Galerkin boundary integral analysis. A relatively simple modification of the standard Galerkin implementation for computing the nonsingular integrals yields a twenty to thirty per cent decrease in computation time. This `fast' Galerkin method is developed for both singular and hypersingular equations, and applied to Symmetric-Galerkin implementations in two-dimensions for the Laplace equation and for orthotropic elasticity. In three dimensions, the modified algorithm has been implemented for the singular equation for the Laplace and elastodynamics equations. Comparison timing results for standard and modified algorithms are presented.

September 1997

On the Convergence of an Infeasible Interior-Point Newton Method for Linear Programming

In this work we consider an infeasible interior-point Newton method for primal-dual linear programs. We use a weak notion of centrality recently introduced by Argáez and Tapia for nonlinear programming in order to reach a central point. We establish a global convergence theory and present rather promising numerical experimentation.

September 1997

Numerical Comparisons of Path-Following Strategies for a Basic Interior-Point Method for Nonlinear Programming

An important activity in general nonlinear programming is to determine effective path-following strategies and their implementations using merit function technology. The objective is to present some numerical results obtained for several globalization strategies for the local interior-point Newton's method suggested by El-Bakry, Tapia, Tsuchiya and Zhang using three centrality conditions combined with three merit functions.

September 1997

Solution of Elliptic Partial Differential Equations by an Optimization-Based Domain Decomposition Method

An optimization-based, non-overlapping domain decomposition method for the solution of elliptic partial differential equations is presented. The crux of the method is a constrained minimization problem for which the objective functional measures the jump in the dependent variables across the common boundaries between subdomains; the constraints are the partial differential equations. The method is reformulated as a linear least-squares problem. The latter is examined and a conjugate gradient method for its solution is presented and analyzed. The results of some numerical experiments are then given.

September 1997

On Constructing Interior-Point Path-Following Methods for Certain Semimonotone Linear Complementarity Problems

Interior-point path-following methods have proven to be effective in solving monotone linear complementarity problems (LCPs). The main objective of this paper is to build a theoretical basis for the construction of interior-point path-following methods for some nonmonotone LCPs. We propose a new homotopy formulation that enables us to establish the existence of solution paths in the interior of the nonnegative orthant for several classes of semimonotone LCPs. These paths connect almost every interior point in the nonnegative orthant to a solution point, while possessing desirable smoothness properties. An algorithmic framework is given based on these paths for solving several classes of semimonotone LCPs.

July 1997

On the Quasi-Dynamic Formation of Fine Structures

A description of the asymptotic behavior of the pseudo-parabolic systems of equations describing the curveof the steepest descent and the gradient flow associated with the non-quasiconvex variational integrals is given. It is proven that, for initial data with low energy, the omega-limit set consists of a singletons which are weak relative minimizers of the non-quasiconvex variational integrals.

July 1997

The Relaxation of Non-Quasiconvex Variational Integrals

We show that the Steepest Descent Algorithm in connection with wiggly energies yields minimizing sequences that converge to a global minimum of the associated non-quasiconvex variational integrals. We introduce a multi-level infinite dimensional variant of the Steepest Descent Algorithm designed to compute complex microstructures. We apply this multi-level method to the minimization of the variational problems associated with martensitic branching.

September 1997

[Numer. Math. 82 (1999), no. 2, 281-311.]

An Interior-Point Krylov-Orthogonal Projection Method for Nonlinear Programming

In this work we consider an inexact Newton's method implementation of the primal-dual interior-point algorithm for solving general nonlinear programming problems recently introduced by Argáez and Tapia. This inexact method is designed to solve large scale problems. The iterative solution technique uses an orthogonal projection - Krylov subspace scheme to solve the highly indefinite and nonsymmetric linear systems associated with nonlinear programming. Our iterative method is a projection method that maintains linearized feasibility with respect to both the equality constraints and the complementarity conditions. This guarantees that in each iteration the linear solver generates a descent direction, so that the iterative solver is not required to find a Newton step but rather cheaply provides a way to march toward an optimal solution of the problem. This makes the use of a preconditioner inconsequential except near the solution of the problem, where the Newton step is effective. Moreover, we limit the problem to finding a good preconditioner only for the Hessian of the Lagrangian function associated with the problem plus a positive diagonal matrix. We report numerical experimentation for several large scale problems to illustrate the viability of the method.

June 1997 (revised August 1997)

Airfoil Design by an All-At-Once Method

The all-at-once approach is implemented to solve an optimum airfoil design problem. The airfoil design problem is formulated as a constrained optimization problem in which flow variables and design variables are viewed as independent and the coupling steady state Euler equation is included as a constraint, along with geometry and other constraints. In this formulation, the optimizer computes a sequence of points which tend toward feasiblility and optimality at the same time (all-at-once). This decoupling of variables typically makes the problem less nonlinear and can lead to more efficient solutions. In this paper an existing optimization algorithm is combined with an existing flow code. The problem formulation, its discretization, and the underlying solvers are described. Implementation issues are presented and numerical results are given which indicate that the cost of solving the design problem is approximately six times the cost of solving a single analysis problem.

June 1997

[Int. J. Comput. Fluid Dyn. 11 (1998), no. 1-2, 3-25.]

Formulation and Analysis of a Sequential Quadratic Programming Method for the Optimal Dirichlet Boundary Control of Navier-Stokes Flow

The optimal boundary control of Navier-Stokes flow is formulated as a constrained optimization problem, and a sequential quadratic programming (SQP) approach is studied for its solution.

Since SQP methods treat states and controls as independent variables and do not insist on satisfying the constraints during the iterations, care must be taken to avoid a possible incompatibility of Dirichlet boundary conditions and incompressibility constraint. In this paper, compatibility is enforced by choosing appropriate function spaces. The resulting optimization problem is analyzed. Differentiability of the constraints and surjectivity of linearized constraints are verified and adjoints are computed. An SQP method is applied to the optimization problem and compared with other approaches.

May 1997 (revised October 1997)

[In Optimal control (Gainesville, FL, 1997), 178-203, Kluwer Acad. Publ., Dordrecht, 1998.]

Exact and Inexact Newton Linesearch Interior-Point Algorithms for Nonlinear Programming Problems

In the first part of this research we consider a linesearch globalization of the local primal-dual interior-point Newton's method for nonlinear programming recently introduced by El-Bakry, Tapia, Tsuchiya, and Zhang. Our linesearch uses a new merit function that is a generalization of the standard augmented Lagrangian function and a new notion of centrality. We establish a global convergence theory and present rather promising numerical experimentation.

In the second part, we consider an inexact Newton's method implementation of the linesearch globalization algorithm given in the first part. This inexact method is designed to solve large-scale nonlinear programming problems. The iterative solution technique uses an orthogonal projection-Krylov subspace scheme to solve the highly indefinite and nonsymmetric linear systems associate with nonlinear programming. Our iterative projection method maintains linearized feasibility with respect to both the equality constraints and complementarity condition. This guarantees that in each iteration the linear solver generates a descent direction, so that the iterative solver is not required to find a Newton step but rather cheaply provides a way to march toward an optimal solution of the problem. This makes the use of a preconditioner inconsequential except near the solution of the problem, where the Newton step is effective. Moreover, we limit the problem to finding a good preconditioner only for the Hessian of the Lagrangian function associated with the nonlinear programming problem plus a positive diagonal matrix. We report numerical experimentation for several large scale problems to illustrate the viability of the method.

May 1997

A Modified Augmented Lagrangian Merit Function, and Q-Superlinear Characterization Results for Primal-Dual Quasi-Newton Interior-Point Method for Nonlinear Programming

Two classes of primal-dual interior-point methods for nonlinear programming are studied. The first class corresponds to a path-following Newton method formulated in terms of the nonnegative variables rather than all primal and dual variables. The centrality condition is a relaxation of the perturbed Karush-Kuhn-Tucker condition and primarily forces feasibility in the constraints. In order to globalize the method using a linesearch strategy, a modified augmented Lagrangian merit function is defined in terms of the centrality condition. The second class is the Quasi-Newton interior-point methods. In this class the well-known Boggs-Tolle-Wang characterization of Q-Superlinear convergence for Quasi-Newton method for equality constrained optimization is extended. Critical issues in this extension are the choice of the centering parameter, the choice of the steplength parameter, and the choice of the primary variables.

May 1997

A New Class of Preconditioners for Large-Scale Linear Systems from Interior-Point Methods for Linear Programming

A new class of preconditioners for the iterative solution of the linear systems arising from interior point methods is proposed. For many of these methods, the linear systems come from applying Newton's method on the perturbed Karush-Kuhn-Tucker optimality conditions for the linear programming problem. This leads to a symmetric indefinite linear system called the augmented system. This system can be reduced to the Schur complement system which is positive definite. After the reduction, the solution for the linear system is usually computed via the Cholesky factorization. This factorization can be dense for some classes of problems. Therefore, the solution of these systems by iterative methods must be considered. Since these systems are very ill-conditioned near a solution of the linear programming problem, it is crucial to develop efficient preconditioners. We show that from the point of view of designing preconditioners, it is better to work with the augmented system. We show that all preconditioners for the Schur complement system have an equivalent for the augmented system while the opposite is not true. The theoretical properties of the new preconditioners are discussed. This class works better near a solution of the linear programming problem when the linear systems are highly ill-conditioned. Another important feature is the option to reduce the preconditioned indefinite system to a positive definite one of the size of the Schur complement. This class of preconditioners relies on the computation of an LU factorization of a subset of columns of the matrix of constraints. The techniques developed for a competitive implementation are rather sophisticated since the subset of columns is not known a priori. The new preconditioner applied to the conjugate gradient method compares favorably with the Cholesky factorization approach. The new approach performs better on large scale problems whose Cholesky factorization contains a large number of nonzero entries. Numerical experiments on several representative classes of linear programming problems are presented to indicate the promise of this new approach.

April 1997

The Solution of a Class of Limited Diversification Portfolio Selection Problems

A branch-and-bound algorithm for the solution of a class of mixed-integer nonlinear programming problems arising from the field of investment portfolio selection is presented. The problems in this class are characterized by the inclusion of the fixed transaction costs associated with each asset, a constraint that explicitly limits the number of distinct assets in the selected portfolio, or both. Modeling either of these forms of limiting the cost of owning an investment portfolio involves the introduction of binary variables, resulting in a mathematical programming problem that has a nonconvex feasible set. Two objective functions are examined in this thesis; the first is a positive definite quadratic function which is commonly used in the selection of investment portfolios. The second is a convex function that is not continuously differentiable; this objective function, although not as popular as the first, is, in many cases, a more appropriate objective function. To take advantage of the structure of the model, the branch-and-bound algorithm is not applied in the standard fashion; instead, we generalize the implicit branch-and-bound algorithm introduced by Bienstock (Math. Prog., 1996). This branch-and-bound algorithm adopts many of the standard techniques from mixed-integer linear programming, including heuristics for finding feasible points and cutting planes. Implicit branch-and-bound involves the solution of a sequence of subproblems of the original problem, and thus it is necessary to be able to solve these subproblems efficiently. For each of the two objective functions, we develop an algorithm for solving its corresponding subproblems; these algorithms exploit the structure of the constraints and the objective function, simplifying the solution of the resulting linear systems. Convergence for each algorithm is proven.

Results are provided for computational experiments performed on investment portfolio selection problems for which the cardinality of the universe of assets available for inclusion in the selected portfolio ranges in size from 52 to 1140.

April 1997

On the Fundamental Role of Interior-Point Methodology in Constrained Optimization

Recently, primal-dual interior-point methodology has proven to be an effective tool in linear programming applications and is now being extended, with great enthusiasm, to general nonlinear programming applications. The primary purpose of this current study is to develop and promote the belief that since Newton's method is a tool for square nonlinear systems of equations, the fundamental role of interior-point methodology in inequality constrained optimization is to produce, in a meaningful and effective manner, a square system of nonlinear equations that represents the inequality constrained optimization problem sufficiently well that the application of Newton's method methodology to this square system is effective and successful.

April 1997

An Investigation of the Optimal Design of the Tallest Unloaded Column

The problem of the optimal design of the tallest unloaded column is revisited with a view towards clarifying the optimality of the design proposed by Keller & Niordson in 1966. (J.B. Keller and F.I. Niordson. The Tallest Column. Jour. Math. Mech., 16(5):433-446, 1966.) The first eigenvalue of a singular Sturm-Liouville problem must be maximized in order to yield the tallest column. The difficulty with the proposed design comes from the nature of the spectrum associated with it. If this spectrum were discrete, Keller & Niordson's techniques would have been appropriate. The proposed design is shown here to admit continuous spectra and hence warrants further investigation.

Over a class of admissible designs admitting purely discrete spectra, it is shown that the decreasing rearrangement of the shape leads to a column at least as tall as the original. Existence of an optimal design follows from this fact. Similar methods are applied to design problems arising from other classes of Sturm-Liouville problems.

The necessary conditions for optimality established by Keller & Niordson are re-established using generalized gradient methods. Using a finite element approximation to the boundary value problem, the first eigenvalue is maximized using MATLAB's Sequential Quadratic Programming implementation (Andrew Grace. Optimization Toolbox for use with Matlab. The Math Works, Inc.) to optimize and Radke's implementation of the Implicitly Restarted Arnoldi Method (R.J. Radke. A Matlab Implementation of the Implicitly Restarted Arnoldi Method for Solving Large-Scale Eigenvalue Problems. Master's thesis, Rice University, 1996. Computational and Applied Mathematics.) to compute eigenvalues. Analysis of the convergence behavior of the higher eigenvalues leads to the conclusion that the spectrum of the Keller & Niordson design is made up of an essential spectrum and one isolated eigenvalue. This justifies the methods used by Keller & Niordson and confirms the optimality of their design.

Finally, inverse spectral methods are investigated as a means by which to increase the height of a given column by adding or subtracting material appropriately.

April 1997

Global Analysis of Linearized Inversion for the Acoustic Wave Equation

To predict the location of natural resources and reduce the cost of exploration, geophysicists rely on various techniques to map the internal structure of the earth. One common mapping method probes the earth's interior using an acoustic energy source (sound waves). The acoustic waves reflect when they impinge on a location where the acoustic velocity field oscillates rapidly (on the scale of a wavelength). When the waves reflect back to the surface, they carry kinematical information about the location of the oscillatory velocity field.

A linearized wave equation models the scattering process and its solution operator is a Fourier integral operator. As such, the scattering operator has a canonical relation lambda which describes how the operator maps oscillatory velocity fields to oscillatory wave fields at the surface. The goal of linearized inversion is to obtain an inverse operator (with inverse canonical relation) for the scattering operator. We give a geometrical condition on lambda that is equivalent to the existence of a linearized inversion operator.

Since the L^2-adjoint of the scattering operator has inverse canonical relation, geophysicists often apply it to the scattered field to obtain a map of the subsurface. I analyze the scattering operator using high-frequency asymptotics and show that if the geometrical condition fails, the scattering canonical relation is not injective. Therefore, application of the adjoint operator to the scattered wave field can produce artifacts in the resulting map of the subsurface. I demonstrate this effect numerically. I also prove that the scattering operator is continuous between a certain domain and range space iff the geometrical condition on lambda holds. Furthermore, I have shown that it is possible to map an experiment where the geometrical condition fails into another experiment where it holds.

April 1997

Nonlinear Multicriteria Optimization and Robust Optimality

This dissertation attempts to address two important problems in systems engineering, namely, multicriteria optimization and robustness optimization. In fields ranging from engineering to the social sciences, designers are very often required to make decisions that attempt to optimize several criteria or objectives at once. Mathematically this amounts to finding the Pareto optimal set of points for these constrained multiple criteria optimization problems which happen to be nonlinear in many realistic situations, particularly in engineering design.

Traditional techniques for nonlinear multicriteria optimization suffer from various drawbacks. The popular method of minimizing weighted sums of the multiple objectives suffers from the deficiency that choosing an even spread of `weights' does not yield an even spread of points on the Pareto surface and further this spread is often quite sensitive to the relative scales of the functions. A continuation/homotopy based strategy for tracing out the Pareto curve tries to make up for this deficiency, but unfortunately requires exact second derivative information and further cannot be applied to problems with more than two objectives in general. Another technique, goal programming, requires prior knowledge of feasible goals which may not be easily available for more than two objectives.

Normal-Boundary Intersection (NBI), a new technique introduced in this dissertation, overcomes all of the difficulties inherent in the existing techniques by introducing a better parametrization of the Pareto set. It is rigorously proved that NBI is completely independent of the relative scales of the functions and is quite successful in producing an evenly distributed set of points on the Pareto set given an evenly distributed set of `NBI parameters' (comparable to the `weights' in minimizing weighted sums of objectives). Further, this method can easily handle more than two objectives while retaining the computational efficiency of continuation-type algorithms, which is an improvement over homotopy techniques for tracing the trade-off curve. Various aspects of NBI including computational issues and its relationships with minimizing convex combinations and goal programming are discussed in this dissertation. Finally some case studies from engineering disciplines are performed using NBI.

The other facet of this dissertation deals with robustness optimization, a concept useful in quantifying the stability of an optimum in the face of random fluctuations in the design variables. This robustness optimization problem is presented as an application of multicriteria optimization since it essentially involves the simultaneous minimization of two criteria, the objective function value at a point and the dispersion in the function values in a neighborhood of the point. Moreover, a formulation of the robustness optimization problem is presented so that it fits the framework of constrained, nonlinear optimization problems, which is an improvement on existing formulations that deal with either unconstrained nonlinear formulations or constrained linear formulations.

April 1997

Superlinear Convergence of Affine-Scaling Interior-Point Newton Methods for Infinite-Dimensional Problems with Pointwise Bounds

We develop and analyze a superlinearly convergent affine-scaling interior-point Newton method for infinite-dimensional problems with pointwise bounds in L^{p}-space. The problem formulation is motivated by optimal control problems with L^{p}-controls and pointwise control constraints. The finite-dimensional convergence theory by Coleman and Li (SIAM J. Optim., 6 (1996), pp. 418-445) makes essential use of the equivalence of norms and the exact identifiability of the active constraints close to an optimizer with strict complementarity. Since these features are not available in our infinite-dimensional framework, algorithmic changes are necessary to ensure fast local convergence. The main building block is a Newton-like iteration for an affine-scaling formulation of the KKT-condition. We demonstrate in an example that a stepsize rule to obtain an interior iterate may require very small stepsizes even arbitrarily close to a nondegenerate solution. Using a pointwise projection instead we prove superlinear convergence under a weak strict complementarity condition and convergence with Q-rate >1 under a slightly stronger condition if a smoothing step is available. We discuss how the algorithm can be embedded in the class of globally convergent trust-region interior-point methods recently developed by M. Heinkenschloss and the authors. Numerical results for the control of a heating process confirm our theoretical findings.

March 1997

Global Convergence of Trust-Region Interior-Point Algorithms for Infinite-Dimensional Nonconvex Minimization Subject to Pointwise Bounds

A class of interior-point trust-region algorithms for infinite-dimensional nonlinear optimization subject to pointwise bounds in L^{p}-Banach spaces, 2 <= p <= infinity, is formulated and analyzed. The problem formulation is motivated by optimal control problems with L^{p}-controls and pointwise control constraints. The interior-point trust-region algorithms are generalizations of those recently introduced by Coleman and Li (SIAM J. Optim., 6 (1996), pp. 418-445) for finite-dimensional problems. Many of the generalizations derived in this paper are also important in the finite-dimensional context. They lead to a better understanding of the method and to considerable improvements in their performance. All first- and second-order global convergence results known for trust-region methods in the finite-dimensional setting are extended to the infinite-dimensional framework of this paper.

March 1997 (revised October 1997)

[SIAM J. Control Optim. 37 (1999), no. 3, 731-764.]

Computing Distances Between Convex Sets and Subsets of the Positive Semidefinite Matrices

We describe an important class of semidefinite programming problems that has received scant attention in the optimization community. These problems are derived from considerations in distance geometry and multidimensional scaling and therefore arise in a variety of disciplines, e.g. computational chemistry and psychometrics. In most applications, the feasible positive semidefinite matrices are restricted in rank, so that recent interior-point methods for semidefinite programming do not apply. We establish some theory for these problems and discuss what remains to be accomplished.

March 1997

Numerical Optimization Using Computer Experiments

Engineering design optimization often gives rise to problems in which expensive objective functions are minimized by derivative-free methods. We propose a method for solving such problems that synthesizes ideas from the numerical optimization and computer experiment literatures. Our approach relies on kriging known function values to construct a sequence of surrogate models of the objective function that are used to guide a grid search for a minimizer. Results from numerical experiments on a standard test problem are presented.

March 1997 (Revised August 1999)

Robustness Optimization for Constrained, Nonlinear Programming Problems

In realistic situations, engineering designs should take into consideration random aberrations from the stipulated design variables arising from manufacturing variability. Moreover, many environmental parameters are often stochastic in nature. Traditional nonlinear optimization attempts to find a deterministic optimum of a cost function and does not take into account the effect of these random variations on the objective. This paper attempts to devise a technique for finding optima of constrained nonlinear functions that are robust with respect to such variations.

The expectation of the function over a domain of aberrations in the parameters is taken as a measure of `robustness' of the function value at a point. It is pointed out that robustness optimization is ideally an attempt to trade off between `optimality' and `robustness'. A newly-developed multicriteria optimization technique, known as Normal-Boundary Intersection, is used here to find evenly-spaced points on the Pareto curve for the `optimality' and `robustness' criteria. This Pareto curve enables the user to make the trade-off decision explicitly free of arbitrary `weighting' parameters.

This paper also formulates a derivative-based approximation for evaluating the expected value of the objective function on the nonlinear manifold defined by the state equations for the system. Existing procedures for evaluating the expectation usually involve numerical integration techniques requiring many solutions of the state equations for one evaluation of the expectation. The procedure presented here bypasses the need for multiple solutions of the state equations and hence provides a cheaper and more easily optimizable approximation to the expectation. Finally, this paper discusses how nonlinear inequality constraints should be treated in the presence of random parameters in the design. Computational results are presented for finding a robust optimum of a structural optimization problem.

March 1997

Go to 1996 reports

Go to 1998 reports