On Rosen's gradient projection methods

This paper is a survey of Rosen's projection methods in nonlinear programming. Through the discussion of previous works, we propose some interesting questions for further research, and also present some new results about the questions.This work was supported in part by the National Science Foundation of China.     

Variable step-size implementation of sixth-order Numerov-type methods

The explicit sixth-order Numerov-type family of methods is considered. A new representative from this family is produced and equipped with a cheap step-size changing algorithm. Actually, after the completion of a step, this remains the same, halved, or doubled. The off-step points required for such technique are evaluated through local interpolant. Numerical tests over various problems illustrate the efficiency gained by this approach.     

On nonlinear generalized conjugate gradient methods

Summary. The Generalized Conjugate Gradient method (see [1]) is an iterative method for nonsymmetric linear systems. We obtain generalizations of this method for nonlinear systems with nonsymmetric Jacobians. We prove global convergence results. Received April 29, 1992 / Revised version received November 18, 1993     

Two adaptive scaled gradient projection methods for Stiefel manifold constrained optimization

Numerical Algorithms - This article is concerned with the problem of minimizing a smooth function over the Stiefel manifold. In order to address this problem, we introduce two adaptive scaled...     

Optimal approximation of stochastic differential equations by adaptive step-size control

We study the pathwise (strong) approximation of scalar stochastic differential equations with respect to the global error in the -norm. For equations with additive noise we establish a sharp lower error bound in the class of arbitrary methods that use a fixed number of observations of the driving Brownian motion. As a consequence, higher order methods do not exist if the global error is analyzed. We introduce an adaptive step-size control for the Euler scheme which performs asymptotically optimally. In particular, the new method is more efficient than an equidistant discretization. This superiority is confirmed in simulation experiments for equations with additive noise, as well as for general scalar equations.

     

Mean-square convergence of stochastic multi-step methods with variable step-size

We study mean-square consistency, stability in the mean-square sense and mean-square convergence of drift-implicit linear multi-step methods with variable step-size for the approximation of the solution of Itô stochastic differential equations. We obtain conditions that depend on the step-size ratios and that ensure mean-square convergence for the special case of adaptive two-step-Maruyama schemes. Further, in the case of small noise we develop a local error analysis with respect to the h$h$–ε$\epsilon$ approach and we construct some stochastic linear multi-step methods with variable step-size that have order 2 behaviour if the noise is small enough.     

On a modification of a step-size algorithm

In this paper we consider a modification of the Curry-Altman stepsize algorithm. This modification of the Curry-Altman algorithm is based on so called ‘forcing functions’. It is proved that this modified algorithm is well-defined. Further a proof of the convergence of the obtained sequence of points to an optimal solution of the problem of unconstrained optimization is given. Finally, numerical results obtained by use of Fortran IV programs on Facom 230/45 are given.     

On selections and classes of spaces

Strong paracompactness, Lindelöf number and degree of compactness are characterized in terms of selections of set-valued mappings.     

On the asymptotic behaviour of some new gradient methods

The Barzilai-Borwein (BB) gradient method, and some other new gradient methods have shown themselves to be competitive with conjugate gradient methods for solving large dimension nonlinear unconstrained optimization problems. Little is known about the asymptotic behaviour, even when applied to n−dimensional quadratic functions, except in the case that n=2. We show in the quadratic case how it is possible to compute this asymptotic behaviour, and observe that as n increases there is a transition from superlinear to linear convergence at some value of n≥4, depending on the method. By neglecting certain terms in the recurrence relations we define simplified versions of the methods, which are able to predict this transition. The simplified methods also predict that for larger values of n, the eigencomponents of the gradient vectors converge in modulus to a common value, which is a similar to a property observed to hold in the real methods. Some unusual and interesting recurrence relations are analysed in the course of the study.This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grant (no. 10171104)     

On the splitting problem for selections

We investigate when does the Repovš-Semenov splitting problem for selections have an affirmative solution for continuous set-valued mappings in finite-dimensional Banach spaces. We prove that this happens when images of set-valued mappings or even their graphs are P-sets (in the sense of Balashov) or strictly convex sets. We also consider an example which shows that there is no affirmative solution of this problem even in the simplest case in R³. We also obtain affirmative solution of the approximate splitting problem for Lipschitz continuous selections in the Hilbert space.     

Differential gradient methods

A class of recently developed differential descent methods for function minimization is presented and discussed, and a number of algorithms are derived which minimize a quadratic function in a finite number of steps and rapidly minimize general functions. The main characteristics of our algorithms are that a more general curvilinear search path is used instead of a ray and that the eigensystem of the Hessian matrix is associated with the function minimization problem. The curvilinear search paths are obtained by solving certain initial-value systems of differential equations, which also suggest the development of modifications of known numerical integration techniques for use in function minimization. Results obtained on testing the algorithms on a number of test functions are also given and possible areas for future research indicated.     

Duality in conjugate gradient methods

In this paper we show that if the step (displacement) vectors generated by the preconditioned conjugate gradient algorithm are scaled appropriately they may be used to solve equations whose coefficient matrices are the preconditioning matrices of the original equations. The dual algorithms thus obtained are shown to be equivalent to the reverse algorithms of Hegedüs and are subsequently generalised to their block forms. It is finally shown how these may be used to construct dual (or reverse) algorithms for solving equations involving nonsymmetric matrices using only short recurrences, and reasons are suggested why some of these algorithms may be more numerically stable than their primal counterparts. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the integrable selections of certain multifunctions

The aim of this paper is to establish a result of which the following is a particular case: If F is a nonempty closed-valued measurable multifunction, from a nonatomic σ-finite measure space (T, F, μ) into a separable real Banach space E, such that $$d(0,F( \cdot )) \in L^1 (T) and \mathop {\lim }\limits_{\lambda \to + \infty } \frac{{d(\lambda x,F(t))}}{\lambda } = 0$$ for almost every t ∈ T and for every x ∈ E, then each closed hyperplane of L ¹(T,E) contains a selection of F. Also, some consequences are indicated.     

On linear selections of convex set-valued maps

We study continuous subadditive set-valued maps taking points of a linear space X to convex compact subsets of a linear space Y. The subadditivity means that φ(x ₁ + x ₂) ⊂ φ(x ₁) + φ(x ₂). We characterize all pairs of locally convex spaces (X, Y) for which any such map has a linear selection, i.e., there exists a linear operator A: X → Y such that Ax ∈ φ(x), x ∈ X. The existence of linear selections for a class of subadditive maps generated by differences of a continuous function is proved. This result is applied to the Lipschitz stability problem for linear operators in Banach spaces.     

On Lipschitz selections of affine-set valued mappings

We prove a Helly-type theorem for the family of all k-dimensional affine subsets of a Hilbert space H. The result is formulated in terms of Lipschitz selections of set-valued mappings from a metric space (M,r) ({\cal M},\rho) into this family.¶Let F be such a mapping satisfying the following condition: for every subset M￠ ì M {\cal M'} \subset {\cal M} consisting of at most 2^k+1 points, the restriction F|_M￠ F|_{\cal M'} of F to M￠ {\cal M'} has a selection f_M￠ (i.e. f_M￠(x) ? F(x) for all x  ? M￠) f_{\cal M'}\,({\rm i.e.}\,f_{\cal M'}(x) \in F(x)\,{\rm for\,all}\,x\,\in {\cal M'}) satisfying the Lipschitz condition ||f_M￠(x) - f_M￠(y)||  ￡ r(x,y ), x,y ? M￠ \parallel f_{\cal M'}(x) - f_{\cal M'}(y)\parallel\,\le \rho(x,y ),\,x,y \in {\cal M'} . Then F has a Lipschitz selection f : M ? H f : {\cal M} \to H such that ||f(x) - f(y) ||  ￡ gr(x,y ), x,y ? M \parallel f(x) - f(y) \parallel\,\le \gamma \rho (x,y ),\,x,y \in {\cal M} where g = g(k) \gamma = \gamma(k) is a constant depending only on k. (The upper bound of the number of points in M￠ {\cal M'} , 2^k+1, is sharp.)¶The proof is based on a geometrical construction which allows us to reduce the problem to an extension property of Lipschitz mappings defined on subsets of metric trees.     

On some questions on Borel 1 selections

In this paper we continue to investigate conditions under which a multifunction φ:X→2 ^Y admits a Borel 1 selection (see [2]).     

Complex conjugate gradient methods

Linear systems with complex coefficients arise from various physical problems. Examples are the Helmholtz equation and Maxwell equations approximated by finite difference or finite element methods, that lead to large sparse linear systems. When the continuous problem is reduced to integral equations, after discretization, one obtains a dense linear system. The resulting matrices are generally non-Hermitian but, most of the time, symmetric and consequently the classical conjugate gradient method cannot be directly applied. Usually, these linear systems have to be solved with a large number of unknowns because, for instance, in electromagnetic scattering problems the mesh size must be related to the wave length of the incoming wave. The higher the frequency of the incoming wave, the smaller the mesh size must be. When one wants to solve 3D-problems, it is no longer practical to use direct method solvers, because of the huge memory they need. So iterative methods are attractive for this kind of problems, even though their convergence cannot be always guaranteed with theoretical results. In this paper we derive several methods from a unified framework and we numerically compare these algorithms on some test problems.