Variable metric bundle methods: From conceptual to implementable forms

To minimize a convex function, we combine Moreau-Yosida regularizations, quasi-Newton matrices and bundling mechanisms. First we develop conceptual forms using “reversal” quasi-Newton formulae and we state their global and local convergence. Then, to produce implementable versions, we incorporate a bundle strategy together with a “curve-search”. No convergence results are given for the implementable versions; however some numerical illustrations show their good behaviour even for large-scale problems.     

From Hermite to stationary subdivision schemes in one and several variables

Vector and Hermite subdivision schemes both act on vector data, but since the latter one interprets the vectors as function values and consecutive derivatives they differ by the “renormalization” of the Hermite scheme in any step. In this paper we give an algebraic factorization method in one and several variables to relate any Hermite subdivision scheme that satisfies the so–called spectral condition to a vector subdivision scheme. These factorizations are natural extensions of the “zero at π” condition known for the masks of refinable functions. Moreover, we show how this factorization can be used to investigate different forms of convergence of the Hermite scheme and why the multivariate situation is conceptionally more intricate than the univariate one. Finally, we give some examples of such factorizations.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Inverse singularly perturbed problems of the convection-diffusion type in quadrangular curvilinear domains

We have constructed an algorithm for the asymptotic approximation of the solutions of inverse singularly perturbed boundary-value problems of the convection-diffusion type with unknown diffusion coefficient, depending on the coordinates of a quadrangular curvilinear domain of filtration. The case of sufficient smoothness and consistency of the overdetermination, initial, and boundary conditions is considered. Unlike the construction of an algorithm for the solution of similar problems in doubly connected domains, here, in the corresponding relations, there appear corrections taking into account the influence of “lateral sources of pollution.” With the help of this algorithm, we have carried out a computer experiment, the results of which confirm the well-known fact of “strong sensitivity” of the model to assignment of the overdetermination condition. In particular, we have revealed the specific character of influence of this condition on the required diffusion coefficient depending on the filtration velocity.     

Viscosity approximation methods for nonexpansive multimaps in Banach spaces

We prove strong convergence of the viscosity approximation process for nonexpansive nonself multimaps. Furthermore, an explicit iteration process which converges strongly to a fixed point of multimap T is constructed. It is worth mentioning that, unlike other authors, we do not impose the condition ＂Tz = {z}＂ on the map T.     

Relative Convergence Estimates for the Spectral Asymptotic in the Large Coupling Limit

We prove optimal convergence estimates for eigenvalues and eigenvectors of a class of singular/stiff perturbed problems. Our profs are constructive in nature and use (elementary) techniques which are of current interest in computational Linear Algebra to obtain estimates even for eigenvalues which are in gaps of the essential spectrum. Further, we also identify a class of “regular” stiff perturbations with (provably) good asymptotic properties. The Arch Model from the theory of elasticity is presented as a prototype for this class of perturbations. We also show that we are able to study model problems which do not satisfy this regularity assumption by presenting a study of a Schroedinger operator with singular obstacle potential.     

Interaction dynamics of two reinforcement learners

The paper investigates a stochastic model where two agents (persons, companies, institutions, states, software agents or other) learn interactive behavior in a series of alternating moves. Each agent is assumed to perform “stimulus-response-consequence” learning, as studied in psychology. In the presented model, the response of one agent to the other agent's move is both the stimulus for the other agent's next move and part of the consequence for the other agent's previous move. After deriving general properties of the model, especially concerning convergence to limit cycles, we concentrate on an asymptotic case where the learning rate tends to zero (“slow learning”). In this case, the dynamics can be described by a system of deterministic differential equations. For reward structures derived from [2×2] bimatrix games, fixed points are determined, and for the special case of the prisoner's dilemma, the dynamics is analyzed in more detail on the assumptions that both agents start with the same or with different reaction probabilities.     

A new algorithm for generalized fractional programs

A new dual problem for convex generalized fractional programs with no duality gap is presented and it is shown how this dual problem can be efficiently solved using a parametric approach. The resulting algorithm can be seen as “dual” to the Dinkelbach-type algorithm for generalized fractional programs since it approximates the optimal objective value of the dual (primal) problem from below. Convergence results for this algorithm are derived and an easy condition to achieve superlinear convergence is also established. Moreover, under some additional assumptions the algorithm also recovers at the same time an optimal solution of the primal problem. We also consider a variant of this new algorithm, based on scaling the “dual” parametric function. The numerical results, in case of quadratic-linear ratios and linear constraints, show that the performance of the new algorithm and its scaled version is superior to that of the Dinkelbach-type algorithms. From the computational results it also appears that contrary to the primal approach, the “dual” approach is less influenced by scaling. This research was carried out at the Econometric Institute, Erasmus University, Rotterdam, the Netherlands and was supported by J.N.I.C.T. (Portugal) under contract BD/707/90-RM.     

On a size-structured two-phase population model with infinite states-at-birth

In this work, we introduce and analyze a linear size-structured population model with infinite states-at-birth. We model the dynamics of a population in which individuals have two distinct life-stages: an “active” phase when individuals grow, reproduce and die and a second “resting” phase when individuals only grow. Transition between these two phases depends on individuals’ size. First we show that the problem is governed by a positive quasicontractive semigroup on the biologically relevant state space. Then, we investigate, in the framework of the spectral theory of linear operators, the asymptotic behavior of solutions of the model. We prove that the associated semigroup has, under biologically plausible assumptions, the property of asynchronous exponential growth.     

New asymptotic expansion for the Gamma function

Using a series transformation, the Stirling-De Moivre asymptotic series approximation to the Gamma function is converted into a new one with better convergence properties. The new formula is being compared with those of Stirling, Laplace, and Ramanujan for real arguments greater than 0.5 and turns out to be, for equal number of “correction” terms, numerically superior to all of them. As a side benefit, a closed-form approximation has turned up during the analysis which is about as good as 3rd order Stirling’s (maximum relative error smaller than 1e − 10 for real arguments greater or equal to 24).     

Evidence of a natural boundary and nonintegrability of the mixmaster universe model

Summary The formal asymptotic analysis of Latifi et al. [4] suggests that the Mixmaster Universe model possesses movable transcendental singularities and thus is nonintegrable in the sense that it does not satisfy the Painlevé property (i.e., singularities with nonalgebraic branching). In this paper, we present numerical evidence of the nonintegrability of the Mixmaster model by studying the singularity patterns in the complext-plane, wheret is the “physical” time, as well as in the complex τ-plane, where τ is the associated “logarithmic” time. More specifically, we show that in the τ-plane there appears to exist a “natural boundary” of remarkably intricate structure. This boundary lies at the ends of a sequence of smaller and smaller “chimneys” and consists of the type of singularities studied in [4], on which pole-like singularities accumulate densely. We also show numerically that in the complext-plane there appear to exist complicated, dense singularity patterns and infinitely-sheeted solutions with sensitive dependence on initial conditions.     

Junctions of singularly degenerating domains with different limit dimensions 1

The asymptotic series for solutions of the mixed boundary-value problem for the Poisson equation in a domain, which is a junction of singularly degenerating domains, are constructed. In this paper, which is the first part of the publication, the three-dimensional problem (“wheel hub with spokes”) and the analogous two-dimensional problems are considered. The methods of matched and compound asymptotic expansions are used. It is shown that a special self-adjoint extension of the operator of the limit problem in the “hub” supplied by the straight-line segments (“limits of spokes”) can be chosen as an asymptotical model of the problem in question; the extension parameters are to be some integral characteristics of the boundary-layer problems. Bibliography: 39 titles. Translated from Trudy Seminara imeni I. G. Petrovskogo. No. 18, pp. 3–78, 1995.     

Tail index estimation for heavy tails: accommodation of bias in the excesses over a high threshold

In statistics of extremes, inference is often based on the excesses over a high random threshold. Those excesses are approximately distributed as the set of order statistics associated to a sample from a generalized Pareto model. We then get the so-called “maximum likelihood” estimators of the tail index γ. In this paper, we are interested in the derivation of the asymptotic distributional properties of a similar “maximum likelihood” estimator of a positive tail index γ, based also on the excesses over a high random threshold, but with a trial of accommodation of bias in the Pareto model underlying those excesses. We next proceed to an asymptotic comparison of the two estimators at their optimal levels. An illustration of the finite sample behaviour of the estimators is provided through a small-scale Monte Carlo simulation study. Research partially supported by FCT/POCTI and POCI/FEDER.     

Pricing in an equilibrium based model for a large investor

We study a financial model with a non-trivial price impact effect. In this model we consider the interaction of a large investor trading in an illiquid security, and a market maker who is quoting prices for this security. We assume that the market maker quotes the prices such that by taking the other side of the investor’s demand, the market maker will arrive at maturity with the maximal expected utility of the terminal wealth. Within this model we provide an explicit recursive pricing formula for an exponential utility function, as well as an asymptotic expansion for the price for a “small” simple demand.     

Superlinear convergence of the control reduced interior point method for PDE constrained optimization

A thorough convergence analysis of the Control Reduced Interior Point Method in function space is performed. This recently proposed method is a primal interior point pathfollowing scheme with the special feature that the control variable is eliminated from the optimality system. Apart from global linear convergence we show that this method converges locally superlinearly, if the optimal solution satisfies a certain non-degeneracy condition. In numerical experiments we observe that a prototype implementation of our method behaves as predicted by our theoretical results. Supported by the DFG Research Center Matheon “Mathematics for key technologies”.     

Structural stability and robustness to bounded rationality for non-compact cases

We study the model M consisting of “general games” with noncompact action space, together with an associated abstract rationality function. We prove that M is structurally stable and robust to ϵ-equilibria for “almost all” parameters. As applications, we investigate structural stability and robustness to bounded rationality for noncooperative games, multiobjective optimizations and fixed point problems satisfying existence and some continuity conditions. Specifically, we introduce concrete rationality functions for such three kinds of problems with both payoffs and strategy sets, objective functions and domain spaces, and correspondence and domain spaces as parameters, respectively, and show the generic structural stability and robustness to bounded rationality for the corresponding model Ms.     

Iterative computation of negative curvature directions in large scale optimization

In this paper we deal with the iterative computation of negative curvature directions of an objective function, within large scale optimization frameworks. In particular, suitable directions of negative curvature of the objective function represent an essential tool, to guarantee convergence to second order critical points. However, an “adequate” negative curvature direction is often required to have a good resemblance to an eigenvector corresponding to the smallest eigenvalue of the Hessian matrix. Thus, its computation may be a very difficult task on large scale problems. Several strategies proposed in literature compute such a direction relying on matrix factorizations, so that they may be inefficient or even impracticable in a large scale setting. On the other hand, the iterative methods proposed either need to store a large matrix, or they need to rerun the recurrence. On this guideline, in this paper we propose the use of an iterative method, based on a planar Conjugate Gradient scheme. Under mild assumptions, we provide theory for using the latter method to compute adequate negative curvature directions, within optimization frameworks. In our proposal any matrix storage is avoided, along with any additional rerun.     

Regular Score Tests of Independence in Multivariate Extreme Values

The score tests of independence in multivariate extreme values derived by Tawn (Tawn, J.A., “Bivariate extreme value theory: models and estimation,” Biometrika 75, 397–415, 1988) and Ledford and Tawn (Ledford, A.W. and Tawn, J.A., “Statistics for near independence in multivariate extreme values,” Biometrika 83, 169–187, 1996) have non-regular properties that arise due to violations of the usual regularity conditions of maximum likelihood. Two distinct types of regularity violation are encountered in each of their likelihood frameworks: independence within the underlying model corresponding to a boundary point of the parameter space and the score function having an infinite second moment. For applications, the second form of regularity violation has the more important consequences, as it results in score statistics with non-standard normalisation and poor rates of convergence. The corresponding tests are difficult to use in practical situations because their asymptotic properties are unrepresentative of their behaviour for the sample sizes typical of applications, and extensive simulations may be needed in order to evaluate adequately their null distribution. Overcoming this difficulty is the primary focus of this paper. We propose a modification to the likelihood based approaches used by Tawn (Tawn, J.A., “Bivariate extreme value theory: models and estimation,” Biometrika 75, 397–415, 1988) and Ledford and Tawn (Ledford, A.W. and Tawn, J.A., “Statistics for near independence in multivariate extreme values,” Biometrika 83, 169–187, 1996) that provides asymptotically normal score tests of independence with regular normalisation and rapid convergence. The resulting tests are straightforward to implement and are beneficial in practical situations with realistic amounts of data. AMS 2000 Subject Classification Primary—60G70 Secondary—62H15     

Outdoor WLAN planning via non-monotone derivative-free optimization: algorithm adaptation and case study

In this paper, we study the application of non-monotone derivative-free optimization algorithms to wireless local area networks (WLAN) planning, which can be modeled as an unconstrained minimization problem. We wish to determine the access point (AP) positions that maximize coverage in order to provide connectivity to static and mobile users. As the objective function of the optimization model is not everywhere differentiable, previous research has discarded gradient methods and employed heuristics such as neighborhood search (NS) and simulated annealing (SA). In this paper, we show that the model fulfills the conditions required by recently proposed non-monotone derivative-free (DF) algorithms. Unlike SA, DF has guaranteed convergence. The numerical tests reveal that a tailored DF implementation (termed “zone search”) outperforms NS and SA. A collaboration between U. of Vigo, Spain and USB, Venezuela.     

Weakly Gibbsian representations for joint measures of quenched lattice spin models

Can the joint measures of quenched disordered lattice spin models (with finite range) on the product of spin-space and disorder-space be represented as (suitably generalized) Gibbs measures of an “annealed system”? - We prove that there is always a potential (depending on both spin and disorder variables) that converges absolutely on a set of full measure w.r.t. the joint measure (“weak Gibbsianness”). This “positive” result is surprising when contrasted with the results of a previous paper [K6], where we investigated the measure of the set of discontinuity points of the conditional expectations (investigation of “a.s. Gibbsianness”). In particular we gave natural “negative” examples where this set is even of measure one (including the random field Ising model). Further we discuss conditions giving the convergence of vacuum potentials and conditions for the decay of the joint potential in terms of the decay of the disorder average over certain quenched correlations. We apply them to various examples. From this one typically expects the existence of a potential that decays superpolynomially outside a set of measure zero. Our proof uses a martingale argument that allows to cut (an infinite-volume analogue of) the quenched free energy into local pieces, along with generalizations of Kozlov's constructions. Received: 11 November 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000 RID="*" ID="*" Work supported by the DFG Schwerpunkt `Wechselwirkende stochastische Systeme hoher Komplexit?t'