Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

A Class of Iterative Algorithms and Solvability of Nonlinear Variational Inequalities Involving Multivalued Mappings

The solvability of the following class of nonlinear variational inequality (NVI) problems based on a class of iterative procedures, which possess an equivalence to a class of projection formulas, is presented.Determine an element x ^* K and u ^* T(x ^*) such that u ^*, x – x ^* 0 for all x K where T: K P(H) is a multivalued mapping from a real Hilbert space H into P(H), the power set of H, and K is a nonempty closed convex subset of H. The iterative procedure adopted here is represented by a nonlinear variational inequality: for arbitrarily chosen initial points x ⁰, y ⁰ K, u ⁰ T(y ⁰) and v ⁰ T(x ⁰), we have u ^k + x ^k+1 – y ^k , x – x ^k+1 0, x K, for u ^k T(y ^k ) and for k 0where v ^k + y ^k – x ^k , x – y ^k 0, x K and for v ^k T(x ^k ).     

Fast Summation of Power Series with Coefficients Analytic at Infinity

We propose a fast summation algorithm for slowly convergent power series of the form _{j=j 0} z ^j _j j _i=1 ^s (j+ _i )^– _i , where R, _i 0 and _i C, 1is, are known parameters, and _j =(j), being a given real or complex function, analytic at infinity. Such series embody many cases treated by specific methods in the recent literature on acceleration. Our approach rests on explicit asymptotic summation, started from the efficient numerical computation of the Laurent coefficients of . The effectiveness of the resulting method, termed ASM (Asymptotic Summation Method), is shown by several numerical tests.     

Method of moments on semigroups

If ( _j ) is a sequence of measures onR ^k having momentss _n ( _j ) of all ordersnN ₀ ^k and if for eachnN ₀ ^k the sequence (s _{n j} )) _jN converges to somet _n R then some subsequence of ( _j ) converges weakly to a measure with moments of all orders satisfyings _n ()=t _n for allnN^0/k . Thisindeterminate method of moments and the continuity theorems in probability theory suggest a common generalization, dealing with a commutative semigroupS, with involution and a neutral element, and measures on the dual semigroupS ^* ofcharacters on S—hermitian multiplicative complex functions not identically zero. In this setting, a continuity theorem holds for measures on the set of bounded characters,⁽²⁾ and an indeterminate method of moments whenS is finitely generated.⁽²⁾ The latter result is generalized in the present paper to the case of arbitraryS. This leads to a generalization of Haviland's criterion for theK-moment problem, and to a continuity theorem for the so-called perfect semigroups.     

Quadratically constrained quadratic programming: Some applications and a method for solution

The problem (QPQR) considered here is: minimizeQ ₁ (x) subject toQ _i (x) 0,i M ₁ {2,...,m},x P R ⁿ, whereQ _i (x), i M {1} M ₁ are quadratic forms with positive semi-definite matrices, andP a compact nonempty polyhedron of Rⁿ. Applications of (QPQR) and a new method to solve it are presented.Letu S={u R ^m;u 0, u _i= l}be fixed;then the problem:iM minimize u _iQ_i (x (u)) overP, always has an optimal solutionx (u), which is either feasible, iM i.e. u C₁ {u S;Q _i (x (u)) 0,i M ₁} or unfeasible, i.e. there exists ani M ₁ withu C {u S; Q_i(x(u)) 0}.Let us defineC _i C_i S _i withS _i {u S; u _i=0}, i M. A constructive method is used to prove that C _i is not empty and thatx (û) withiM û C _i characterizes an optimal solution to (QPQR). Quite attractive numerical results have been reached with this method.

---

Zusammenfassung Die vorliegende Arbeit befaßt sich mit Anwendungen und einer neuen Lösungsmethode der folgenden Aufgabe (QPQR): man minimiere eine konvexe quadratische ZielfunktionQ _i (x) unter Berücksichtigung konvexer quadratischer RestriktionenQ _i (x) 0, iM ₁ {2,...,m}, und/oder linearer Restriktionen.·Für ein festesu S {u R ^m;u 0, u _i=1},M {1} M₁ besitzt das Problem:iM minimiere die konvexe quadratische Zielfunktion u _i Q_i (x (u)) über dem durch die lineareniM Restriktionen von (QPQR) erzeugten, kompakten und nicht leeren PolyederP R ⁿ, immer eine Optimallösungx (u), die entweder zulässig ist: u C₁ {u S;Q ₁ (x (u)) 0,i M ₁} oder unzulässig ist, d.h. es existiert eini M ₁ mitu C_i {u S;Q _i (x(u))0}.Es seien folgende MengenC _i C_i S _i definiert, mitS _i {u S;u _i=0}, i M. Es wird konstruktiv bewiesen, daß C _i 0 undx (û) mitû C _i eine Optimallösung voniM iM (QPQR) ist; damit ergibt sich eine Methode zur Lösung von (QPQR), die sich als sehr effizient erwiesen hat. Ein einfaches Beispiel ist angegeben, mit dem alle Schritte des Algorithmus und dessen Arbeitsweise graphisch dargestellt werden können.

---

---

An earlier version of this paper was written during the author's stay at the Institute for Operations Research, Swiss Federal Institute of Technology, Zürich.     

On solvability of linear difference equations in smooth and real analytic vector functions of several variables

We investigate the multidimensional equations _j=1 ^q A_j(x)y(x+e _j )=f(x),e _j ⁿ wherex ⁿ andA _j : ⁿ Hom( ^p , ^m ),f : ^{n m} are given maps. Sufficient conditions for smooth and analytic solvability for anyf C ^k ,k are found.Research partially supported by the Israel Ministry of ScienceAMS classification 39B Functional equations     

Invariant measures ofC 2-diffeomorphisms of Markov type inR d

A class of uniformly expanding, piecewiseC ²-diffeomorphisms from domainsIR ^d (bounded or not) into themselves is considered. It is shown that the number of the extreme points of Fix (P )={gG:Pg=g} whereP is the Frobenius-Perron operator associated with andG={gL ¹: g0 g=1}, can be determined in an effective way. Moreover, it is shown that the sequence {P ^j g} is convergent inL ¹ for anygG, and in the topology of uniform convergence for anygG(1). The limit is a linear projectionR inL ¹ (defined by (3.1)) which mapsG onto Fix (P ) (see Th. 3.1).Dedicated to professor A. Lasota on the occasion of his 60th birthday     

On a Property of Subexponential Distributions

Let F be a distribution function (d.f.) on [0, ) with finite first moment m >0. We define the integrated tail distribution function F ₁ of F by F ₁(t)=m^-1 ₀ ^t (1- F(u))du, t0. In this paper, we obtain sufficient conditions under which implications FSF ₁S and F ₁S FS hold, where S is the class of subexponential distributions.     

Efficiency of Proximal Bundle Methods

We give efficiency estimates for proximal bundle methods for finding f_*min_Xf, where f and X are convex. We show that, for any accuracy <0, these methods find a point x^kX such that f(x^k)–f^* after at most k=O(1/³) objective and subgradient evaluations.     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.     

Ergodic properties of Poisson processes with almost periodic intensity

Summary We discuss in this paper a non-homogeneous Poisson process A driven by an almost periodic intensity function. We give the stationary version A ^* and the Palm version A ⁰ corresponding to A ^*. Let (T _i ,i) be the inter-point distance sequence in A and (T _i ⁰ ,i) in A ⁰. We prove that forj, the sequence (T _i+j,i) converges in distribution to (T _i ⁰ ,i). If the intensity function is periodic then the convergence is in variation.     

Fine Analysis of the Quasi-Orderings on the Power Set

We pursue the fine analysis of the quasi-orderings and on the power set of a quasi-ordering (Q,). We set X Y if every xX is majorized in by some yY, and X Y if every yY is minorized in by some xX. We show that both these quasi-orderings are -wqo if and only if the original quasi-ordering is ( )-wqo. For this holds also restricted to finite subsets, thus providing an example of a finitary operation on quasi-orderings which does not preserve wqo but preserves bqo.     

Asymptotic behaviour of Gaussian random fields

Summary Let X={X(t), t ^N} be a centred Gaussian random field with covariance X(t)X(s)=r(t–s) continuous on ^N×^N and r(0)=1. Let (t,s)=((X(t)–X(s)) ²)^1/2; (t,s) is a pseudometric on ^N. Assume X is -separable. Let D ₁ be the unit cube in ^N and for 0<k, D _k= {x^N: k ^–1 xD₁}, Z(k)=sup{X(t),tD _k}. If X is sample continuous and ¦r(t)¦ =o(1/log¦t¦) as ¦t¦8 then Z(k)-(2Nlogk) ^1/20 as k a.s.     

Joint convergence of conditional expectations

Let P_n, nIN{0}, be probability measures on a-fieldA; f_n, nIN{0}, be a family of uniformly boundedA-measurable functions andA _n, nIN, be a sequence of sub--fields ofA, increasing or decreasing to the-fieldA _o. It is shown in this paper that the conditional expectations converge in P_o-measure to with k, n, m , if P_n|A, nIN, converges uniformly to P_n|A and f_n, nIN, converges in P_o-measure to f_o.     

The distortion of Hilbert space

The unit sphere of Hilbert space, ₂, is shown to contain a remarkable sequence of nearly orthogonal sets. Precisely, there exist a sequence of sets of norm one elements of ₂, (C _i ) _i=1 , and reals _i 0 so that a) each setC _i has nonempty intersection with every infinite dimensional closed subspace of ₂ and b) forij,xC, andyC _j , |x, y|<_{min(i, j)} E. Odell was partially supported by NSF and TARP. Th. Schlumprecht was partially supported by NSF and LEQSF.     

Transversally bounded lattices

A problem stemming from a boundedness question for torsion modules and its translation into ideal lattices is explored in the setting of abstract lattices. Call a complete lattice L transversally bounded (resp., uniformly transversally bounded) if for all families (X _i)_iIof nonempty subsets of L with the property that {x _iiI}<1 for all choices of x _iX _i, almost all of the sets X _ihave join smaller than 1 (resp., _jJ X _jhas join smaller than 1 for some cofinite subset J of I). It is shown that the lattices which are transversally bounded, but not uniformly so, correspond to certain ultrafilters with peculiar boundedness properties similar to those studied by Ramsey. The prototypical candidates of the two types of lattices which one is led to construct from ultrafilters (in particular the lattices arising from what will be called Ramsey systems) appear to be of interest beyond the questions at stake.     

Mixing and some integro-functional equations

Summary It is proved that the operatorP: L ¹ (0, ) L ¹(0, ), given byPg(z) = _z/c [g(x)/cx]dx, is completely mixing, i.e.,P ⁿ g ₁ 0 forg L ¹(0, ) with g dx = 0. This implies that, forc (0, 1), each continuous and bounded solution of the equationf(x)= ₀ ^cx f(t)dt/(cx) (x (0, 1]) is constant.     

On the complete solution of ∈y″=y 3

In Ref. 1, the author claimed that the problem y=y ³ is soluble only for a certain range of the parameter . An analytic approach, as adopted in the following contribution, reveals that a unique solution exists for any positive value of . The solution is given in closed form by means of Jacobian elliptic functions, which can be numerically computed very efficiently. In the limit 0+, the solutions exhibit boundary-layer behavior at both endpoints. An easily interpretable approximate solution for small is obtained using a three-variable approach.     

On unconditional bases in certain Banach function spaces

Let X be a Banach space, L ([0,1])XL ¹([0,1]), with an unconditional basis. By the well-known stability property in X, there exists a unconditional basis {f _n} _m=1 , where f _n in C([0,1]), nN. In this paper, we introduce the notion that X ^*has the singularity property of X ^*at a point t ₀[0,1]. It is proved that if X ^*has the singularity property at a point t ₀ [0,1], then there exists no orthonormal, fundamental system in C([0,1]) which forms an unconditional basis in X.     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.