On the convergence of a class of derivative-free minimization algorithms

A convergence analysis is presented for a general class of derivative-free algorithms for minimizing a functionf(x) for which the analytic form of the gradient and the Hessian is impractical to obtain. The class of algorithms accepts finite-difference approximation to the gradient, with stepsizes chosen in such a way that the length of the stepsize must meet two conditions involving the previous stepsize and the distance from the last estimate of the solution to the current estimate. The algorithms also maintain an approximation to the second-derivative matrix and require that the change inx made at each iteration be subject to a bound that is also revised automatically. The convergence theorems have the features that the starting pointx ¹ need not be close to the true solution andf(x) need not be convex. Furthermore, despite the fact that the second-derivative approximation may not converge to the true Hessian at the solution, the rate of convergence is still Q-superlinear. The theorry is also shown to be applicable to a modification of Powell's dog-leg algorithm.     

On the use of some known methods forT-colorings of graphs

A generalization of the classical graph coloring model is studied in this paper. The problem we are interested in is a variant of the generalT-coloring problem related in the literature. We want to color the vertices of a graph in such a way that the two colors assigned to two adjacent verticesi andj differ by at least _ij , wheret _ij is a fixed coefficient associated to the edge [i, j]. The goal is to minimize the length of the spectrum of colors used. We present here the results produced by well-known heuristics (tabu search and simulated annealing) applied to the considered problem. The results are compared with optimal colorings obtained by a branch-and-bound algorithm.     

Numerosities of labelled sets: a new way of counting

The notions of “labelled set” and “numerosity” are introduced to generalize the counting process of finite sets. The resulting numbers, called numerosities, are then used to develop nonstandard analysis. The existence of a numerosity function is equivalent to the existence of a selective ultrafilter, hence it is independent of the axioms of ZFC.     

S-types of Global Towers of Spaces and Exterior Spaces

The closed model category of exterior spaces, that contains the proper category, is a useful tool for the study of non compact spaces and manifolds. The notion of exterior weak ℕ-S-equivalences is given by exterior maps which induce isomorphisms on the k-th ℕ-exterior homotopy groups for k ∈ S, where S is a set of non negative integers. The category of exterior spaces with a base ray localized by exterior weak ℕ-S-equivalences is called the category of exterior ℕ-S-types. The existence of closed model structures in the category of exterior spaces permits to establish equivalences between homotopy categories obtained by dividing by exterior homotopy relations, and categories of fractions (localized categories) given by the inversion of classes of week equivalences. The family of neighbourhoods ‘at infinity’ of an exterior space can be interpreted as a global prospace and under the condition of first countable at infinity we can consider a global tower instead of a prospace. The objective of this paper is to use localized categories to find the connection between S-types of exterior spaces and S-types of global towers of spaces. The main result of this paper establishes an equivalence between the category of S-types of rayed first countable exterior spaces and the category of S-types of global towers of pointed spaces. As a consequence of this result, categories of global towers of algebraic models localized up to weak equivalences can be used to give some algebraic models of S-types. The authors acknowledge the financial support given by the projects FOMENTA 2007/03 and MTM2007-65431.     

Partitions of sets of matrices

The set of all 2×2 matrices with elements from a given set Ω is partitioned into a finite number of classes. The principal object of this paper is to estimate how small a matrix is guaranteed to contain an r×s submatrix all of whose 2×2 submatrices belong to one class only. This problem includes a number of particular situations that had previously been considered in isolation. One of the tools employed is a generalization of the notion of partial order.     

A Connection Between the Reticulation of a Ring of Quotients and the Localization Lattice of the Reticulation of a Commutative Ring

Through this article, R denotes a commutative ring with identity. The aim of this article is to construct a morphism of lattices between the reticulation of a ring of quotients (of a commutative ring with respect to a Gabriel topology) and the localization lattice of the reticulation of the initial ring. The article is structured as follows: The first section introduces all the necessary notions required to simplify the reading of the article. The second section presents some properties of the topology induced by a Gabriel topology on the reticulation L(R). In the third section the morphism δ, which achieves the intended link, is constructed. The last section studies the defined morphism in some particular cases.     

Perturbation of the SVD in the presence of small singular values

This paper gives SVD perturbation bounds and expansions that are of use when an m × n, m ? n matrix A has small singular values. The first part of the paper gives subspace bounds that are closely related to those of Wedin but are stated so as to isolate the effect of any small singular values to the left singular subspace. In the second part first and second order approximations are given for perturbed singular values. The subspace bounds are used to show that all approximations retain accuracy when applied to small singular values. The paper concludes by deriving a subspace bound for multiplicative perturbations and using that bound to give a simple approximation to a singular value perturbed by a multiplicative perturbation.     

Finite-dimensional points of continuity of Lat

Associated with every linear transformation A on a finite-dimensional vector space V there is a collection Lat A of subspaces of V, namely the subspaces invariant under A. The collection lat A always contains the (trivial) subspace 0 and the (improper) subspace V. Since, moreover, it is closed under the formation of intersections and spans, it forms a lattice with respect to those operations (whence its name). The purpose of this paper is to interpret and to prove the following assertion: anecessary and sufficient condition that a linear transformation on a finite-dimensionalcomplex vector space be a point of continuity of Lat is that it be non-derogatory. The assumption that the underlying coefficient field is the set of complex numbers is maintained throughout.     

Orbits of unbounded energy in quasi-periodic perturbations of geodesic flows

We show that certain mechanical systems, including a geodesic flow in any dimension plus a quasi-periodic perturbation by a potential, have orbits of unbounded energy.The assumptions we make in the case of geodesic flows are:

(a)

The metric and the external perturbation are smooth enough.

(b)

The geodesic flow has a hyperbolic periodic orbit such that its stable and unstable manifolds have a tranverse homoclinic intersection.

(c)

The frequency of the external perturbation is Diophantine.

(d)

The external potential satisfies a generic condition depending on the periodic orbit considered in (b).

The assumptions on the metric are C² open and are known to be dense on many manifolds. The assumptions on the potential fail only in infinite codimension spaces of potentials.The proof is based on geometric considerations of invariant manifolds and their intersections. The main tools include the scattering map of normally hyperbolic invariant manifolds, as well as standard perturbation theories (averaging, KAM and Melnikov techniques).We do not need to assume that the metric is Riemannian and we obtain results for Finsler or Lorentz metrics. Indeed, there is a formulation for Hamiltonian systems satisfying scaling hypotheses. We do not need to make assumptions on the global topology of the manifold nor on its dimension.     

An application of cooperative game among container terminals of one port

In this paper a two-stage game that involves three container terminals located in Karachi Port in Pakistan is discussed. In the first stage, the three terminals have to decide on whether to act as a singleton or to enter into a coalition with one or both of the other terminals. The decision at this stage should presumably be based on the predicted outcome for the second stage. The second stage is here modelled as a Bertrand game with one outside competitor, the coalition and the terminal in Karachi Port (if any) that has not joined the coalition. Furthermore, three partial and one grand coalition among the three terminals at Karachi Port are investigated. The concepts of “characteristic function” and “core” are used to analyse the stability of these coalitions and this revealed that one combination does not satisfy the superadditivity property of the characteristic function and can therefore be ruled out. The resulting payoffs (profits) of these coalitions are analysed on the basis of “core”. The best payoff for all players is in the case of a “grand coalition”. However, the real winner is the outsider (the terminal at the second port) which earns a better payoff without joining the coalition, and hence will play the role of the “orthogonal free-rider”.     

On the regularity of the distribution of the maximum of one-parameter Gaussian processes

The main result in this paper states that if a one-parameter Gaussian process has C ^2k paths and satisfies a non-degeneracy condition, then the distribution of its maximum on a compact interval is of class C ^k . The methods leading to this theorem permit also to give bounds on the successive derivatives of the distribution of the maximum and to study their asymptotic behaviour as the level tends to infinity. Received: 14 May 1999 / Revised version: 18 October 1999 / Published online: 14 December 2000     

Optimal construction of a selection of a subpopulation

Summary The problem of selecting a subpopulation from a given populationII is to be, on the basis of measurements of members ofII, achieved by choosing those members ofII who satisfy the standards determined by a given selection cirterion and rejecting those who do not. Since the optimum selection depends on the unknown parameter of the probability distribution ofII, it is here considered how to construct a decision function from the space of subsidiary sample having infor-mation on θ to the space of selections. Thus the existence of Bayes and minimax decision functions under the constraint defined by the selection criterion is proved. A necessary and sufficient condition for a decision function satisfying the constraint to be a Bayes decision function is also obtained. The Institute of Statistical Mathematics     

A Semantic Resolution of the Paradox of Analysis

The paradox of analysis has been a problem for analytic philosophers at least since Moore’s time, and it is especially significant for those who seek an account of analysis along classical lines. The present paper offers a new solution to the paradox, where a theory of analysis is given where (1) analysandum and analysans are distinct concepts, due to their failing to share the same conceptual form, yet (2) they are related in virtue of satisfying various semantic constraints on the analysis relation. Rather than distinguish between analysandum and analysans by appeal to epistemic considerations, the paper appeals to semantic considerations in giving a candidate account of the identity conditions for concepts. The distinctness of analysandum and analysans then serves to block the paradox in a straightforward way.

The Friedrichs Extension of a Pair of Operators

Abstract

An extension of a pair of linear unbounded operators which map from a Banach space X to a Hilbert space Y is constructed and studied. The purpose of the extension is to obtain a pair of jointly closed operators which will be the generating pair of a B-evolution similar to the classical Friedrichs extension of a single operator which generates a holomorphic semigroup. The construction is based on spectral methods.     

Dynamics of a two-frequency parametrically driven duffing oscillator

Summary We investigate the transition from two-frequency quasiperiodicity to chaotic behavior in a model for a quasiperiodically driven magnetoelastic ribbon. The model system is a two-frequency parametrically driven Duffing oscillator. As a driving parameter is increased, the route to chaos takes place in four distinct stages. The first stage is a torus-doubling bifurcation. The second stage is a transition from the doubled torus to a strange nonchaotic attractor. The third stage is a transition from the strange nonchaotic attractor to a geometrically similar chaotic attractor. The final stage is a hard transition to a much larger chaotic attractor. This latter transition arises as the result of acrisis, the characterization of which is one of our primary concerns. Numerical evidence is given to indicate that the crisis arises from the collision of the chaotic attractor with the stable manifold of a saddle torus. Intermittent bursting behavior is present after the crisis with the mean time between bursts scaling as a power law in the distance from the critical control parameter; τ ∼ (A-A_c)^-α. The critical exponent is computed numerically, yielding the value α=1.03±0.01. Theoretical justification is given for the computed critical exponent. Finally, a Melnikov analysis is performed, yielding an expression for transverse crossings of the stable and unstable manifolds of the crisis-initiating saddle torus.     

Classification of extensions of classifiable -algebras

For a certain class of extensions of C^*-algebras in which B and A belong to classifiable classes of C^*-algebras, we show that the functor which sends to its associated six term exact sequence in K-theory and the positive cones of K₀(B) and K₀(A) is a classification functor. We give two independent applications addressing the classification of a class of C^*-algebras arising from substitutional shift spaces on one hand and of graph algebras on the other. The former application leads to the answer of a question of Carlsen and the first named author concerning the completeness of stabilized Matsumoto algebras as an invariant of flow equivalence. The latter leads to the first classification result for nonsimple graph C^*-algebras.     

Construction and asymptotic stability of structurally stable internal layer solutions

We introduce a geometric/asymptotic method to treat structurally stable internal layer solutions. We consider asymptotic expansions of the internal layer solutions and the critical eigenvalues that determine their stability. Proofs of the existence of exact solutions and eigenvalue-eigenfunctions are outlined.

Multi-layered solutions are constructed by a new shooting method through a sequence of pseudo Poincaré mappings that do not require the transversality of the flow to cross sections. The critical eigenvalues are determined by a coupling matrix that generates the SLEP matrix. The transversality of the shooting method is related to the nonzeroness of the critical eigenvalues.

An equivalent approach is given to mono-layer solutions. They can be determined by the intersection of a fast jump surface and a slow switching curve, which reduces Fenichel's transversality condition to the slow manifold. The critical eigenvalue is determined by the angle of the intersection.

We present three examples. The first treats the critical eigenvalues of the system studied by Angenent, Mallet-Paret & Peletier. The second shows that a key lemma in the SLEP method may not hold. The third is a perturbed activator-inhibitor system that can have any number of mono-layer solutions. Some of the solutions can only be found with the new shooting method.