A semidefinite framework for trust region subproblems with applications to large scale minimization

Primal-dual pairs of semidefinite programs provide a general framework for the theory and algorithms for the trust region subproblem (TRS). This latter problem consists in minimizing a general quadratic function subject to a convex quadratic constraint and, therefore, it is a generalization of the minimum eigenvalue problem. The importance of (TRS) is due to the fact that it provides the step in trust region minimization algorithms. The semidefinite framework is studied as an interesting instance of semidefinite programming as well as a tool for viewing known algorithms and deriving new algorithms for (TRS). In particular, a dual simplex type method is studied that solves (TRS) as a parametric eigenvalue problem. This method uses the Lanczos algorithm for the smallest eigenvalue as a black box. Therefore, the essential cost of the algorithm is the matrix-vector multiplication and, thus, sparsity can be exploited. A primal simplex type method provides steps for the so-called hard case. Extensive numerical tests for large sparse problems are discussed. These tests show that the cost of the algorithm is 1 +α(n) times the cost of finding a minimum eigenvalue using the Lanczos algorithm, where 0<α(n)<1 is a fraction which decreases as the dimension increases. Research supported by the National Science and Engineering Research Council Canada.     

Adaptive eigenvalue computation: complexity estimates

This paper is concerned with the design and analysis of a fully adaptive eigenvalue solver for linear symmetric operators. After transforming the original problem into an equivalent one formulated on ℓ ₂, the space of square summable sequences, the problem becomes sufficiently well conditioned so that a gradient type iteration can be shown to reduce the error by some fixed factor per step. It then remains to realize these (ideal) iterations within suitable dynamically updated error tolerances. It is shown under which circumstances the adaptive scheme exhibits in some sense asymptotically optimal complexity. This research was supported in part by the Leibniz Programme of the DFG, by the SFB 401 funded by DFG, the DFG Priority Program SPP1145 and by the EU NEST project BigDFT.     

Global error estimation with adaptive explicit Runge-Kutta methods

Users of locally-adaptive software for initial value ordinarydifferential equations are likely to be concerned with globalerrors. At the cost of extra computation, global error estimationis possible. Zadunaisky's method and ‘solving for theerror estimate’ are two techniques that have been successfullyincorporated into Runge-Kutta algorithms. The standard erroranalysis for these techniques, however, does not take accountof the stepsize selection mechanism. In this paper, some newresults are presented which, under suitable assumptions showthat these techniques are asymptotically valid when used withan adaptive, variable stepsize algorithm—the global errorestimate reproduces the leading term of the global error inthe limit as the error tolerance tends to zero. The analysisis also applied to Richardson extrapolation (step halving).Numerical results are provided for the technique of solvingfor the error estimate with several Runge-Kutta methods of Dormand,Lockyer, McGorrigan and Prince.     

带有固定步长的非单调自适应信赖域算法

提出了求解无约束优化问题带有固定步长的非单调自适应信赖域算法.信赖域半径的修正采用自适应技术,算法在试探步不被接受时,采用固定步长寻找下一迭代点.并在适当的条件下,证明算法具有全局收敛性和超线性收敛性.初步的数值试验表明算法对高维问题具有较好的效果.     

Probabilistic and deterministic convergence proofs for software for initial value problems

The numerical solution of initial value problems for ordinary differential equations is frequently performed by means of adaptive algorithms with user-input tolerance τ. The time-step is then chosen according to an estimate, based on small time-step heuristics, designed to try and ensure that an approximation to the local error commited is bounded by τ. A question of natural interest is to determine how the global error behaves with respect to the tolerance τ. This has obvious practical interest and also leads to an interesting problem in mathematical analysis. The primary difficulties arising in the analysis are that: (i) the time-step selection mechanisms used in practice are discontinuous as functions of the specified data; (ii) the small time-step heuristics underlying the control of the local error can break down in some cases. In this paper an analysis is presented which incorporates these two difficulties. For a mathematical model of an error per unit step or error per step adaptive Runge–Kutta algorithm, it may be shown that in a certain probabilistic sense, with respect to a measure on the space of initial data, the small time-step heuristics are valid with probability one, leading to a probabilistic convergence result for the global error as τ→0. The probabilistic approach is only valid in dimension m>1 this observation is consistent with recent analysis concerning the existence of spurious steady solutions of software codes which highlights the difference between the cases m=1 and m>1. The breakdown of the small time-step heuristics can be circumvented by making minor modifications to the algorithm, leading to a deterministic convergence proof for the global error of such algorithms as τ→0. An underlying theory is developed and the deterministic and probabilistic convergence results proved as particular applications of this theory. This revised version was published online in June 2006 with corrections to the Cover Date.     

An accurate a posteriori error estimator for the Steklov eigenvalue problem and its applications

In this paper, a type of accurate a posteriori error estimator is proposed for the Steklov eigenvalue problem based on the complementary approach, which provides an asymptotic exact estimate for the approximate eigenpair. Besides, we design a type of cascadic adaptive finite element method for the Steklov eigenvalue problem based on the proposed a posteriori error estimator. In this new cascadic adaptive scheme, instead of solving the Steklov eigenvalue problem in each adaptive space directly, we only need to do some smoothing steps for linearized boundary value problems on a series of adaptive spaces and solve some Steklov eigenvalue problems on a low dimensional space. Furthermore, the proposed a posteriori error estimator provides the way to refine mesh and control the number of smoothing steps for the cascadic adaptive method. Some numerical examples are presented to validate the efficiency of the algorithm in this paper.

     

Adaptive solution of elliptic PDE-eigenvalue problems.

In this paper we introduce a new adaptive algorithm (AFEMLA) for elliptic PDE-eigenvalue problems. In contrast to other approaches the algebraic eigenvalue problem does not have to be solved to full accuracy. We incorporate the iterative solution of the resulting finite dimensional algebraic eigenvalue problems in the adaptation process in order to balance the cost with the costs for the iterative eigenvalue method. We present error estimates that incorporate the discretization errors, approximation errors in the eigenvalue solver and roundoff errors. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Numerical solution of Volterra integral and integro-differential equations with rapidly vanishing convolution kernels

Variable stepsize algorithms for the numerical solution of nonlinear Volterra integral and integro-differential equations of convolution type are described. These algorithms are based on an embedded pair of Runge–Kutta methods of order p=5 and p=4 proposed by Dormand and Prince with interpolation of uniform order p=4. They require O(N) number of kernel evaluations, where N is the number of steps. The cost of the algorithms can be further reduced for equations that have rapidly vanishing convolution kernels, by using waveform relaxation iterations after computing the numerical approximation by variable stepsize algorithm on some initial interval. AMS subject classification (2000)  65R20, 45L10, 93C22     

Improving projection‐based eigensolvers via adaptive techniques

We consider subspace iteration (or projection‐based) algorithms for computing those eigenvalues (and associated eigenvectors) of a Hermitian matrix that lie in a prescribed interval. For the case that the projector is approximated with polynomials, we present an adaptive strategy for selecting the degree of these polynomials such that convergence is achieved with near‐to‐optimum overall work without detailed a priori knowledge about the eigenvalue distribution. The idea is then transferred to the approximation of the projector by numerical integration, which corresponds to FEAST algorithm proposed by E. Polizzi in 2009. [E. Polizzi: Density‐matrix‐based algorithm for solving eigenvalue problems. Phys. Rev. B 2009; 79 :115112]. Here, our adaptation controls the number of integration nodes. We also discuss the interaction of the method with search space reduction methods.     

Adaptive Two-Point Stepsize Gradient Algorithm

Combined with the nonmonotone line search, the two-point stepsize gradient method has successfully been applied for large-scale unconstrained optimization. However, the numerical performances of the algorithm heavily depend on M, one of the parameters in the nonmonotone line search, even for ill-conditioned problems. This paper proposes an adaptive nonmonotone line search. The two-point stepsize gradient method is shown to be globally convergent with this adaptive nonmonotone line search. Numerical results show that the adaptive nonmonotone line search is specially suitable for the two-point stepsize gradient method.     

Homotopy spectral sequences and obstructions

For a pointed cosimplicial spaceX ^•, the author and Kan developed a spectral sequence abutting to the homotopy of the total space TotX ^•. In this paper,X ^• is allowed to be unpointed and the spectral sequence is extended to include terms of negative total dimension. Improved convergence results are obtained, and a very general homotopy obstruction theory is developed with higher order obstructions belonging to spectral sequence terms. This applies, for example, to the classical homotopy spectral sequence and obstruction theory for an unpointed mapping space, as well as to the corresponding unstable Adams spectral sequence and associated obstruction theory, which are presented here. Supported in part by NSF Grant DMS-8602432.     

Rayleigh quotient algorithms for nonsymmetric matrix pencils

A classical Rayleigh-quotient iterative algorithm (known as “broken iteration”) for finding eigenvalues and eigenvectors is applied to semisimple regular matrix pencils A − λB. It is proved that cubic convergence is attained for eigenvalues and superlinear convergence of order three for eigenvectors. Also, each eigenvalue has a local basin of attraction. A closely related Newton algorithm is examined. Numerical examples are included. Dedicated to the memory of Gene H. Golub.     

A multigrid preconditioner for an adaptive Black-Scholes solver

This paper is concerned with the efficient solution of the linear systems of equations that arise from an adaptive space-implicit time discretisation of the Black-Scholes equation. These nonsymmetric systems are very large and sparse, so an iterative method will usually be the method of choice. However, such a method may require a large number of iterations to converge, particularly when the timestep used is large (which is often the case towards the end of a simulation which uses adaptive timestepping). An appropriate preconditioner is therefore desirable. In this paper we show that a very simple multigrid algorithm with standard components works well as a preconditioner for these problems. We analyse the eigenvalue spectrum of the multigrid iteration matrix for uniform grid problems and illustrate the method’s efficiency in practice by considering the results of numerical experiments on both uniform grids and those which use adaptivity in space.     

Adaptive computation of smallest eigenvalues of self‐adjoint elliptic partial differential equations

We consider a new adaptive finite element (AFEM) algorithm for self‐adjoint elliptic PDE eigenvalue problems. In contrast to other approaches we incorporate the inexact solutions of the resulting finite‐dimensional algebraic eigenvalue problems into the adaptation process. In this way we can balance the costs of the adaptive refinement of the mesh with the costs for the iterative eigenvalue method. We present error estimates that incorporate the discretization errors, approximation errors in the eigenvalue solver and roundoff errors, and use these for the adaptation process. We show that it is also possible to restrict to very few iterations of a Krylov subspace solver for the eigenvalue problem on coarse meshes. Several examples are presented to show that this new approach achieves much better complexity than the previous AFEM approaches which assume that the algebraic eigenvalue problem is solved to full accuracy. Copyright © 2010 John Wiley & Sons, Ltd.     

New adaptive mixed finite element method (AMFEM)

The need to develop reliable and efficient adaptive algorithms using mixed finite element methods arises from various applications in fluid dynamics and computational continuum mechanics. In order to save degrees of freedom, not all but just some selected set of finite element domains are refined and hence the fundamental question of convergence requires a new mathematical argument as well as the question of optimality. We will present a new adaptive algorithm for mixed finite element methods to solve the model Poisson problem, for which optimal convergence can be proved. The a posteriori error control of mixed finite element methods dates back to Alonso (1996) Error estimators for a mixed method. and Carstensen (1997) A posteriori error estimate for the mixed finite element method. The error reduction and convergence for adaptive mixed finite element methods has already been proven by Carstensen and Hoppe (2006) Error Reduction and Convergence for an Adaptive Mixed Finite Element Method, Convergence analysis of an adaptive nonconforming finite element methods. Recently, Chen, Holst and Xu (2008) Convergence and Optimality of Adaptive Mixed Finite Element Methods. presented convergence and optimality for adaptive mixed finite element methods following arguments of Rob Stevenson for the conforming finite element method. Their algorithm reduces oscillations, before applying and a standard adaptive algorithm based on usual error estimation. The proposed algorithm does this in a natural way, by switching between the reduction of either the estimated error or oscillations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Random algorithms for convex minimization problems

This paper deals with iterative gradient and subgradient methods with random feasibility steps for solving constrained convex minimization problems, where the constraint set is specified as the intersection of possibly infinitely many constraint sets. Each constraint set is assumed to be given as a level set of a convex but not necessarily differentiable function. The proposed algorithms are applicable to the situation where the whole constraint set of the problem is not known in advance, but it is rather learned in time through observations. Also, the algorithms are of interest for constrained optimization problems where the constraints are known but the number of constraints is either large or not finite. We analyze the proposed algorithm for the case when the objective function is differentiable with Lipschitz gradients and the case when the objective function is not necessarily differentiable. The behavior of the algorithm is investigated both for diminishing and non-diminishing stepsize values. The almost sure convergence to an optimal solution is established for diminishing stepsize. For non-diminishing stepsize, the error bounds are established for the expected distances of the weighted averages of the iterates from the constraint set, as well as for the expected sub-optimality of the function values along the weighted averages.     

Steklov eigenvalue problem and its applications An accurate a posteriori error estimator for the

In this paper, a type of accurate a posteriori error estimator is proposed for the Steklov eigenvalue problem based on the complementary approach, which provides an asymptotic exact estimate for the approximate eigenpair. Besides, we design a type of cascadic adaptive finite element method for the Steklov eigenvalue problem based on the proposed a posteriori error estimator. In this new cascadic adaptive scheme, instead of solving the Steklov eigenvalue problem in each adaptive space directly, we only need to do some smoothing steps for linearized boundary value problems on a series of adaptive spaces and solve some Steklov eigenvalue problems on a low dimensional space. Furthermore, the proposed a posteriori error estimator provides the way to refine meshes and control the number of smoothing steps for the cascadic adaptive method. Some numerical examples are presented to validate the efficiency of the algorithm in this paper.     

Halpern Iteration in CAT（k） Spaces

In this paper we show that an iterative sequence generated by the Halpern algorithm converges to a fixed point in the case of complete CAT(κ) spaces. Similar results for Hadamard manifolds were obtained in [Li, C., López, G., Martín-Márquez, V.: Iterative algorithms for nonexpansive mappings on Hadamard manifolds. Taiwanese J. Math., 14, 541–559 (2010)], but we study a much more general case. Moreover, we discuss the Halpern iteration procedure for set-valued mappings.     

The Adaptive Projected Subgradient Method over the Fixed Point Set of Strongly Attracting Nonexpansive Mappings

This paper presents an algorithmic solution, the adaptive projected subgradient method, to the problem of asymptotically minimizing a certain sequence of non-negative continuous convex functions over the fixed point set of a strongly attracting nonexpansive mapping in a real Hilbert space. The method generalizes Polyak's subgradient algorithm for the convexly constrained minimization of a fixed nonsmooth function. By generating a strongly convergent and asymptotically optimal point sequence, the proposed method not only offers unifying principles for many projection-based adaptive filtering algorithms but also enhances the adaptive filtering methods with the set theoretic estimation's armory by allowing a variety of a priori information on the estimandum in the form, for example, of multiple intersecting closed convex sets.     

Modified Proximal-Point Algorithm for Maximal Monotone Operators in Banach Spaces

We introduce an iterative sequence for finding the solution to 0∈T(v), where T : E⇉E ^* is a maximal monotone operator in a smooth and uniformly convex Banach space E. This iterative procedure is a combination of iterative algorithms proposed by Kohsaka and Takahashi (Abstr. Appl. Anal. 3:239–249, 2004) and Kamamura, Kohsaka and Takahashi (Set-Valued Anal. 12:417–429, 2004). We prove a strong convergence theorem and a weak convergence theorem under different conditions respectively and give an estimate of the convergence rate of the algorithm. An application to minimization problems is given. This work was partially supported by the National Natural Sciences Grant 10671050 and the Heilongjiang Province Natural Sciences Grant A200607. The authors thank the referees for useful comments improving the presentation and Professor K. Kohsaka for pointing out Ref. 7.