Convergence Results for Pattern Search Algorithms are Tight

Recently, general definitions of pattern search methods for both unconstrained and linearly constrained optimization were presented. It was shown under mild conditions, that there exists a subsequence of iterates converging to a stationary point. In the unconstrained case, stronger results are derived under additional assumptions. In this paper, we present three small dimensioned examples showing that these results cannot be strengthened without additional assumptions. First, we show that second order optimality conditions cannot be guaranteed. Second, we show that there can be an accumulation point of the sequence of iterates whose gradient norm is strictly positive. These two examples are also valid for the bound constrained case. Finally, we show that even under the stronger assumptions of the unconstrained case, there can be infinitely many accumulation points.

November 1998

Analysis of the Lagrange-SQP-Newton Method for the Control of a Phase Field Equation

This paper investigates the local convergence of the Lagrange-SQP-Newton method applied to an optimal control problem governed by a phase field equation with distributed control. The phase field equation is a system of two semilinear parabolic differential equations. Stability analysis of optimization problems and regularity results for parabolic differential equations are used to prove convergence of the controls with respect to the L²(Q) norm and with respect to the L^{infinity}(Q) norm.

October 1998

The Computational Role of Proximity Measures in Computing Analytic Centers

Fidelity to the central path is a key concept in the design and analysis of most interior-point methods. In these methods the generated iterates are required to remain in a vicinity of the central path of the linear programming problem. Proximity measures define vicinities of the central path and play a fundamental theoretical role in the analysis of interior-point methods. In most practical implementations, however, the iterates are required to remain in a relatively large neighborhood of the central path and a certain proximity measure is often used. On the other hand, one of the main ingredients of interior-point methods that compute the analytic center of the solution set is to confine the iterates to a relatively small neighborhood of the central path. In this paper we present a numerical study that demonstrates that proximity measures play a computationally significant role in designing efficient algorithms for computing analytic centers of linear programming problems.

September 1998

Majorization and Proximity Measures in Optimization

(Abstract not available.)

September 1998

Optimal Face Identification Methods and Bounded Variable Linear Programs

We extend optimal face identification methods to bounded variable linear programming problems. Distance to the lower and upper bounds are incorporated into a projection model and Mehrotra-Ye's solution technique to prevent the computed solution from violating the bound contstraints. Empirical and theoretical evidence are provided that support use of the new models to compute an exact solution. We also introduce a nonlinear weighted projection method to solve the optimal face identification problem.

August 1998

A Large-Scale Trust-Region Approach to the Regularization of Discrete Ill-Posed Problems

We consider the problem of computing the solution of large-scale discrete ill-posed problems when there is noise in the data. These problems arise in important areas such as seismic inversion, medical imaging and signal processing. We pose the problem as a quadratically constrained least squares problem and develop a method for the solution of such problem. Our method does not require factorization of the coefficient matrix, it has very low storage requirements and handles the high degree of singularities arising in discrete ill-posed problems. We present numerical results on test problems and an application of the method to a practical problem with real data.

May 1998

Consulting in Applied Mathematics

This report contains a description of four projects brought to the attention of the Consulting Course, CAAM 513 in the Department of Computational and Applied Mathematics at Rice University. The enclosed reports reflect the work done by Genetha Gray, Nathan Hillson, Shannon Walsh and the instructor Liliana Borcea, in the Spring semester of 1998.

July 1998

Effective Finite Termination Procedures in Interior-Point Methods for Linear Programming

Due to the structure of the solution set, an exact solution to a linear program cannot be computed by an interior-point algorithm without adding features, such as finite termination procedures, to the algorithm. Finite termination procedures attempt to compute an exact solution in a finite number of steps. The addition of a finite termination procedure enables interior-point algorithms to generate highly accurate solutions for problems in which the ill-conditioning of the Jacobian in the neighborhood of the solution currently precludes such accuracy.

The main ingredients of finite termination are activating the procedure, predicting the optimal partition, formulating a simple mathematical model to compute a solution and developing computational techniques to solve the model. Each of these issues are studied in turn in this thesis. First, the current optimal face identification models are extended to bounded variable linear programming problems. Distance to the lower and upper bounds are incorporated into the model to prevent the computed solution from violating the bound constraints. Theory in the literature is extended to the new model. Empirical evidence shows that the proposed model reduces the number of projection attempts needed to find an exact solution. When early termination is the goal, projection from a pure composite Newton step is advocated. However, the cost may exceed the benefits due to the average need of more than one projection attempt to find an exact solution.

Variants of Mehrotra's predictor-corrector primal-dual interior-point algorithm provide the foundation for most practical interior-point codes. To take advantage of all available algorithmic information, we investigate the behavior of the Tapia predictor-corrector indicator, which incorporates the corrector step, to identify the optimal partition. Globally, the Tapia predictor-corrector indicator behaves poorly as do all indicators, but locally exhibits fast convergence.

July 1998

On the Component-Wise Convergence Rate

In this paper we investigate the convergence rate of a sequence of vectors provided that the convergence rates of the components are known. The result of this investigation is then used to study the m-step convergence rate of sequences.

Key words: convergence rate, Q factor, multi-step convergence.

June 1998

An Interior-Point Algorithm for the Maximum-Volume Ellipsoid Problem

In this report, we consider the problem on finding the maximum-volume ellipsoid inscribing a given full-dimensional polytope in R^n defined by a finite set of affine inequalities. We present several formulations for the problem that may serve as algorithmic frameworks for applying interior-point methods. We propose a practical interior-point algorithm based on one of the formulations and present preliminary numerical results.

June 1998 (revised April 1999)

The Finite Element Approximation of Binomial Microstructures

We give improved error analysis and convergence results for weak convergence of deformations gradients of approximate three dimensional crystalline microstructures.  We give lower bounds for the size and number of laminates that nucleate during relaxation of a rotationally invariant, double-well energy density.  We provide lower estimates for macroscopic convergence rates.  We prove Harnack-type inequality for the size of martensitic laminates.

Key words: microstructures, finite elements.

revised May 2000

(Replaced by TR99-20)

Deflation for Implicitly Restarted Arnoldi Methods

The implicitly restarted Arnoldi method (IRAM) is an effective technique for computing a selected subset of the eigenvalues and corresponding eigenvectors of a large matrix A. However, the performance of this method can be improved considerably with the introduction of appropriate deflation schemes to isolate approximate invariant subspaces associated with converged Ritz values. These deflation strategies make it possible to compute multiple or clustered eigenvalues with a single vector implicit restart method.

It is of particular interest to provide schemes that can deflate with user specified relative error tolerances epsilonD that are considerably greater than working precision epsilonM. The primary contribution of this paper is to develop efficient and numerically stable schemes for this purpose. Two forms of deflation are presented. The first, a locking operation, decouples converged Ritz values and associated invariant subspace from the active part of the IRAM iteration. The second, a purging operation, removes unwanted but converged Ritz pairs. Convergence of the IRAM iteration is improved and a reduction in computational effort is also achieved.

June 1998 (under revision as of July 2000)

Three Dimensional Finite Element Modeling of the Earth's Magnetosphere

We demonstrate the feasibility of using a nonconforming finite element method on an unstructured grid in solving a magnetospheric physics problem. We use this approach to construct a global discrete model of the magnetic field of the magnetosphere that includes the effects of shielding currents at the outer boundary (the magnetopause). As in the approach of [17] the internal magnetospheric field model is that of Hilmer and Voigt [3] while the magnetopause shape is based on an empirically-determined approximation [12]. The result is a magnetic field model whose field lines are completely confined within the magnetosphere. The numerical results indicate that the nonconforming discrete model is robust and efficient.

May 1998

A Priori Error Estimates of Finite Element Models of Systems of Shallow Water Equations

In recent years, there has been much interest in the numerical solution of shallow water equations. The numerical procedure used to solve the shallow water equations must resolve the physics of the problem without introducing spurious oscillations or excessive numerical diffusion. Staggered-grid finite difference methods have been used extensively in modeling surface flow without introducing spurious oscillations. Finite element methods, permitting a high degree of grid flexibility for complex geometries and facilitating grid refinement near land boundaries to resolve important processes, have become much more prevalent. However, early finite element simulations of shallow water systems were plagued by spurious oscillations and the various methods introduced to eliminate these oscillations through artificial diffusion were generally unsuccessful due to excessive damping of physical components of the solution.

Here, we give a brief overview on some finite element models of the shallow water equations, with particular attention given to the wave and characteristic formulations. In the literature, standard analysis, based on Fourier decompositions of these methods, has always neglected contributions from the nonlinear terms.

We derive L^{infinity} ((0,T);L² (Omega)) and L² ((0,T);H¹ (Omega)) a priori error estimates for both the continuous-time and discrete-time Galerkin approximation to the nonlinear wave model, finding these to be optimal in H¹ (Omega).

Finally, we derive L^{infinity} ((0,T);L² (Omega)) and L² ((0,T);H¹ (Omega)) a priori error estimates for our proposed Characteristic-Galerkin approximation to the nonlinear primitive model. We find these estimates to be optimal in H¹ (Omega) but with less restrictive time-step constraints when compared to the Galerkin estimates for the wave model.

May 1998

Numerical Solution of Semielliptic Optimal Control Problems Using an SQP Based Optimization Algorithm

(Abstract not available.)

May 1998

A Ferris-Mangisarian Technique Applied to Linear Least Squares Problems

This note specializes to linear least squares problems an approach suggested by Ferris and Mangasarian for solving constrained optimization problems on parallel computers. It will be shown here that this specialization leads to an algorithm which is mathematically equivalent to an acceleration and convergence forcing modification of the block Jacobi iteration applied to the normal equations. The resulting algorithm is a promising way to speed up a parallel multisplitting algorithm of Renaut for linear least squares. Renaut's algorithm is related to a specialization of part of the Ferris and Mangasarian approach.

May 1998

Convergence Analysis of an Inexact Truncated RQ-Iteration

The Truncated RQ-iteration (TRQ) can be used to calculate interior or clustered eigenvalues of a large sparse and/or structured matrix A. This method requires solving a sequence of linear equations. When these equations can be solved accurately by a direct solver, the convergence of each eigenvalue is quadratic in general and cubic if A is hermitian. An important question is whether the TRQ iteration will still converge if these equations are approximately solved by a preconditioned iterative solver. If it does converge, how fast is the convergence rate? In this paper, we analyze the convergence of an inexact TRQ iteration in which linear systems are solved iteratively with some error. We show that under some appropriate conditions, the convergence rate of the inexact TRQ is at least linear with a small convergence factor.

April 1998

[Electron. Trans. Numer. Anal. 7 (1998), 40-55.]

Accelerating the Arnoldi Iteration - Theory and Practice

The Arnoldi iteration is widely used to compute a few eigenvalues of a large sparse or structured matrix. However, the method may suffer from slow convergence when the desired eigenvalues are not dominant or well separated. A systematic approach is taken in this dissertation to address the issue of how to accelerate the convergence of the Arnoldi algorithm within a subspace of limited size.

The acceleration strategies presented here are grouped into three categories. They are the method of restarting, the method of spectral transformation and the Newton-like acceleration.

Simply put, the method of restarting repeats a k-step Arnoldi iteration after improving the starting vector. The method is further divided into polynomial and rational restarting based on the way the starting vector is modified. We show that both mechanisms can be implemented in an implicit fashion by relating the restarted Arnoldi to a truncated QR or the RQ iteration. The rational restarting via a Truncated RQ (TRQ) iteration converges extremely fast. However, a linear system must be solved for each restarting. The possibility of replacing a direct linear solver with a preconditioned iterative solver while maintaining the rapid convergence of TRQ is explored in this thesis.

The method of spectral transformation is based on the idea of transforming the original eigenvalue problem into one that is easier to solve. Again, both polynomial and rational transformations are possible. Practical issues regarding the design and implementation of effective spectral transformations are discussed.

Finally, one can treat the eigenvalue problem as a nonlinear equation upon which Newton-like methods can be applied. The Jacobi-Davidson (JD) algorithm proposed by Sleijpen and Van der Vorst takes this approach. In JD, the Arnoldi iteration is merely used as a global searching tool to provide a good starting point for the Newton iteration. This algorithm shares many similar properties with the TRQ iteration. Numerical comparisons between these two methods are made in this thesis.

April 1998

An Interface Between Optimization and Application for the Numerical Solution of Optimal Control Problems

An interface between the application problem and the nonlinear optimization algorithm is proposed for the numerical solution of distributed optimal control problems. By using this interface, numerical optimization algorithms can be designed to take advantage of inherent problem features like the splitting of the variables into states and controls and the scaling inherited from the functional scalar products. Further, the interface allows the optimization algorithm to make efficient use of user provided function evaluations and derivative calculations.

April 1998

A Home Health Care Routing and Scheduling Problem

Consider the problem of routing a set of nurses from each individual nurse's home to a set of patients and back home again. Each patient must be visited by a single "feasible" nurse during its time window. Essentially, this is a multi-depot vehicle routing problem with time windows with additional feasibility restrictions on which nurses can visit which patients. This problem is NP-Hard. We give mixed integer linear programming formulations of this problem and a parallel tour-building heuristic for finding a good solution.

revised June 1998

An Updated Mixed Integer Programming Library: MIPLIB 3.0

In response to the needs of researchers for access to challenging mixed integer programs, Bixby et al. [1] created MIPLIB, an electronically available library of both pure and mixed integer programs, most of which arise from real-world applications.

Since its introduction, MIPLIB has become a standard test set for comparing the performance of mixed integer optimization codes. Its availability has provided an important stimulus for researchers in this very active area. As technology has progressed, however, there have been significant improvements in state-of-the-art optimizers and computing machinery. Consequently, several instances have become too easy, and a need has emerged for more difficult instances. Also, it has been observed that certain types of problems are overrepresented in MIPLIB and others underrepresented. These considerations have prompted the present update.

Since mixed integer programming is such an active research area, and the performance of optimizers keep improving, we anticipate that this update will not be the last. Subsequent updates are planned on a yearly basis. We encourage both researchers and practitioners in integer programming to submit real-world instances for consideration and possible inclusion in MIPLIB.

This note describes the MIPLIB update.  We have added several new problems and deleted some existing ones.  In addition, we have included, for each problem, certain auxiliary information describing the structure of the constraint matrix.  The purpose of this information is to identify constraint classes that may be useful in the various phases of problem solving, such as preprocessing, constraint generation, and branching.

February 1998

The Behavior of Newton-Type Methods on Two Equivalent Systems from Linear Programming

Newton-type methods are fundamental techniques for solving optimization problems. However, it is often not fully appreciated that these methods can produce significantly different behavior when applied to two equivalent systems. In this paper, we investigate differences in local and global behavior of Newton-type methods when applied to the first-order optimality conditions for the logarithmic barrier formulation of the linear programming problem, and when applied to the perturbed first-order optimality conditions for the linear programming problem. Through theoretical analysis and numerical results, we show that Newton-type methods perform more effectively on the latter system than on the former system.

February 1998

Truncated QZ Methods for Large Scale Generalized Eigenvalue Problems

This paper presents three methods for the large scale generalized eigenvalue problem:

Ax = Bx·lambda

These methods are developed within a subspace projection framework as a truncation and modification of the QZ-algorithm for dense problems that is suitable for computing partial generalized Schur decompostions of the pair (A,B). A generalized partial reduction to condensed form is developed by analogy with the Arnoldi process. Then truncated forward and backward QZ iterations are introduced to derive generalizations of the Implicitly Restarted Arnoldi Method and the Truncated RQ method for the large scale generalized problem. These two methods require accurate solutions of linear systems at each step of the iteration. Relaxing these accuracy requirements forces us to introduce non-Krylov projection spaces that lead most naturally to block variants of the QZ iterations. A two-block method is developed that incorporates k approximate Newton corrections at each iteration. An important feature is the potential to utilize k matrix vector products for each access of the matrix pair (A,B). Preliminary computational experience is presented to compare the three new methods.

February 1998

[Electron. Trans. Numer. Anal. 7 (1998), 141-162.]

Go to 1997 reports

Go to 1999 reports