On the projected subgradient method for nonsmooth convex optimization in a Hilbert space

We consider the method for constrained convex optimization in a Hilbert space, consisting of a step in the direction opposite to an _k -subgradient of the objective at a current iterate, followed by an orthogonal projection onto the feasible set. The normalized stepsizes _k are exogenously given, satisfying _{k=0 k} = , _{k=0 k} ² < , and _k is chosen so that _{k k} for some > 0. We prove that the sequence generated in this way is weakly convergent to a minimizer if the problem has solutions, and is unbounded otherwise. Among the features of our convergence analysis, we mention that it covers the nonsmooth case, in the sense that we make no assumption of differentiability off, and much less of Lipschitz continuity of its gradient. Also, we prove weak convergence of the whole sequence, rather than just boundedness of the sequence and optimality of its weak accumulation points, thus improving over all previously known convergence results. We present also convergence rate results. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research of this author was partially supported by CNPq grant nos. 301280/86 and 300734/95-6.     

Packing of partial designs

We say that two hypergraphsH ₁ andH ₂ withv vertices eachcan be packed if there are edge disjoint hypergraphsH ₁ andH ₂ on the same setV ofv vertices, whereH _i is isomorphic toH _i.It is shown that for every fixed integersk andt, wheretk2t–2 and for all sufficiently largev there are two (t, k, v) partial designs that cannot be packed. Moreover, there are twoisomorphic partial (t, k, v)-designs that cannot be packed. It is also shown that for every fixedk2t–1 and for all sufficiently largev there is a (₁,t,k,v) partial design and a (₁,t,k,v) partial design that cannot be packed, where _{1 2}O(v ^k–2t+1 logv). Both results are nearly optimal asymptotically and answer questions of Teirlinck. The proofs are probabilistic.     

An infinite dimensional analogue of the Albeverio-Röckner's theorem on Fukushima's conjecture

LetX be the solution of the SDE:dX _t = (X _t)dB _t +b(X _t)dt, with andb C _b (R) such that >0 for some constant , andB a real Brownian motion. Let be the law ofX onE=C([0, 1],R) andk E* – {0}, whereE* is the topological dual space ofE. Consider the classical form: _k (u, v)=u / kv / kd, whereu andv are smooth functions onE. We prove that, if _k is closable for anyk in a dense subset ofE* and if the smooth functions are contained in the domain of the generator of the closure of _k , must be a constant function.     

Propriété de stabilité de la fonction extrémale relative

Nous donnons une caractérisation des domaines DX pour lesquels la fonction extrémale relative ^*(,E,D) a la propriété de stabilité pour tout ED, i.e. lim _k^*(,E,D _k )=^*(,E,D), ED. Ensuite, nous étudions la relation entre cette propriété et les enveloppes pluripolaires. Nous concluons par quelques remarques sur la propriété de stabilité lim _k^*(,E _k ,D)=^*(,E,D).     

A family of noetherian rings with their finite length modules under control

We investigate the category mod of finite length modules over the ring =A _k , where is a V-ring, i.e. a ring for which every simple module is injective, k a subfield of its centre and A an elementary k-algebra. Each simple module E _j gives rise to a quasiprogenerator P _j = A E _j . By a result of K. Fuller, P _j induces a category equivalence from which we deduce that mod _j mod EndP _j . As a consequence we can(1) construct for each elementary k-algebra A over a finite field k a nonartinian noetherian ring such that modA mod(2) find twisted versions of algebras of wild representation type such that itself is of finite or tame representation type (in mod)(3) describe for certain rings the minimal almost split morphisms in mod and observe that almost all of these maps are not almost split in Mod.     

On the smoothness of the moduli space of mathematical instanton bundles

In this paper we prove that the moduli spaces MI _2n+1(k) of mathematical instanton bundles on ²ⁿ⁺¹ with quantum number k are singular for n 2 and k 3 ,giving a positive answer to a conjecture made by Ancona and Ottaviani in 1993.     

On sequences of Fourier coefficients of functions of Hölder classes

The following theorem is proved. Let { _k(t)} be an arbitrary complete orthonormal system on [0, 1] and let 1/2<<1. Then anf(t) C exists for all< such that _k=1 · |c_k(f)|^p=, p=2/(l+2), where .Translated from Matematicheskie Zametki, Vol. 6, No. 5, pp. 567–572, November, 1969.The authors wish to thank P. P. Zabreiko and P. L. Ul'yanov for helpful discussions and remarks.     

Elations and symmetric designs having projective subspaces

Consider symmetric 2-designs D which have an automorphism group G containing sufficiently many elations. This paper investigates the case where there are the least number of elations. Under certain assumptions it is shown that D has a projective subspace and in a particular case D _n,q or D is obtained from _n,q by a process called K-alteration.The results in this paper form part of a PhD thesis submitted by the author to the University of London. The author gratefully acknowledges the support of the Commonwealth Scholarship Commission.     

Homothetic floating bodies

We show that a convex bodyK in ⁿ is homothetic to an ellipsoid if there is a sequence { _k }k converging to 0 so thatK is homothetic to its floating bodiesK _k.Supported by NSF grant DMS-9108003.     

Sum of Divisors in a Ring of Gaussian Integers

We construct an asymptotic formula for a sum function for _a (), where _a () is the sum of the ath powers of the norms of divisors of the Gaussian integer on an arithmetic progression ₀ (mod ) and in a narrow sector ₁ arg < ₂. For this purpose, we use a representation of _a (n) in the form of a series in the Ramanujan sums.     

Mouvement moyen et système dynamique gaussien

Summary In the situation of the classical mean motion, we haven planets moving in the plane, planetk+1 being a satellite of planetk. A classcal result then states that planetn has a mean motion,i.e. its mean angular speed between time 0 and timet has a limit whent. We show in this article that any real gaussian dynamical system can be interpreted as the limit of this situation, whenn. From a given nonatomic probability measure on [0,], we construct a transformationT of the complex brownian path (B _u)_0u1 which preserves Wiener measure.T is defined as the limit of a sequenceT _n, whereT _n acts as the motion of 2ⁿ planets. In this way we get a real gaussian dynamical system, whose spectral measure is the symetric probability on [-,] obtained from . The transformationT can be inserted in a flow (T ^t) _t, and the orbitstZ _t=B ₁T ^t still have almost surely a mean motion, which is the mean of .     

Diffusions réfléchies réversibles dégénérées

On a domain D in ^d, for a smooth enough probability density and a diffusion matrix which can degenerate, we construct the law Q ^s of a (x)d -symmetric reflecting process in D with matrix . Therefore, we use the associated Dirichlet form and a sequence of approximating processes already used by Pardoux and R. Williams in [23]. Under mild conditions on the boundary ofD (finite Minkowski content), we prove that Q ^s is the law of a semi-martingale and provide its decomposition. Comparing with the decomposition in additive functionals, we conclude that the process is reflected in the conormal direction ^* n where n denotes Chen's normal (cf [10]), that is, the reflection direction of the Brownian motion in Kuramochi compactification.     

Approximation by linear methods of summation of orthogonal series

We give an estimate of the rapidity of convergence of certain linear means of the orthogonal series _k =0 c_{k k} (x) to the functionf (x) L₂ (a, b) defined by this series according to the Riesz-Fisher theorem for almost all x (a, b). The results obtained are, in a certain sense, final.Translated from Matematicheskie Zametki, Vol. 3, No. 3, pp. 345–356, March, 1968.     

A graded scale of parametric families of distributions,and parameter estimates based on the sample mean

Summary Denote by _k a class of familiesP={P} of distributions on the line R¹ depending on a general scalar parameter , being an interval of R¹, and such that the moments µ₁()=xdP ,...,µ_2k ()=x ^2k dP are finite, ₁ (), ..., _k (), _k+1 () ..., _k () exist and are continuous, with ₁ () 0, and _j +1 ()= ₁ () _j () +[₂() -₁()²] _j ()/ ₁ (), J=2, ..., k. Let ₁=¯x=x ₁ + ... +x _n/n, ₂=x ₁ ² + ... +x _n ²/n, ..., _k =(x ₁ ^k + ... +x _n ^k/n denote the sample moments constructed for a sample x₁, ..., x_n from a population with distribution Pg. We prove that the estimator of the parameter by the method of moments determined from the equation ₁= ₁() and depending on the observations x₁, ..., x_n only via the sample mean ¯x is asymptotically admissible (and optimal) in the class _k of the estimators determined by the estimator equations of the form ₀ () + ₁ () ₁ + ... + _k () _k =0 if and only ifP _k .The asymptotic admissibility (respectively, optimality) means that the variance of the limit, as n (normal) distribution of an estimator normalized in a standard way is less than the same characteristic for any estimator in the class under consideration for at least one 9 (respectively, for every ).The scales arise of classes _{1 2}... of parametric families and of classes _{1 2} ... of estimators related so that the asymptotic admissibility of an estimator by the method of moments in the class _k is equivalent to the membership of the familyP in the class _k .The intersection consists only of the families of distributions with densities of the form h(x) exp {C₀() + C₁() x } when for the latter the problem of moments is definite, that is, there is no other family with the same moments ₁ (), ₂ (), ...Such scales in the problem of estimating the location parameter were predicted by Linnik about 20 years ago and were constructed by the author in [1] (see also [2, 3]) in exact, not asymptotic, formulation.Translated from Problemy Ustoichivosti Stokhasticheskikh Modelei, pp. 41–47, 1981.     

Extension of Subgradient Techniques for Nonsmooth Optimization in Banach Spaces

In this paper we continue the study of the subgradient method for nonsmooth convex constrained minimization problems in a uniformly convex and uniformly smooth Banach space. We consider the case when the stepsizes satisfy _{k=1 k} =, lim _{k k} =0.     

Ultrafilter translations

We develop a method for extending results about ultrafilters into a more general setting. In this paper we shall be mainly concerned with applications to cardinality logics. For example, assumingV=L, Gödel's Axiom of Constructibility, we prove that if > then the logic with the quantifier there exist many is (,)-compact if and only if either is weakly compact or is singular of cofinality<. As a corollary, for every infinite cardinals and , there exists a (,)-compact non-(,)-compact logic if and only if either < orcf<cf or < is weakly compact.Counterexamples are given showing that the above statements may fail, ifV=L is not assumed.However, without special assumptions, analogous results are obtained for the stronger notion of [,]-compactness.     

An approach to the constructivization of Cantor's set theory

A new approach is proposed for the construction of constructive analogs of set theory in hyperarithmetic languages , where is a scale of constructive ordinals. For every ordinal in the language , a special relation of equality = is defined for codes of one-parameter formulas (conditions) of the level in a constructive hyperarithmetic hierarchy corresponding to the scale . The membership relation, (also expressible in the language ), is defined by the conditionx y=z(z= x&z y), where the relation is obtained by suitable refinement of the traditional representations of the constructive relation of membership. This results in a hierarchy of constructive analogsM of the theory of sets (in which the sets are represented by codes of conditions of level , identified modulo the relation =, and is taken as the relation of membership). Some properties of this hierarchy are introduced which show that for the limits ,M is sufficiently rich from the traditional set theoretic standpoint.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 68, pp. 38–49, 1977.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

Cross-cuts in the power set of an infinite set

In the power setP(E) of a setE, the sets of a fixed finite cardinalityk form across-cut, that is, a maximal unordered setC such that ifX, Y E satisfyXY, X someX inC, andY someY inC, thenXZY for someZ inC. ForE=, ₁, and ₂, it is shown with the aid of the continuum hypothesis thatP(E) has cross-cuts consisting of infinite sets with infinite complements, and somewhat stronger results are proved for and ₁.The work reported here has been partially supported by NSERC Grant No. A8054.     

On convergence subsystems of orthonormal systems

It is proved that for any sequence {R _k} _k=1 of real numbers satisfyingR _kk (k1) andR _k=o(k log₂ k),k, there exists an orthonormal system {n _k(x)} _n=1 ,x (0;1), such that none of its subsystems {n _k(x)} _k=1 withn _kR_k (k1) is a convergence subsystem.