Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison

We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P: find a globally-optimal value off and a corresponding point; Problem Q: find a set of disjoint subintervals of [a, b] containing only points with a globally-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P. In phase I, this algorithm obtains rapidly a solution which is often globally-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.     

Sufficiency-Type Stability and Stabilization Criteria for Linear Time-Invariant Systems with Constant Point Delays

A set of criteria of asymptotic stability for linear and time-invariant systems with constant point delays are derived. The criteria are concerned with -stability local in the delays and -stability independent of the delays, namely, stability with all the characteristic roots in Res–<0 for all delays in some defined real intervals including zero and stability with characteristic roots in Res<–<0 as 0⁺ for all possible values of the delays, respectively. The results are classified in several groups according to the technique dealt with. The used techniques include both Lyapunov's matrix inequalities and equalities and Gerschgorin's circle theorem. The Lyapunov's inequalities are guaranteed if a set of matrices, built from the matrices of undelayed and delayed dynamics, are stability matrices. Some extensions to robust stability of the above results are also discussed.     

On Bahadur asymptotic efficiency in a semiparametric regression model

ＯＮＢＡＨＡＤＵＲＡＳＹＭＰＴＯＴＩＣＥＦＦＩＣＩＥＮＣＹＩＮＡＳＥＭＩＰＡＲＡＭＥＴＲＩＣＲＥＧＲＥＳＳＩＯＮＭＯＤＥＬＬＩＡＮＧＨＵＡ（梁华）;ＣＨＥＮＧＰＩＮＧ（成平）（ＩｎｓｔｉｔｕｔｅｏｆＳｙｓｔｅｍｓＳｃｉｅｎｃｅ,ｔｈｅＣｈｉｎｅｓｅＡ...     

On the complex zeros of solutions of linear differential equations

Summary A classical result (see R.Nevanlinna, Acta Math.,58 (1932), p. 345) states that for a second-order linear differential equation, w + P(z) w + Q(z) w=0, where P(z) and Q(z) are polynomials, there exist finitely many rays, arg z=_j, for j=1,..., m, such that for any solution w=f(z) 0 and any > 0, all but finitely many zeros off lie in the union of the sectors ¦ arg z - _j¦ < for j=1,..., m. In this paper, we give a complete answer to the question of determining when the same result holds for equations of arbitrary order having polynomial coefficients. We prove that for any such equation, one of the following two properties must hold: (a) for any ray, arg z=, and any > 0, there is a solution f 0 of the equation having infinitely many zeros in the sector ¦arg z - ¦ <, or (b) there exist finitely many rays, arg z=_j, for j= 1,..., m, such that for any >0, all but finitely many zeros of any solution f 0 must lie in the union of the sectors ¦ arg z - _j¦ < for j=1, ..., m. In addition, our method of proof provides an effective procedure for determining which of the two possibilities holds for a given equation, and in the case when (b) holds, our method will produce the rays, arg z=_j. We emphasize that our result applies to all equations having polynomial coefficients, without exception. In addition, we mention that if the coefficients are only assumed to be rational functions, our results will still give precise information on the possible location of the bulk of the zeros of any solution.This research was supported in part by the National Science Foundation (DMS-84-20561 and DMS-87-21813).     

Boundary-layer averaging for standard systems with lag

Thekth-order asymptotic solution of a standard system with lag is constructed along trajectories calculated according to the averaging scheme of A. N. Filatov. If the perturbation parameter 1, then the use of the step method for finding the solution is connected with cumbersome calculations because the number of required steps is inversely proportional to . We suggest another approach in which the step method is used onlyk times fort [0,k] and justify the asymptotic method.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 10 pp. 1362–1368, October, 1994.     

Black holes on the plane drawn by a Wiener process

Summary We say that the discD()R ², of radius , located around the origin isp-covered in timeT by a Wiener processW(·) if for anyzD() there exists a 0tT such thatW(t) is a point of the disc of radiusp, located aroundz. The supremum of those 's (0) is studied for which,D() isp-covered inT.     

On the complexity of approximating a KKT point of quadratic programming

We present a potential reduction algorithm to approximate a Karush—Kuhn—Tucker (KKT) point of general quadratic programming (QP). We show that the algorithm is a fully polynomial-time approximation scheme, and its running-time dependency on accuracy (0, 1) is O((l/) log(l/) log(log(l/))), compared to the previously best-known result O((l/)²). Furthermore, the limit of the KKT point satisfies the second-order necessary optimality condition of being a local minimizer. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research support in part by NSF grants DDM-9207347 and DMI-9522507, and the Iowa Business School Summer Grant.     

Asymptotic limit law for the close approach of two trajectories in expanding maps of the circle

Summary Given two pointsx, yS ¹ randomly chosen independently by a mixing absolutely continuous invariant measure of a piecewise expanding and smooth mapf of the circle, we consider for each >0 the point process obtained by recording the timesn>0 such that |f ⁿ (x)–f ⁿ (y)|. With the further assumption that the density of is bounded away from zero, we show that when tends to zero the above point process scaled by –1 converges in law to a marked Poisson point process with constant parameter measure. This parameter measure is given explicity by an average on the rate of expansion off.Partially supported by FAPESP grant number 90/3918-5     

On the sums of a family of Kapteyn series

The series ₁ n ^r–1 J _n (n)J _n (n) (r 0, 0 < 1) arise in studying the emission and absorption of radiation by a charged particle on a Kepler orbit. For the first few even,r, the sums are obtained in closed form, and for oddr they are given in terms of a certain definite integral. The integral is expressed as a power series in for ||<1, and, near =1, an asymptotic expansion in powers of (1–²)^1/2 may be obtained.

---

Résumé La série ₁ n ^r–1 J _n (n)J _n (n) (r 0, 0 < 1) se trouve par l'émission et l'absorption du rayonnement d'une particule chargée sur l'orbite Keplerien. Pour les plus petites valuers paires der, les sommes s'obtienment en forme compacte, et pour les valuers impaires, elles se déterminent d'après une intégrale definie. Pour ||<1, cette intégrale se développe dans une série de puissances de , et dans le voisinage de =1, on obtient une série asymptotique et puissances de (1–²)^1/2.

     

Convexity theories III. Classification of certain real convexity theories

In this paper we classify all real convexity theories that contain the standard convexity theory _c. For this purpose we consider three subcases: finitary; infinitary and (_sc\_c)Ø; infinitary and _sc=_c. In each of these subcases one encounters a phenomenon resembling bifurcation.This research was supported by the Deutsche Forschungsgemeinschaft.     

A Nonparametric Estimation Problem From Indirect Observations

This paper deals with a nonparametric estimation problem of an integral-type functional from indirect observations where the observation Y (t) is a sum of a known function of an unobservable process X (t) and a Gaussian white noise, and X (t) is a sum of an unknown function a(t) and a Gaussian process. The minimax lower bound on the quality of nonparametric estimation is derived and an asymptotically efficient estimator is proposed. The paper concludes with some examples including one about reduction to parameter estimation.     

Almost Fredholm operators in von Neumann algebras

LetA be a von Neumann algebra,J be the ideal of compact operators relative toA and letF ₊ be the left-Fredholm class ofA. We call almost left-Fredholm the class = {A A: if P A is a projection and AP J then P J}. Then and the inclusion is proper unlessA is semifinite and has a non-large center. satisfies all of the algebraic properties ofF ₊ but it is generally not open. IfA is semifinite then A iff there are central projectionsG with G = I such that AG F₊(AG). Let :A A/J. Then the left almost essential spectrum ofA A, , coincides with the set of eigenvalues of (A)     

Local Stochastic Channeling Theory: Kinetic Functions in the Case of Interaction Between Fast Particles and Lattice Atoms

We investigate the motion of high-energy particles in a crystal with regard to their interaction with the thermal vibrations of the lattice atoms using analytic methods in the theory of Markov processes including the local Fokker–Planck equation. We construct a local matrix of random actions, which is used to introduce the main kinetic functions in the traverse-energy space, namely, the function a() of energy losses due to the dynamic friction and the diffusion function b(). We show that the singularities of the functions a() and b() are related to the distinction between the contributions to the kinetics from particles moving in three different regimes, namely, in the channeling, quasichanneling, and chaotic motion modes.     

Efficient nonparametric estimation of distribution density in the basis of algebraic polynomials

A nonparametric estimatef ^* of an unknown distribution densityf W is called locally minimax iff it is minimax for all not too small neighborhoodsW _g ,g W, simultaneously, whereW is some dense subset ofW. Radaviius and Rudzkis proved the existence of such an estimate under some general conditions. However, the construction of the estimate is rather complicated. In this paper, a new estimate is proposed. This estimate is locally minimax under some additional assumptions which usually hold for orthobases of algebraic polynomial and is almost as simple as the linear projective estimate. Thus, it takes a form convenient for the construction of an adaptive estimator, which does not usea-priori information about the smoothness of the density. The adaptive estimation problem is briefly discussed and an unknown density fitting by Jacobi polynomials is investigated more explicitly.     

On the distribution of square-full and cube-full integers

LetN _r (x) be the number ofr-full integers x and let _r (x) be the error term in the asymptotic formula forN _r (x). Under Riemann's hypothesis, we prove the estimates ₂(x)x^1/7+, ₃(x)x^97/804+(>0), which improve those of Cao and Nowak. We also investigate the distribution ofr-full andl-free numbers in short intervals (r=2,3). Our results sharpen Krätzel's estimates.     

Errors in approximate solutions of Cauchy's problem for a first-order quasilinear equation

The proximity is investigated of the solution of Cauchy's problem for the equation u _t +((u))_x= u _xx ((u) > 0) to the solution of Cauchy's problem for the equation u_t+ ((u))_x= 0, when the solution of the latter problem has a finite number of lines of discontinuity in the strip 0 t T. It is proved that, everywhere outside a fixed neighborhood of the lines of discontinuity, we have |u–u| C, where the constant C is independent of. Similar inequalities are derived for the first derivatives of u–u.Translated from Matematicheskie Zametki, Vol. 8, No. 3, pp. 309–320, September, 1970.In conclusion we express our gratitude to L. A. Chudov for his valuable advice concerning this work.     

Inverse Problems in the Theory of Singular Perturbations

First, in joint work with S. Bodine of the University of Puget Sound, Tacoma, Washington, USA, we consider the second-order differential equation ² y'=(1+² (x, ))y with a small parameter , where is analytic and even with respect to . It is well known that it has two formal solutions of the form y^±(x,)=e^±x/h^±(x,), where h^±(x,) is a formal series in powers of whose coefficients are functions of x. It has been shown that one (resp. both) of these solutions are 1-summable in certain directions if satisfies certain conditions, in particular concerning its x-domain. We show that these conditions are essentially necessary for 1-summability of one (resp. both) of the above formal solutions. In the proof, we solve a certain inverse problem: constructing a differential equation corresponding to a certain Stokes phenomenon. The second part of the paper presents joint work with Augustin Fruchard of the University of La Rochelle, France, concerning inverse problems for the general (analytic) linear equations ^r y' = A(x,) y in the neighborhood of a nonturning point and for second-order (analytic) equations y' - 2xy'-g(x,) y=0 exhibiting resonance in the sense of Ackerberg-O'Malley, i.e., satisfying the Matkowsky condition: there exists a nontrivial formal solution such that the coefficients have no poles at x=0.     

Large deviations for the invariant measure of a reaction-diffusion equation with non-Gaussian perturbations

Summary In this paper we establish a large deviations principle for the invariant measure of the non-Gaussian stochastic partial differential equation (SPDE) _t v =v +f(x,v )+(x,v ) . Here is a strongly-elliptic second-order operator with constant coefficients, h:=DH _xx-h, and the space variablex takes values on the unit circleS ¹. The functionsf and are of sufficient regularity to ensure existence and uniqueness of a solution of the stochastic PDE, and in particular we require that 0<mM wherem andM are some finite positive constants. The perturbationW is a Brownian sheet. It is well-known that under some simple assumptions, the solutionv ² is aC ^k (S ¹)-valued Markov process for each 0<1/2, whereC (S ¹) is the Banach space of real-valued continuous functions onS ¹ which are Hölder-continuous of exponent . We prove, under some further natural assumptions onf and which imply that the zero element ofC (S ¹) is a globally exponentially stable critical point of the unperturbed equation _t ⁰ = ⁰ +f(x,⁰), that has a unique stationary distributionv ^K, on (C (S ¹), (C ^K (S ¹))) when the perturbation parameter is small enough. Some further calculations show that as tends to zero,v ^K, tends tov ^K,0, the point mass centered on the zero element ofC (S ¹). The main goal of this paper is to show that in factv ^K, is governed by a large deviations principle (LDP). Our starting point in establishing the LDP forv ^K, is the LDP for the process , which has been shown in an earlier paper. Our methods of deriving the LDP forv ^K, based on the LDP for are slightly non-standard compared to the corresponding proofs for finite-dimensional stochastic differential equations, since the state spaceC (S ¹) is inherently infinite-dimensional.This work was performed while the author was with the Department of Mathematics, University of Maryland, College Park, MD 20742, USA     

On Logarithmic Smoothing of the Maximum Function

We consider the maximum function f resulting from a finite number of smooth functions. The logarithmic barrier function of the epigraph of f gives rise to a smooth approximation g of f itself, where >0 denotes the approximation parameter. The one-parametric family g converges – relative to a compact subset – uniformly to the function f as tends to zero. Under nondegeneracy assumptions we show that the stationary points of g and f correspond to each other, and that their respective Morse indices coincide. The latter correspondence is obtained by establishing smooth curves x() of stationary points for g , where each x() converges to the corresponding stationary point of f as tends to zero. In case of a strongly unique local minimizer, we show that the nondegeneracy assumption may be relaxed in order to obtain a smooth curve x().     

Stationary Gaussian processes with a finite correlation function

If the correlation function vanishes outside the segment [–R, R], then an upper estimate (uniform with respect to all such processes) is possible for the probability of the fact that on an other segment [–r, r] the process remains between – and . Such an estimate is obtained, decreasing for 0 asexp(–f(r/R ln ²+ ) and, moreover,r/R may be either 0 or +. The proof is based on an estimate of the form P_mQ_n c_mn P_m Q_n for norms of polynomials on a circle in the complex plane.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 184, pp. 279–288, 1990.