Search

In this paper it is proposed to equip direct-search methods with a general procedure to minimize an objective function, possibly nonsmooth, without using derivatives and subject to constraints on the variables. One aims at considering constraints, most likely nonlinear or nonsmooth, for which the derivatives of the corresponding functions are also unavailable. The novelty of this contribution relies mostly on how relaxable constraints are handled. Such constraints, which can be relaxed during the course of the optimization, are taken care of by a merit function and, if necessary, by a restoration procedure. Constraints that are unrelaxable. when present, are treated by an extreme barrier approach. One is able to show that the resulting merit function direct-search algorithm exhibits global convergence properties for first-order stationary constraints. As in the progressive barrier method [C. Audet and J. E. Dennis Jr., SIAM J. Optim., 20 (2009), pp. 445-472], we provide a mechanism to indicate the transfer of constraints from the relaxable set to the unrelaxable one. [ABSTRACT FROM AUTHOR]

This work is concerned with the development and study of a minimum residual norm subspace method based on the generalized conjugate residual method with inner orthogonalization (GCRO) method that allows flexible preconditioning and deflated restarting for the solution of non-symmetric or non-Hermitian linear systems. First we recall the main features of flexible generalized minimum residual with deflated restarting (FGMRES-DR), a recently proposed algorithm of the same family but based on the GMRES method. Next we introduce the new inner-outer subspace method named FGCRO-DR. A theoretical comparison of both algorithms is then made in the case of flexible preconditioning. It is proved that FGCRO-DR and FGMRES-DR are algebraically equivalent if a collinearity condition is satisfied. While being nearly as expensive as FGMRES-DR in terms of computational operations per cycle, FGCRO-DR offers the additional advantage to be suitable for the solution of sequences of slowly changing linear systems (where both the matrix and right-hand side can change) through subspace recycling. Numerical experiments on the solution of multidimensional elliptic partial differential equations show the efficiency of FGCRO-DR when solving sequences of linear systems. [ABSTRACT FROM AUTHOR]

The objects of this paper are to introduce range-space variants of standard Krylov iterative solvers for unsymmetric and symmetric linear systems and to discuss how inexact matrix-vector products may be used in this context. The new range-space variants are characterized by possibly much lower storage and computational costs than their full-space counterparts, which is crucial in data assimilation applications and other inverse problems. However, this gain is achieved without sacrificing the inherent monotonicity properties of the original algorithms, which are of paramount importance in data assimilation applications. The use of inexact matrix-vector products is shown to further reduce computational cost in a controlled manner. Formal error bounds are derived on the size of the residuals obtained under two different accuracy models, and it is shown why a model controlling forward error on the product result is often preferable to one controlling backward error on the operator. Simple numerical examples finally illustrate the developed concepts and methods. [ABSTRACT FROM AUTHOR]

This work studies a class of limited memory preconditioners (LMPs) for solving linear (positive-definite) systems of equations with multiple right-hand sides. We propose a class of (LMPs), whose construction requires a small number of linearly independent vectors. After exploring the theoretical properties of the preconditioners, we focus on three particular members: spectral-LMP, quasi-Newton-LMP, and Ritz-LMP. We show that the first tow are well known, while the third is new. Numerical tests indicate that the Ritz-LMP is efficient on a real-life nonlinear optimization problem arising in a data assimilation system for oceanography. [ABSTRACT FROM AUTHOR]

A strict adherence to threshold pivoting in the direct solution of symmetric indefinite problems can result in substantially more work and storage than forecast by a sparse analysis of the symmetric problem. One way of avoiding this is to use static pivoting where the data structures and pivoting sequence generated by the analysis are respected and pivots that would otherwise be very small are replaced by a user defined quantity. This can give a stable factorization but of a perturbed matrix. The conventional way of solving the sparse linear system is then to use iterative refinement, but there are cases where this fails to converge. In this paper, we discuss the use of more robust iterative methods, namely GMRES and flexible GMRES (FGMRES). We show both theoretically and experimentally that both approaches are more robust than iterative refinement and furthermore that FGMRES is far more robust than GMRES and that, under reasonable hypotheses, FGMRES is backward stable. We also show how restarted variants can be beneficial, although again the GMRES variant is not as robust as FGMRES. [ABSTRACT FROM AUTHOR]

This work is the follow-up of the experimental study presented in [A. Bouras and V. Frayssé, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 660-678]. It is based on and extends some theoretical results in [V. Simoncini and D. B. Szyld, SIAM J. Sci. Comput., 25 (2003), pp. 454- 477; J. van den Eshof and G. L. G. Sleijpen, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 125- 153]. In a backward error framework we study the convergence of GMRES when the matrix-vector products are performed inaccurately. This inaccuracy is modeled by a perturbation of the original matrix. We prove the convergence of GMRES when the perturbation size is proportional to the inverse of the computed residual norm; this implies that the accuracy can be relaxed as the method proceeds which gives rise to the terminology "relaxed GMRES." As for the exact GMRES we show under proper assumptions that only happy breakdowns can occur. Furthermore, the convergence can be detected using a byproduct of the algorithm. We explore the links between relaxed rightpreconditioned GMRES and flexible GMRES (FGMRES). In particular, this enables us to derive a proof of convergence of FGMRES. Finally, we report results of numerical experiments to illustrate the behavior of the relaxed GMRES monitored by the proposed relaxation strategies. [ABSTRACT FROM AUTHOR]

The Gauss-Newton algorithm is an iterative method regularly used for solving nonlinear least squares problems. It is particularly well suited to the treatment of very large scale variational data assimilation problems that arise in atmosphere and ocean forecasting. The procedure consists of a sequence of linear least squares approximations to the nonlinear problem, each of which is solved by an "inner" direct or iterative process. In comparison with Newton's method and its variants, the algorithm is attractive because it does not require the evaluation of second-order derivatives in the Hessian of the objective function. In practice the exact Gauss-Newton method is too expensive to apply operationally in meteorological forecasting, and various approximations are made in order to reduce computational costs and to solve the problems in real time. Here we investigate the effects on the convergence of the Gauss-Newton method of two types of approximation used commonly in data assimilation. First, we examine "truncated" Gauss-Newton methods where the inner linear least squares problem is not solved exactly, and second, we examine "perturbed" Gauss-Newton methods where the true linearized inner problem is approximated by a simplified, or perturbed, linear least squares problem. We give conditions ensuring that the truncated and perturbed Gauss-Newton methods converge and also derive rates of convergence for the iterations. The results are illustrated by a simple numerical example. A practical application to the problem of data assimilation in a typical meteorological system is presented. [ABSTRACT FROM AUTHOR]

It is well known that the convergence of the conjugate gradient method for solving symmetric positive definite linear systems depends to a large extent on the eigenvalue distribution. In many cases, it is observed that ‘removing’ the extreme eigenvalues can greatly improve the convergence. Several preconditioning techniques based on approximate eigenelements have been proposed in the past few years that attempt to tackle this problem. The proposed approaches can be split into two main families, depending on whether the extreme eigenvalues are moved exactly to one or are shifted to close to one. The first technique is often referred to as the deflation approach, while the latter is referred to as a coarse grid preconditioner by analogy to techniques first used in domain decomposition methods. Many variants exist in the two families that reduce to the same preconditioners if the exact eigenelements are used. In this paper we investigate the behavior of some of these techniques when the eigenelements are known only approximately. We use the first-order perturbation theory for eigenvalues and eigenvectors to investigate the behavior of the spectrum of the preconditioned systems using first-order approximation. We illustrate the sharpness of the first-order approximation and show the effect of the inexactness of the eigenelements on the behavior of the resulting preconditioner when applied to accelerating the conjugate gradient method. [ABSTRACT FROM AUTHOR]