A class of nonlinear complementarity problems for multifunctions

Given a continuous mapF:R ⁿ R ⁿ and a lower semicontinuous positively homogeneous convex functionh:R ⁿ R, the nonlinear complementarity problem considered here is to findxR ₊ ⁿ andyh(x), the subdifferential ofh atx, such thatF(x)+y0 andx ^T (F(x)+y)=0. Some existence theorems for the above problem are given under certain conditions on the mapF. An application to quasidifferentiable convex programming is also shown.The authors are grateful to Professor O. L. Mangasarian and the referee for their substantive suggestions.     

Generalized pseudoinverses of matrix valued functions

We define the pseudoinverse (resp. a generalized pseudoinverse) of a matrix-valued functionF to be the functionF ^x such that, for each in the domain ofF, F ^x () is the inverse (resp. a generalized inverse) of the matrixF(). We derive a state space formula for a generalized pseudoinverse of a rational matrix function without a pole or zero at infinity. This derivation makes use of the theorem characterizing the factorization of a nonregular rational matrix functionW in terms of the decomposition of the state space of a realization ofW. We also give a formula for a generalized pseudoinverse of an arbitrary rational matrix function in the form of a centered realization. We indicate some applications of generalized pseudoinverses of matrix valued functions.     

Iterative hyperidentities for theA n,m varieties of semigroups

Iterative hyperidentities are hyperidentities of the special formF ^a (x ₁,...,x _k =F ^a+b (x ₁,...,x _k ). This type of hyperidentity has been considered by Denecke and Pöschel, and by Schweigert. Here we consider iterative hyperidentities for the variety A_n,m of commutative semigroups satisfyingx ⁿ =x ^n+m ,n,m 1. We introduce two parameters(m, n) and(m) associated withn andm, and show thatA _nn,m satisfies the iterative hyperidentitiesF (x ₁,...,x _k =F ^+b (x ₁,...,x _k ) for every arityk. Moreover, the numbers and are minimal, making these hyperidentities irreducible in the sense of Schweigert. We also show how these hyperidentities for A_n,m may be used to prove that no non-trivial proper variety of commutative semigroups can have a finite hyperidentity basis.Presented by W. Taylor.Research supported by NSERC of Canada     

An implicit function theorem

Suppose thatF:DR ⁿ×R^mRⁿ, withF(x ⁰,y ⁰)=0. The classical implicit function theorem requires thatF is differentiable with respect tox and moreover that ₁ F(x ⁰,y ⁰) is nonsingular. We strengthen this theorem by removing the nonsingularity and differentiability requirements and by replacing them with a one-to-one condition onF as a function ofx.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

Convergence of the steepest descent method for minimizing quasiconvex functions

To minimize a continuously differentiable quasiconvex functionf: ⁿ , Armijo's steepest descent method generates a sequencex ^k+1 =x ^k –t _k f(x ^k ), wheret _k >0. We establish strong convergence properties of this classic method: either , s.t. ; or arg minf = , x ^k andf(x ^k ) inff. We also discuss extensions to other line searches.The research of the first author was supported by the Polish Academy of Sciences. The second author acknowledges the support of the Department of Industrial Engineering, Hong Kong University of Science and Technology.We wish to thank two anonymous referees for their valuable comments. In particular, one referee has suggested the use of quasiconvexity instead of convexity off.     

On the convergence of projected gradient processes to singular critical points

The projected gradient methods treated here generate iterates by the rulex _k+1=P (x _k –s _k F(x _k )),x ₁ , where is a closed convex set in a real Hilbert spaceX,s _k is a positive real number determined by a Goldstein-Bertsekas condition,P projectsX into ,F is a differentiable function whose minimum is sought in , and F is locally Lipschitz continuous. Asymptotic stability and convergence rate theorems are proved for singular local minimizers in the interior of , or more generally, in some open facet in . The stability theorem requires that: (i) is a proper local minimizer andF grows uniformly in near ; (ii) –F() lies in the relative interior of the coneK of outer normals to at ; and (iii) is an isolated critical point and the defect P (x – F(x)) –x grows uniformly within the facet containing . The convergence rate theorem imposes (i) and (ii), and also requires that: (iv)F isC ⁴ near and grows no slower than x–⁴ within the facet; and (v) the projected Hessian operatorP _{F 2} F()F is positive definite on its range in the subspaceF orthogonal toK . Under these conditions, {x _k } converges to from nearby starting pointsx ₁, withF(x _k ) –F() =O(k ^–2) and x _k – =O(k ^–1/2). No explicit or implied local pseudoconvexity or level set compactness demands are imposed onF in this analysis. Furthermore, condition (v) and the uniform growth stipulations in (i) and (iii) are redundant in ⁿ .     

Approximation to the expectation of a function of order statistics and its applications

ThisprojectissupportedbytheNationalNaturalScienceFoundationofChinaandDoctoralProgramFoundationofHigherEducation.1.IntroductionLetUI,U2,'bei.i.d.randomvariableswithuniformd.f.ontheinterval(0,l),andforeveryn31,writeUt,,15'5Un,.fortheorderstatisticsofUI,'tUn.SupposethatXI1X2,'arei.i.d.observationsfromanondegenerated.f.F,anddenotebyX.,l5'5X.,.theorderstatisticsofXI,'IX,,'Withoutlossofgenerality,wewillassume0相似文献   

Convex interpolating splines of arbitrary degree II

For given data {(x _i ,y _i )} _i=0 ⁿ , (x ₀<x ₁<...<x _n ) we consider the possibility of finding a spline functions of arbitrary degreek+1 (k 1) with preassigned smoothnessl, where 1 l [(k+1)/2]. The splines should be such thats(x _i )=y _i ,i=0, 1,...,n ands is increasing and convex on [x ₀,x _n ]. Sufficient conditions which guarantee the existence ofs and an explicit formula for this function are derived.     

Characterizations of the Poisson process as a renewal process via two conditional moments

Given two independent positive random variables, under some minor conditions, it is known that fromE(X^rX+Y)=a(X+Y)^r andE(X^sX+Y)=b(X+Y)^s, for certain pairs ofr ands, wherea andb are two constants, we can characterizeX andY to have gamma distributions. Inspired by this, in this article we will characterize the Poisson process among the class of renewal processes via two conditional moments. More precisely, let {A(t), t0} be a renewal process, with {S _k, k1} the sequence of arrival times, andF the common distribution function of the inter-arrival times. We prove that for some fixedn andk, kn, ifE(S _k ^r A(t)=n)=at^r andE(S _k ^s A(t)=n)=bt^s, for certain pairs ofr ands, wherea andb are independent oft, then {A(t), t0} has to be a Poisson process. We also give some corresponding results about characterizingFto be geometric whenF is discrete.Support for this research was provided in part by the National Science Council of the Republic of China, Grant No. NSC 81-0208-M110-06.     

Gewichtete Volumsmittelwerte von Simplices,welche zufällig in einem konvexen Körper des ℝ gewählt werden

For any set ofn+1 pointsx ₁, ...,x _n+1F we denote byv(C(x ₁,...,x _n+1)) then-dimensional oriented volume of the convex hullC(x ₁,...,x _n+1) of these points. With a fixed symmetric functionf: >> strictly monotone increasing on the nonnegative real line, we consider the real functional RODEL on the set of all convex bodiesK of ⁿ with absolute volume |v(K)|=1 and assert, that it takes its minimal value on the ellipsoids with absolute volume 1.     

Approximation of the viability kernel

We study recursive inclusionsx ⁿ⁺¹ G(x ⁿ ). For instance, such systems appear for discrete finite-difference inclusionsx ⁿ⁺¹ G (x ⁿ) whereG :=1+F. The discrete viability kernel ofG , i.e., the largest discrete viability domain, can be an internal approximation of the viability kernel ofK underF. We study discrete and finite dynamical systems. In the Lipschitz case we get a generalization to differential inclusions of the Euler and Runge-Kutta methods. We prove first that the viability kernel ofK underF can be approached by a sequence of discrete viability kernels associated withx ⁿ⁺¹ (xⁿ) where (x) =x + F(x) + (ML/2) ². Secondly, we show that it can be approached by finite viability kernels associated withx _h ⁿ⁺¹ ( (x _h ⁿ⁺¹ ) +(h) X _h .     

The empirical process of a short-range dependent stationary sequence under Gaussian subordination

Summary Consider the stationary sequenceX ₁=G(Z ₁),X ₂=G(Z ₂),..., whereG(·) is an arbitrary Borel function andZ ₁,Z ₂,... is a mean-zero stationary Gaussian sequence with covariance functionr(k)=E(Z ₁ Z _k+1) satisfyingr(0)=1 and _k=1 |r(k)| ^m < , where, withI{·} denoting the indicator function andF(·) the continuous marginal distribution function of the sequence {X _n }, the integerm is the Hermite rank of the family {I{G(·) x} –F(x):xR}. LetF _n (·) be the empirical distribution function ofX ₁,...,X _n . We prove that, asn, the empirical processn ^1/2{F _n (·)-F(·)} converges in distribution to a Gaussian process in the spaceD[–,].Partially supported by NSF Grant DMS-9208067     

Extended Classical Asymptotic Expansions in the Case of Gaussian Limit Distribution

Let X, X ₁, X ₂,... be a sequence of independent and identically distributed random variables with common distribution function F. Denote by F _n the distribution function of centered and normed sum S _n . Let F belong to the domain of attraction of the standard normal law , that is, lim F _n (x)= (x), as n , uniformly in x . We obtain extended asymptotic expansions for the particular case where the distribution function F has the density p(x) = cx ^––1 ln(x), x > r, where 2, , c > 0, and r > 1. We write the classical asymptotic expansion (in powers of n ^–1/2) and then add new terms of orders n ^–/2 ln n, n ^–/2 ln^-1 n, etc., where 0.     

Minimal Morse functions on a pair of manifolds

The existence theorem for a minimal Morse function on a pair of manifolds (M ⁿ,N ^k), wheren-k 3,k 6, is proved.Translated from Ukrainskii Matematiccheskii Zhurnal, Vol. 45, No. 1, pp. 143–144, January, 1993.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

A remark on generalized iterates

Letf be an invertible function on the real lineR, and letZ denote the set of integers. For eachx Z, letf ^|n| denote then'th iterate off. Clearlyf ^|m|(f ^|n|(x))=f ^|m+n|(x) for allm,nZ and allxR. LetG be any group of orderc, the cardinality of the continuum, which contains (an isomorphic copy of)Z as a normal subgroup. If for eachxR, the iteration trajectory (orbit) ofx is non-periodic, then there exists a set of invertible functionsF={F ^||:G} on the real line with the properties (i)F ^||(F ^||(x))=F ^|+| (x) for allxR and (ii)F ^|n|(x)=f ^|n|(x) for allnZ andxR. That is,f can be embedded in a set ofG-generalized iterates. In particular,f can be embedded in a set of complex generalized iterates.Dedicated to Professor Janos Aczél on his 60th birthday     

How large delays build up in a GI/G/1 queue

LetW _k denote the waiting time of customerk, k 0, in an initially empty GI/G/1 queue. Fixa> 0. We prove weak limit theorems describing the behaviour ofW _k /n, 0kn, given W_n >na. LetX have the distribution of the difference between the service and interarrival distributions. We consider queues for which Cramer type conditions hold forX, and queues for whichX has regularly varying positive tail.The results can also be interpreted as conditional limit theorems, conditional on large maxima in the partial sums of random walks with negative drift.Research supported by the NSF under Grant NCR 8710840 and under the PYI Award NCR 8857731.     

Sur les équations fonctionnelles auxq-différences

Summary In this paper, we study the convergence of formal power series solutions of functional equations of the formP _k(x)(^[k](x))=(x), where ^[k] (x) denotes thek-th iterate of the function.We obtain results similar to the results of Malgrange and Ramis for formal solutions of differential equations: if(0) = 0, and(0) =q is a nonzero complex number with absolute value less than one then, if(x)=a(n)x ⁿ is a divergent solution, there exists a positive real numbers such that the power seriesa(n)q ^sn(n+1)2 x ⁿ has a finite and nonzero radius of convergence.

     

Formule d'Itô pour des Diffusions Uniformément Elliptiques,et Processus de Dirichlet

Soit X une diffusion uniformément elliptique sur R ^d ,F une fonction dans H _loc ¹(R ^d ) et la loi initiale de la diffusion. On montre que si l'intégrale |F|²(x)U(x)dx est finie, oùU désigne le potentiel de la mesure , alors F(X) est un processus de Dirichlet. Si de plus, F appartient àH ² _loc(R ^d ) et si les intégrales |F|²(x)U(x)dx et |f _k |²(x)U(x)dx sont finies, pour les dérivées faibles f _k de F, alors on peut écrire une formule d'Itô. En particulier, on définit l'intégrale progressive F(X)dX et on prouve l'existence des covariations quadratiques [f _k (X),X ^k ].