Proximity control in bundle methods for convex nondifferentiable minimization

Proximal bundle methods for minimizing a convex functionf generate a sequence {x ^k } by takingx ^k+1 to be the minimizer of , where is a sufficiently accurate polyhedral approximation tof andu ^k > 0. The usual choice ofu ^k = 1 may yield very slow convergence. A technique is given for choosing {u ^k } adaptively that eliminates sensitivity to objective scaling. Some encouraging numerical experience is reported.This research was supported by Project CPBP.02.15.     

Asymptotic normality in a coupon collector's problem

Summary Let {a _s , s=1, 2, ..., N} be a set of reals and {p _s , s=1, 2, ..., N} be a set of probabilities, i.e. p _s0 and p ₁+p ₂+...+p _N =1. Let I ₁ I ₂,... be independent random variables, all with the distribution P(I=s)=p _s , s=1, 2, ..., N. Put U _v =l if I _v {I ₁, I ₂, ..., I _v –1} and U _v =0 otherwise, v=1, 2, .... The random variable Z _n = is called the bonus sum after ncoupons for a coupon collector in the situation {(p _s , a _s ), s=1, 2, ..., N}.Consider a sequence {(p _ks , a _ks ), s=l, 2, ..., N _k }, k=1, 2, ..., of collector situations, and let {Z _n ^(k) , n=1, 2, ...}, k=1, 2, ..., be the corresponding sequence of bonus sum variables. Let d be an arbitrary natural number and let , k=1, 2, ..., where 1 n _k ⁽¹⁾<n _k ⁽²⁾<< n _k ^(d) .We assume that N ^(k) t8 and that .It is shown that the random vector V ^(k) is, under general conditions, asymptotically (as kt8) normally distributed. An asymptotic expression for the covariance matrix of V ^(k) is derived.Research supported in part at Stanford University, Stanford, California under contract N0014-67-A-0112-0015.     

On cubic polynomials I. Hua's estimate of exponential sums

Hua andChen gave estimates of sums wheree(z)=e ^2iz and is a polynomial of the typef(x)/q wheref(x)=a _k x ^k +...+a ₁ x with integer coefficients having gcd (q, a _k ,...,a ₁)=1 But no good estimates hold for these sums whenq is small in comparison tok. We therefore consider here a related but different class of polynomials. Special emphasis is given to the cubic case.In subsequent papers of this series we shall deal with cubic exponential sums in many variables and withp-adic and rational zeros of systems of cubic forms.Partially supported by NSF contract NSF-MCS-8015356.     

Equally-weighted formulas for numerical differentiation

Equally-weighted formulas for numerical differentiation at a fixed pointx=a, which may be chosen to be 0 without loss in generality, are derived for (1) whereR _2n =0 whenf(x) is any (2n)^th degree polynomial. Equation (1) is equivalent to (2) ,r=1,2,..., 2n. By choosingf(x)=1/(z–x),x _i fori=1,..., n andx _i fori=n+1,..., 2n are shown to be roots ofg _n (z) andh _n (z) respectively, satisfying (3) . It is convenient to normalize withk=(m–1)!. LetP _s (z) denotez ^s · numerator of the (s+1)^th diagonal member of the Padé table fore ^x , frx=1/z, that numerator being a constant factor times the general Laguerre polynomialL _s ^–2s–1 (x), and letP _s (X _i )=0, i=1, ...,s. Then for anym, solutions to (1) are had, for2n=2ms, forx _i , i=1, ...,ms, andx _i , i=ms+1,..., 2ms, equal to all them ^th rootsX _i ^1/m and (–X _i )^1/m respectively, and they give {(2s+1)m–1}^th degree accuracy. For2sm2n(2s+1)m–1, these (2sm)-point solutions are proven to be the only ones giving (2n)^th degree accuracy. Thex _i 's in (1) always include complex values, except whenm=1, 2n=2. For2sm<2n(2s+1)m–1,g _n (z) andh _n (z) are (n–sm)-parameter families of polynomials whose roots include those ofg _ms (z) andh _ms (z) respectively, and whose remainingn–ms roots are the same forg _n (z) andh _n (z). Form>1, and either 2n<2m or(2s+1)m–1<2n<(2s+2)m, it is proven that there are no non-trivial solutions to (1), real or complex. Form=1(1)6, tables ofx _i are given to 15D, fori=1(1)2n, where 2n=2ms ands=1(1) [12/m], so that they are sufficient for attaining at least 24^th degree accuracy in (1).Presented at the Twelfth International Congress of Mathematicians, Stockholm, Sweden, August 15–22, 1962.General Dynamics/Astronautics. A Division of General Dynamics Corporation.     

Whitney Interpolation Constants Bounded by 2 for k = 5, 6, 7

Let f C[0, 1], k = 5, 6, 7. We prove that if f(i/(k – 1)) = 0, i = 0, 1,..., k – 1, then      

Uniqueness of solutions for some nonlinear Dirichlet problems

We consider here a class of nonlinear Dirichlet problems, in a bounded domain , of the form

Some remarks on Vinogradov's mean value theorem and Tarry's problem

LetW(k, 2) denote the, least numbers for which the system of equations has a solution with . We show that for largek one hasW(k, 2)1/2k ²(logk+loglogk+O(1)), and moreover that whenK is large, one hasW(k, 2)1/2k(k+1)+1 for at least one valuek in the interval [K, K ^3/4+]. We show also that the leasts for which the expected asymptotic formula holds for the number of solutions of the above system of equations, inside a box, satisfiessk ²(logk+O(loglogk).Research supported in part by NSF grant DMS-9303505, an Alfred P. Sloan Research Fellowship, and a Fellowship from the David and Lucile Packard Foundation.     

M-estimators of structural parameters in pseudolinear models

Real valued M-estimators in a statistical model 1 with observations are replaced by -valued M-estimators in a new model with observations where are regressors, is a structural parameter and a structural function of the new model. Sufficient conditions for the consistency of are derived, motivated by the sufficiency conditions for the simpler parent estimator The result is a general method of consistent estimation in a class of nonlinear (pseudolinear) statistical problems. If F has a natural exponential density e^{x–b( x )} then our pseudolinear model with u = (g o )^–1 reduces to the well known generalized linear model, provided () = db()/d and g is the so-called link function of the generalized linear model. General results are illustrated for special pairs and leading to some classical M-estimators of mathematical statistics, as well as to a new class of generalized -quantile estimators.     

An O(n 3 L) primal—dual potential reduction algorithm for solving convex quadratic programs

In this paper we combine partial updating and an adaptation of Anstreicher's safeguarded linesearch of the primal—dual potential function with Kojima, Mizuno and Yoshise's potential reduction algorithm for the linear complementarity problem to obtain an O(n ³ L) algorithm for convex quadratic programming. Our modified algorithm is a long step method that requires at most O( L) steps.This research was supported in part by ONR Contract N-00014-87-K0214, NSF Grants DMS-85-12277 and DMS-91-06195.     

Processes of flats induced by higher dimensional processes III

Stationary processes of k-flats in ^d can be thought of as point processes on the Grassmannian _k ^d of k-dimensional subspaces of ^d . If such a process is sampled by a (d–k+ j)-dimensional space F, it induces a process of j-flats in F. In this work we will investigate the possibility of determining the original k-process from knowledge of the intensity measures of the induced j-processes. We will see that this is impossible precisely when 1<k<d–1 and j=0,...,2[r/2]–1, where r is the rank of the manifold _k ^d . We will show how the problem is equivalent to the study of the kernel of various integral transforms, these will then be investigated using harmonic analysis on Grassmannian manifolds.The research of the first and third authors was supported in part by NSF grants DMS-9207019 and DMS-9304284. The research of the second author was supported in part by NFR contract number R-RA 4873-306 and the Swedish Academy of Sciences.     

An inexact primal–dual path following algorithm for convex quadratic SDP

We propose primal–dual path-following Mehrotra-type predictor–corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: , where is a self-adjoint positive semidefinite linear operator on , b∈R ^m , and is a linear map from to R ^m . At each interior-point iteration, the search direction is computed from a dense symmetric indefinite linear system (called the augmented equation) of dimension m + n(n + 1)/2. Such linear systems are typically very large and can only be solved by iterative methods. We propose three classes of preconditioners for the augmented equation, and show that the corresponding preconditioned matrices have favorable asymptotic eigenvalue distributions for fast convergence under suitable nondegeneracy assumptions. Numerical experiments on a variety of QSDPs with n up to 1600 are performed and the computational results show that our methods are efficient and robust. Research supported in part by Academic Research Grant R146-000-076-112.     

The Gaussian Isoperimetric Inequality and Transportation

Any probability measure on ^d which satisfies the Gaussian or exponential isoperimetric inequality fulfils a transportation inequality for a suitable cost function. Suppose that W (x) dx satisfies the Gaussian isoperimetric inequality: then a probability density function f with respect to W (x) dx has finite entropy, provided that t . This strengthens the quadratic logarithmic Sobolev inequality of Gross (Amr. J. Math 97 (1975) 1061). Let (dx) = e ^–(x) dx be a probability measure on ^d, where is uniformly convex. Talagrand's technique extends to monotone rearrangements in several dimensions (Talagrand, Geometric Funct. Anal. 6 (1996) 587), yielding a direct proof that satisfies a quadratic transportation inequality. The class of probability measures that satisfy a quadratic transportation inequality is stable under multiplication by logarithmically bounded Lipschitz densities.     

The action functional for a family of diffusion fields in the plane

For a random fieldx _st defeined by , we find an explicit form for the action functional in the sense of Venttsel'-Freidlin.Translated fromTeoriya Sluchainykh Protsessov, Vol. 15, pp. 40–47, 1987.     

An Ω-theorem for an error term related to the sum-of-divisors function

Let denote the sum-of-divisors function, and set . Gronwall and Wigert proved (independently) in 1913 and 1914, respectively, thatE ₁ (x)= (x log logx). In this paper we obtain the more preciseE ₁ (x)=_–(x log logx). The method consists in averaging over suitable arithmetic progressions, and was suggested by the work ofP. Erdös andH. N. Shapiro [Canad. J. Math. 3–4, 375–385 (1951)] on the error term corresponding to Euler's functions, .     

The Structure of Disjoint Iteration Groups on the Circle

The aim of the paper is to investigate the structure of disjoint iteration groups on the unit circle that is, families of homeomorphisms such that and each F ^veither is the identity mapping or has no fixed point ((V, +) is an arbitrary 2-divisible nontrivial (i.e., card V> 1) abelian group).     

First Exit Time from a Bounded Interval for a Certain Class of Additive Functionals of Brownian Motion

Let (B _t) _t0 be standard Brownian motion starting at y, X _t = x + ^t ₀ V(B _s) ds for x (a, b), with V(y) = y if y0, V(y)=–K(–y) if y0, where >0 and K is a given positive constant. Set _ab=inf{t>0: X _t(a, b)} and ₀=inf{t>0: B _t=0}. In this paper we give several informations about the random variable _ab. We namely evaluate the moments of the random variables , and also show how to calculate the expectations . Then, we explicitly determine the probability laws of the random variables as well as the probability by means of special functions.     

Zur Interpolation und Integration differenzierbarer periodischer Funktionen

Summary Letx ₀<x ₁<...<x _n–1<x ₀+2 be nodes having multiplicitiesv ₀,...,v _n–1, 1v _k r (0k<n). We approximate the evaluation functional ,x fixed, and the integral respectively by linear functionals of the form and determine optimal weights for the Favard classesW _r C ₂. In the even case of optimal interpolation these weights are unique except forr=1,x(x _k +x _k–1)/2 mod 2. Moreover we get periodic polynomial splinesw _{k, j} (0k<n, 0j<v _k ) of orderr such that are the optimal weights. Certain optimal quadrature formulas are shown to be of interpolatory type with respect to these splines. For the odd case of optimal interpolation we merely have obtained a partial solution.

Bojanov hat in [4, 5] ähnliche Resultate wie wir erzielt. Um Wiederholungen zu vermeiden, werden Resultate, deren Beweise man bereits in [4, 5] findet, nur zitiert     

Random k-Sat: A Tight Threshold For Moderately Growing k

We consider a random instance I of k-SAT with n variables and m clauses, where k=k(n) satisfies k—log₂ n. Let m ₀=2 ^k nln2 and let =(n)>0 be such that n. We prove that

Some Convergence Properties of Descent Methods

In this paper, we discuss the convergence properties of a class of descent algorithms for minimizing a continuously differentiable function f on R ⁿ without assuming that the sequence { x _k } of iterates is bounded. Under mild conditions, we prove that the limit infimum of is zero and that false convergence does not occur when f is convex. Furthermore, we discuss the convergence rate of { } and { f(x _k )} when { x _k } is unbounded and { f(x _k )} is bounded.     

On Dirichlet Processes Associated with Second Order Divergence Form Operators

Let be a d - dimensional Markov family corresponding to a uniformly elliptic second order divergence form operator. We show that for any quasi continuous in the Sobolev space the process (X) admits under P ^x a decomposition into a martingale additive functional (AF) M and a continuous AF A of zero quadratic variation for almost every starting point x if q=2, for quasi every x if q>2 and for every if is continuous, d=1 and or d>1 and q>d. Our decomposition enables us to show that in the case of symmetric operator the energy of A equals zero if q=2 and that the decomposition of (X) into the martingale AF M and the AF of zero energy A is strict if for some q>d. Moreover, our decomposition provides a probabilistic representation of A .