Proximal-like contraction methods for monotone variational inequalities in a unified framework I: Effective quadruplet and primary methods

Approximate proximal point algorithms (abbreviated as APPAs) are classical approaches for convex optimization problems and monotone variational inequalities. To solve the subproblems of these algorithms, the projection method takes the iteration in form of u ^k+1=P _Ω [u ^k −α _k d ^k ]. Interestingly, many of them can be paired such that [(u)\tilde]^k = P_\varOmega[u^k - b_kF(v^k)] = P_\varOmega[[(u)\tilde]^k - (d₂^k - G d₁^k)]\tilde{u}^{k} = P_{\varOmega}[u^{k} - \beta_{k}F(v^{k})] = P_{\varOmega}[\tilde {u}^{k} - (d_{2}^{k} - G d_{1}^{k})], where inf {β _k }>0 and G is a symmetric positive definite matrix. In other words, this projection equation offers a pair of directions, i.e., d₁^kd_{1}^{k} and d₂^kd_{2}^{k} for each step. In this paper, for various APPAs we present a unified framework involving the above equations. Unified characterization is investigated for the contraction and convergence properties under the framework. This shows some essential views behind various outlooks. To study and pair various APPAs for different types of variational inequalities, we thus construct the above equations in different expressions according to the framework. Based on our constructed frameworks, it is interesting to see that, by choosing one of the directions (d₁^kd_{1}^{k} and d₂^kd_{2}^{k}) those studied proximal-like methods always utilize the unit step size namely α _k ≡1.     

Geometric realization of Adams maps

Let G/P be a homogenous space with G a compact connected Lie group and P a connected subgroup of G of equal rank. As the rational cohomology ring of G/P is concentrated in even dimensions, for an integer k we can define the Adams map of type k to be l _k : H*(G/P, ℚ) → H*(G/P, ℚ), l _k (u) = k ⁱ u, u ∈ H ²ⁱ (G/P, ℚ). We show that if k is prime to the order of the Weyl group of G, then l _k can be induced by a self map of G/P. We also obtain results which imply the condition that k is prime to the order of the Weyl group of G is necessary.     

An asymptotic approximation of Wallis’ sequence

An asymptotic approximation of Wallis’ sequence W(n) = Π _k=1 ⁿ 4k ²/(4k ² − 1) obtained on the base of Stirling’s factorial formula is presented. As a consequence, several accurate new estimates of Wallis’ ratios w(n) = Π _k=1 ⁿ (2k−1)/(2k) are given. Also, an asymptotic approximation of π in terms of Wallis’ sequence W(n) is obtained, together with several double inequalities such as, for example,

Addendum to “An extension of an inequality of Hoeffding to unbounded random variables”: The non-i.i.d. case

Let S _n = X ₁ + ⋯ + X _n be a sum of independent random variables such that 0 ⩽ X _k ⩽ 1 for all k. Write {ie237-01} and q = 1 − p. Let 0 < t < q. In our recent paper [3], we extended the inequality of Hoeffding ([6], Theorem 1) {fx237-01} to the case where X _k are unbounded positive random variables. It was assumed that the means {ie237-02} of individual summands are known. In this addendum, we prove that the inequality still holds if only an upper bound for the mean {ie237-03} is known and that the i.i.d. case where {ie237-04} dominates the general non-i.i.d. case. Furthermore, we provide upper bounds expressed in terms of certain compound Poisson distributions. Such bounds can be more convenient in applications. Our inequalities reduce to the related Hoeffding inequalities if 0 ⩽ X _k ⩽ 1. Our conditions are X _k ⩾ 0 and {ie237-05}. In particular, X _k can have fat tails. We provide as well improvements comparable with the inequalities in Bentkus [2]. The independence of X _k can be replaced by super-martingale type assumptions. Our methods can be extended to prove counterparts of other inequalities in Hoeffding [6] and Bentkus The research was partially supported by the Lithuanian State Science and Studies Foundation, grant No T-25/08.     

An optimal version of an inequality involving the third symmetric means

Let (GA) _n ^[k](a), A _n (a), G _n (a) be the third symmetric mean of k degree, the arithmetic and geometric means of a ₁, …, a _n (a _i > 0, i = 1, …, n), respectively. By means of descending dimension method, we prove that the maximum of p is k−1/n−1 and the minimum of q is n/n−1(k−1/k) ^k/n so that the inequalities {fx505-1} hold.     

An infeasible-interior-point potential-reduction algorithm for linear programming

n . The method is based on Rockafellar’s proximal point algorithm and a cutting-plane technique. At each step, we use an approximate proximal point p^a(x_k) of x_k to define a v_k∈∂_εkf(p^a(x_k)) with ε_k≤α∥v_k∥, where α is a constant. The method monitors the reduction in the value of ∥v_k∥ to identify when a line search on f should be used. The quasi-Newton step is used to reduce the value of ∥v_k∥. Without the differentiability of f, the method converges globally and the rate of convergence is Q-linear. Superlinear convergence is also discussed to extend the characterization result of Dennis and Moré. Numerical results show the good performance of the method. Received October 3, 1995 / Revised version received August 20, 1998 Published online January 20, 1999     

The intersection of subgroups of finite <Emphasis Type="Italic">p</Emphasis>-groups

For a finite p-group G and a positive integer k let I _k (G) denote the intersection of all subgroups of G of order p ^k . This paper classifies the finite p-groups G with I_k(G) @ C_p^k-1{{I}_k(G)\cong C_{p^{k-1}}} for primes p > 2. We also show that for any k, α ≥ 0 with 2(α + 1) ≤ k ≤ n−α the groups G of order p ⁿ with I_k(G) @ C_p^k-a{{I}_k(G)\cong C_{p^{k-\alpha}}} are exactly the groups of exponent p ^n-α .     

General Hardy’s inequalities for functions nonzero on the boundary

Consider Hardy’s inequalities with general weight ϕ for functions nonzero on the boundary. By an integral identity in C ¹( ), define Hilbert spaces H _k ¹ (Ω, ϕ) called Sobolev-Hardy spaces with weight ϕ. As a corollary of this identity, Hardy’s inequalities with weight ϕ in C ¹ ( ) follow. At last, by Hardy’s inequalities with weight ϕ = 1, discuss the eigenvalue problem of the Laplace-Hardy operator with critical parameter (N − 2)²/4 in H ¹ ₁ (Ω).      

Univalent functions without common values

In this paper we establish inequalities involving moduli of derivatives |f′ _k (0)| of functions f _k univalent in the unit disk |z| < 1 having no common values and translating zero into a point on the segment [−1, 1], k = 1, …, n. We estimate f _k by means of Schwarzian derivatives.     

Projective bases of division algebras and groups of central type

Letk be a field. For each finite groupG and two-cocylef inZ ² (G, k ^x ) (with trivial action), one can form the twisted group algebra wherex _σ x _τ =f(σ,τ)x _στ for all σ, τ∃G. Our main result is a short list ofp-groups containing all thep-groupsG for which there is a fieldk and a cocycle such that the resulting twisted group algebra is ak-central division algebra. We also complete the proof (presented in all but one case in a previous paper by Aljadeff and Haile) that everyk-central division algebra that is a twisted group algebra is isomorphic to a tensor product of cyclic algebras.     

Division algebras with a projective basis

Letk be any field andG a finite group. Given a cohomology class α∈H ²(G,k ^*), whereG acts trivially onk ^*, one constructs the twisted group algebrak ^αG. Unlike the group algebrakG, the twisted group algebra may be a division algebra (e.g. symbol algebras, whereG⋞Z _n×Z_n). This paper has two main results: First we prove that ifD=k ^α G is a division algebra central overk (equivalentyD has a projectivek-basis) thenG is nilpotent andG’ the commutator subgroup ofG, is cyclic. Next we show that unless char(k)=0 and , the division algebraD=k ^α G is a product of cyclic algebras. Furthermore, ifD _p is ap-primary factor ofD, thenD _p is a product of cyclic algebras where all but possibly one are symbol algebras. If char(k)=0 and , the same result holds forD _p, p odd. Ifp=2 we show thatD ₂ is a product of quaternion algebras with (possibly) a crossed product algebra (L/k,β), Gal(L/k)⋞Z ₂×Z₂n.     

Schur multiplier characterization of a class of infinite matrices

Let B _w (ℓ ^p ) denote the space of infinite matrices A for which A(x) ∈ ℓ ^p for all x = {x _k } _k=1^∞ ∈ ℓ ^p with |x _k | ↘ 0. We characterize the upper triangular positive matrices from B _w (ℓ ^p ), 1 < p < ∞, by using a special kind of Schur multipliers and the G. Bennett factorization technique. Also some related results are stated and discussed.     

Extension of smooth functions from finitely connected planar domains

Consider the Sobolev space W _∞ ^k (Ω) of functions with bounded kth derivatives defined in a planar domain. We study the problem of extendability of functions from W _∞ ^k (Ω) to the whole ℝ² with preservation of class, i.e., surjectivity of the restriction operator W _∞ ^k (ℝ²) → W _∞ ^k (Ω).     

Grunsky inequalities and quasiconformal extension

The Grunsky coefficient inequalities play a crucial role in various problems and are intrinsically connected with the integrable holomorphic quadratic differentials having only zeros of even order. For the functions with quasi-conformal extensions, the Grunsky constant ℵ(f) and the extremal dilatationk(f) are related by ℵ(f)≤k(f). In 1985, Jürgen Moser conjectured that any univalent functionf(z)=z+b ₀+b ₁ z ⁻¹+… on Δ*={|z|>1} can be approximated locally uniformly by functions with ℵ(f)<k(f). In this paper, we prove a theorem confirming Moser’s conjecture, which sheds new light on the features of Grunsky coefficients. In memory of Jürgen Moser The research was supported by the RiP program of the Volkswagen-Stiftung in the Mathematisches Forschungsinstitut Oberwolfach.     

Restricted 2-factor polytopes

The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K _n , a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing. Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999     

Reality properties of conjugacy classes in<Emphasis Type="Italic">G</Emphasis><Subscript>2</Subscript>

LetG be an algebraic group over a fieldk. We callg εG(k) real ifg is conjugate tog ⁻¹ inG(k). In this paper we study reality for groups of typeG ₂ over fields of characteristic different from 2. LetG be such a group overk. We discuss reality for both semisimple and unipotent elements. We show that a semisimple element inG(k) is real if and only if it is a product of two involutions inG(k). Every unipotent element inG(k) is a product of two involutions inG(k). We discuss reality forG ₂ over special fields and construct examples to show that reality fails for semisimple elements inG ₂ over ℚ and ℚ_p. We show that semisimple elements are real forG ₂ overk withcd(k) ≤ 1. We conclude with examples of nonreal elements inG ₂ overk finite, with characteristick not 2 or 3, which are not semisimple or unipotent.     

A Markov-Nikolskii type inequality for absolutely monotone polynomials of order <Emphasis Type="Italic">K</Emphasis>

A function Q is called absolutely monotone of order k on an interval I if Q(x) ≥ 0, Q′(x) ≥ 0, …, Q(k)(x) ≥ 0, for all x ε I. An essentially sharp (up to a multiplicative absolute constant) Markov inequality for absolutely monotone polynomials of order k in L _p [−1, 1], p > 0, is established. One may guess that the right Markov factor is cn ²/k, and this indeed turns out to be the case. Similarly sharp results hold in the case of higher derivatives and Markov-Nikolskii type inequalities. There is also a remarkable connection between the right Markov inequality for absolutely monotone polynomials of order k in the supremum norm and essentially sharp bounds for the largest and smallest zeros of Jacobi polynomials. This is discussed in the last section of the paper.     

On J. H. C. Whitehead's aspherical question I

A connected, finite two-dimensional CW-complex with fundamental group isomorphic toG is called a [G, 2] _f -complex. LetL⊲G be a normal subgroup ofG. L has weightk if and only ifk is the smallest integer such that there exists {l ₁,…,l _k}⊆L such thatL is the normal closure inG of {l ₁,…,l _k}. We prove that a [G, 2] _f -complexX may be embedded as a subcomplex of an aspherical complexY=X∪{e ₁ ² ,…,e _k ² } if and only ifG has a normal subgroupL of weightk such thatH=G/L is at most two-dimensional and defG=defH+k. Also, ifX is anon-aspherical [G, 2] _f -subcomplex of an aspherical 2-complex, then there exists a non-trivial superperfect normal subgroupP such thatG/P has cohomological dimension ≤2. In this case, any torsion inG must be inP.     

S-forcing,I. A “black-box” theorem for morasses,with applications to super-Souslin trees

We formulate, for regular μ>ω, a “forcing principle” S_μ which we show is equivalent to the existence of morasses, thus providing a new and systematic method for obtaining applications of morasses. Various examples are given, notably that for infinitek, if 2 ^k =k ⁺ and there exists a (k ⁺, 1)-morass, then there exists ak ⁺⁺-super-Souslin tree: a normalk ⁺⁺ tree characterized by a highly absolute “positive” property, and which has ak ⁺⁺-Souslin subtree. As a consequence we show that CH+SH_{ℵ 2}⟹ℵ₂ is (inaccessible)^L. This author thanks the US-Israel Binational Science Foundation for partial support of this research.     

Nonvanishing derivatives and normal families

We consider the differential operators Ψ _k , defined by Ψ₁(y) =y and Ψ _k+1(y)=yΨ _k y+d/dz(Ψ _k (y)) fork ∈ ℕ fork∈ ℕ. We show that ifF is meromorphic in ℂ and Ψ _k F has no zeros for somek≥3, and if the residues at the simple poles ofF are not positive integers, thenF has the formF(z)=((k-1)z+a)/(z ²+β z+γ) orF(z)=1/(az+β) where α, β, γ ∈ ℂ. If the residues at the simple poles ofF are bounded away from zero, then this also holds fork=2. We further show that, under suitable additional conditions, a family of meromorphic functionsF is normal if each Ψ _k (F) has no zeros. These conditions are satisfied, in particular, if there exists δ>0 such that Re (Res(F, a)) <−δ for all polea of eachF in the family. Using the fact that Ψ _k (f ^′/f) =f ^(k)/f, we deduce in particular that iff andf ^(k) have no zeros for allf in some familyF of meromorphic functions, wherek≥2, then {f ^′/f :f ∈F} is normal. The first author is supported by the German-Israeli Foundation for Scientific Research and Development G.I.F., G-643-117.6/1999, and INTAS-99-00089. The second author thanks the DAAD for supporting a visit to Kiel in June–July 2002. Both authors thank Günter Frank for helpful discussions.