New error bounds and their applications to convergence analysis of iterative algorithms

We present two new error bounds for optimization problems over a convex set whose objective function f is either semianalytic or γ-strictly convex, with γ≥1. We then apply these error bounds to analyze the rate of convergence of a wide class of iterative descent algorithms for the aforementioned optimization problem. Our analysis shows that the function sequence {f(x ^k )} converges at least at the sublinear rate of k ^-ε for some positive constant ε, where k is the iteration index. Moreover, the distances from the iterate sequence {x ^k } to the set of stationary points of the optimization problem converge to zero at least sublinearly. Received: October 5, 1999 / Accepted: January 1, 2000?Published online July 20, 2000     

Cusp forms

LetG andH ⊂G be two real semisimple groups defined overQ. Assume thatH is the group of points fixed by an involution ofG. Letπ ⊂L ²(H\G) be an irreducible representation ofG and letf επ be aK-finite function. Let Γ be an arithmetic subgroup ofG. The Poincaré seriesP _f(g)=Σ_H∩ΓΓ f(γ{}itg) is an automorphic form on Γ\G. We show thatP _f is cuspidal in some cases, whenH ∩Γ\H is compact. Partially supported by NSF Grant # DMS 9103608.     

Convergence Properties of the Regularized Newton Method for the Unconstrained Nonconvex Optimization

The regularized Newton method (RNM) is one of the efficient solution methods for the unconstrained convex optimization. It is well-known that the RNM has good convergence properties as compared to the steepest descent method and the pure Newton’s method. For example, Li, Fukushima, Qi and Yamashita showed that the RNM has a quadratic rate of convergence under the local error bound condition. Recently, Polyak showed that the global complexity bound of the RNM, which is the first iteration k such that ‖∇ f(x _k )‖≤ε, is O(ε ⁻⁴), where f is the objective function and ε is a given positive constant. In this paper, we consider a RNM extended to the unconstrained “nonconvex” optimization. We show that the extended RNM (E-RNM) has the following properties. (a) The E-RNM has a global convergence property under appropriate conditions. (b) The global complexity bound of the E-RNM is O(ε ⁻²) if ∇ ² f is Lipschitz continuous on a certain compact set. (c) The E-RNM has a superlinear rate of convergence under the local error bound condition.     

A convexity theorem for multiplicative functions

We generalize a well known convexity property of the multiplicative potential function. We prove that, given any convex function g : \mathbbR^m ? [0, ￥]{g : \mathbb{R}^m \rightarrow [{0}, {\infty}]}, the function ${({\rm \bf x},{\rm \bf y})\mapsto g({\rm \bf x})^{1+\alpha}{\bf y}^{-{\bf \beta}}, {\bf y}>{\bf 0}}${({\rm \bf x},{\rm \bf y})\mapsto g({\rm \bf x})^{1+\alpha}{\bf y}^{-{\bf \beta}}, {\bf y}>{\bf 0}}, is convex if β ≥ 0 and α ≥ β ₁ + ··· + β _n . We also provide further generalization to functions of the form (x,y₁, . . . , y_n)? g(x)^1+af₁(y₁)^-b₁ ···f_n(y_n)^-b_n{({\rm \bf x},{\rm \bf y}_1, . . . , {y_n})\mapsto g({\rm \bf x})^{1+\alpha}f_1({\rm \bf y}_1)^{-\beta_1} \cdot \cdot \cdot f_n({\rm \bf y}_n)^{-\beta_n} } with the f _k concave, positively homogeneous and nonnegative on their domains.     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

On a class of non-uniform average sampling expansions and partial reconstruction in subspaces of L 2(?)

Let ϕ be a function in the Wiener amalgam space W_￥(L₁)\emph{W}_{\infty}(L_1) with a non-vanishing property in a neighborhood of the origin for its Fourier transform [^(f)]\widehat{\phi}, t={t_n}_{n ? \mathbb Z}{\bf \tau}=\{\tau_n\}_{n\in {{\mathbb Z}}} be a sampling set on ℝ and V_f^tV_\phi^{\bf \tau} be a closed subspace of L₂(\mathbbR)L_2(\hbox{\ensuremath{\mathbb{R}}}) containing all linear combinations of τ-translates of ϕ. In this paper we prove that every function f ? V_f^tf\in V_\phi^{\bf \tau} is uniquely determined by and stably reconstructed from the sample set L_f^t(f)={ò_\mathbbR f(t)[`(f(t-t_n))] dt}_{n ? \mathbb Z}L_\phi^{\bf \tau}(f)=\Big\{\int_{\hbox{\ensuremath{\mathbb{R}}}} f(t) \overline{\phi(t-\tau_n)} dt\Big\}_{n\in {{\mathbb Z}}}. As our reconstruction formula involves evaluating the inverse of an infinite matrix we consider a partial reconstruction formula suitable for numerical implementation. Under an additional assumption on the decay rate of ϕ we provide an estimate to the corresponding error.     

Hilbert’s irreducibility theorem for prime degree and general polynomials

Letf (X, t)εℚ[X, t] be an irreducible polynomial. Hilbert’s irreducibility theorem asserts that there are infinitely manyt ₀εℤ such thatf (X, t ₀) is still irreducible. We say thatf (X, t) isgeneral if the Galois group off (X, t) over ℚ(t) is the symmetric group in its natural action. We show that if the degree off with respect toX is a prime ≠ 5 or iff is general of degree ≠ 5, thenf (X, t ₀) is irreducible for all but finitely manyt ₀εℤ unless the curve given byf (X, t)=0 has infinitely many points (x ₀,t ₀) withx ₀εℚ,t ₀εℤ. The proof makes use of Siegel’s theorem about integral points on algebraic curves, and classical results about finite groups, going back to Burnside, Schur, Wielandt, and others. Supported by the DFG.     

Geometric progressions in sumsets over finite fields

Given two sets A, B í \Bbb F_q^d{\cal A}, {\cal B}\subseteq {\Bbb F}_q^d , the set of d dimensional vectors over the finite field \Bbb F_q{\Bbb F}_q with q elements, we show that the sumset A+B = {a+b | a ? A, b ? B}{\cal A}+{\cal B} = \{{\bf a}+{\bf b}\ \vert\ {\bf a} \in {\cal A}, {\bf b} \in {\cal B}\} contains a geometric progression of length k of the form vΛ ^j , where j = 0,…, k − 1, with a nonzero vector v ? \Bbb F_q^d{\bf v} \in {\Bbb F}_q^d and a nonsingular d × d matrix Λ whenever # A # B 3 20 q^2d-2/k\# {\cal A} \# {\cal B} \ge 20 q^{2d-2/k} . We also consider some modifications of this problem including the question of the existence of elements of sumsets on algebraic varieties.     

Indices of hyperelliptic curves over p-adic fields

Let k be a p-adic field of odd residue characteristic and let C be a hyperelliptic (or elliptic) curve defined by the affine equation Y ²=h(X). We discuss the index of C if h(X)=ɛf(X), where ɛ is either a non-square unit or a uniformising element in O _k and f(X) a monic, irreducible polynomial with integral coefficients. If a root θ of f generates an extension k(θ) with ramification index a power of 2, we completely determine the index of C in terms of data associated to θ. Theorem 3.11 summarizes our results and provides an algorithm to calculate the index for such curves C. Received: 14 July 1997 / Revised version: 16 February 1998     

Reconstruction of functions from their integrals over<Emphasis Type="Italic">k</Emphasis>-planes

Thek-plane Radon transform assigns to a functionsf(x) on ℝ ⁿ the collection of integralsf(τ)=∫ _τ f over allk-dimensional planesτ. We give a systematic treatment of two inversion methods for this transform, namely, the method of Riesz potentials, and the method of spherical means. We develop new analytic tools which allow to invertf(τ) under minimal assumptions forf. It is assumed thatfεL ^p , 1≤p<n/k, orf is a continuous function with minimal rate of decay at infinity. In the framework of the first method, our approach employs intertwining fractional integrals associated to thek-plane transform. Following the second method, we extend the original formula of Radon for continuous functions on ℝ² tofεL ^p (ℝ ⁿ ) and all 1≤k<n. New integral formulae and estimates, generalizing those of Fuglede and Solmon, are obtained. The work was supported in part by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).     

The reverse spelling of an FPrt-universal word in two letters

ForX a set the expression Prt(X) denotes the composition monoid of all functionsf X ×X. Fork a positive integer the letterk denotes also the set of all nonnegative integers less thank. Whenk > 1 the expression r_k denotes the connected injective element {<i, i + 1>i k – 1} in Prt (k). We show for every word w=w(x,y) in a two-letter alphabet that if the equation w(x, y)=r_k has a solution =y) ²Prt(k) then ¯w(x,y)=r_k also has a solution in²Prt(k), where ¯w is the word obtained by spelling the wordw backwards. It is a consequence of this theorem that if for every finite setX and for everyf Prt(X) the equation w(x,y)=f has a solution in²Prt(X) then for every suchX andf the equation ¯w(x, y)=f has a solution in²Prt(X).Presented by J. Mycielski.     

On convex optimization without convex representation

We consider the convex optimization problem P:min_x {f(x) : x ? K}{{\rm {\bf P}}:{\rm min}_{\rm {\bf x}} \{f({\rm {\bf x}})\,:\,{\rm {\bf x}}\in{\rm {\bf K}}\}} where f is convex continuously differentiable, and K ì \mathbb Rⁿ{{\rm {\bf K}}\subset{\mathbb R}^n} is a compact convex set with representation {x ? \mathbb Rⁿ : g_j(x) 3 0, j = 1,?,m}{\{{\rm {\bf x}}\in{\mathbb R}^n\,:\,g_j({\rm {\bf x}})\geq0, j = 1,\ldots,m\}} for some continuously differentiable functions (g _j ). We discuss the case where the g _j ’s are not all concave (in contrast with convex programming where they all are). In particular, even if the g _j are not concave, we consider the log-barrier function f_m{\phi_\mu} with parameter μ, associated with P, usually defined for concave functions (g _j ). We then show that any limit point of any sequence (x_m) ì K{({\rm {\bf x}}_\mu)\subset{\rm {\bf K}}} of stationary points of f_m, m? 0{\phi_\mu, \mu \to 0} , is a Karush–Kuhn–Tucker point of problem P and a global minimizer of f on K.     

Expansion of derivatives in one-dimensional dynamics

We study the expansion of derivatives along orbits of real and complex one-dimensional mapsf, whose Julia setJ _f attracts a finite setCrit of non-flat critical points. Assuming that for eachcεCrit, either |D f ⁿ(f(c))|→∞ (iff is real) orb _n·|Df ⁿ(f(c))|→∞ for some summable sequence {b _n} (iff is complex; this is equivalent to summability of |D f ⁿ(f(c))|⁻¹), we show that for everyxεJ _f\U _i f ⁻ⁱ(Crit), there existℓ(x)≤max _c ℓ(c) andK′(x)>0

On double sine and cosine transforms,Lipschitz and Zygmund classes

We consider complex-valued functions f ∈ L 1 (R+2),where R +:= [0,∞),and prove sufficient conditions under which the double sine Fourier transform f ss and the double cosine Fourier transform f cc belong to one of the two-dimensional Lipschitz classes Lip(α,β) for some 0 α,β≤ 1;or to one of the Zygmund classes Zyg(α,β) for some 0 α,β≤ 2.These sufficient conditions are best possible in the sense that they are also necessary for nonnegative-valued functions f ∈ L 1 (R+2).     

Construction of positive definite cubature formulae and approximation of functions via Voronoi tessellations

Let Ω ⊂ ℝ ^d be a compact convex set of positive measure. In a recent paper, we established a definiteness theory for cubature formulae of order two on Ω. Here we study extremal properties of those positive definite formulae that can be generated by a centroidal Voronoi tessellation of Ω. In this connection we come across a class of operators of the form L_n[f](x): = ?_i=1ⁿ f_i(x)(f(y_i) + á?f(y_i), x-y_i?)L_n[f](\boldsymbol{x}):= \sum_{i=1}^n \phi_i(\boldsymbol{x})(f(\boldsymbol{y}_i) + \langle\nabla f(\boldsymbol{y}_i), \boldsymbol{x}-\boldsymbol{y}_i\rangle), where y₁,..., y_n\boldsymbol{y}_1,\dots, \boldsymbol{y}_n are distinct points in Ω and {ϕ ₁, ..., ϕ _n } is a partition of unity on Ω. We present best possible pointwise error estimates and describe operators L _n with a smallest constant in an L ^p error estimate for 1 ≤ p < ∞ . For a generalization, we introduce a new type of Voronoi tessellation in terms of a twice continuously differentiable and strictly convex function f. It allows us to describe a best operator L _n for approximating f by L _n [f] with respect to the L ^p norm.     

Sharp estimates for derivatives of functions in the Sobolev classes $$ \mathop {W_2^r }\limits^ \circ $$(−1,1)

Explicit formulas are obtained for the maximum possible values of the derivatives f ^(k)(x), x ∈ (−1, 1), k ∈ {0, 1, ..., r − 1}, for functions f that vanish together with their (absolutely continuous) derivatives of order up to ≤ r − 1 at the points ±1 and are such that $ \left\| {f^{\left( r \right)} } \right\|_{L_2 ( - 1,1)} \leqslant 1 $ \left\| {f^{\left( r \right)} } \right\|_{L_2 ( - 1,1)} \leqslant 1 . As a corollary, it is shown that the first eigenvalue λ _1,r of the operator (−D ²) ^r with these boundary conditions is $ \sqrt 2 $ \sqrt 2 (2r)! (1 + O(1/r)), r → ∞.     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

On the error of quadrature formulae for Cauchy principal value integrals based on piecewise interpolation

We consider the computation of the Cauchy principal value integral by quadrature formulae Q _n ^F [f] of compound type, which are obtained by replacing f by a piecewise defined function F_n[f]. The behaviour of the constants k_{i, n} in the estimates [R _n ^F [f]] |⩽K _i,n ‖f ⁽ⁱ⁾‖_∞ (where R _n ^F [f] is the quadrature error) is determined for fixed i and n→∞, which means that not only the order, but also the coefficient of the main term of k_{i, n} is determined. The behaviour of these error constants k_{i, n} is compared with the corresponding ones obtained for the method of subtraction of the singularity. As it turns out, these error constants have, in general, the same asymptotic behaviour.     

Wavelet approximation and Fourier widths of classes of periodic functions of several variables. I

We obtain characterizations (and prove the corresponding equivalence of norms) of function spaces B _pq ^sm ($ \mathbb{I} $ \mathbb{I} ^k ) and L _pq ^sm ($ \mathbb{I} $ \mathbb{I} ^k ) of Nikol’skii-Besov and Lizorkin-Triebel types, respectively, in terms of representations of functions in these spaces by Fourier series with respect to a multiple system $ \mathcal{W}_m^\mathbb{I} $ \mathcal{W}_m^\mathbb{I} of Meyer wavelets and in terms of sequences of the Fourier coefficients with respect to this system. We establish order-sharp estimates for the approximation of functions in B _pq ^sm ($ \mathbb{I} $ \mathbb{I} ) and L _pq ^sm ($ \mathbb{I} $ \mathbb{I} ^k ) by special partial sums of these series in the metric of L _r ($ \mathbb{I} $ \mathbb{I} ^k ) for a number of relations between the parameters s, p, q, r, and m (s = (s ₁, ..., s _n ) ∈ ℝ₊ ⁿ , 1 ≤ p, q, r ≤ ∞, m = (m ₁, ..., m _n ) ∈ ℕ ⁿ , k = m ₁ +... + m _n , and $ \mathbb{I} $ \mathbb{I} = ℝ or $ \mathbb{T} $ \mathbb{T} ). In the periodic case, we study the Fourier widths of these function classes.     

Regularity of solutions of Poisson’s equation in multiplier spaces

The most important result stated in this paper is to show that the solutions of the Poisson equation −Δu = f, where f ∈ (Ḣ¹(ℝ ^d ) → (Ḣ⁻¹(ℝ ^d )) is a complex-valued distribution on ℝ ^d , satisfy the regularity property D ^k u ∈ (Ḣ¹ → Ḣ⁻¹) for all k, |k| = 2. The regularity of this equation is well studied by Maz’ya and Verbitsky [12] in the case where f belongs to the class of positive Borel measures.