Dual extrapolation and its applications to solving variational inequalities and related problems

In this paper we suggest new dual methods for solving variational inequalities with monotone operators. We show that with an appropriate step-size strategy, our method is optimal both for Lipschitz continuous operators ( $O({1 \over \epsilon})In this paper we suggest new dual methods for solving variational inequalities with monotone operators. We show that with an appropriate step-size strategy, our method is optimal both for Lipschitz continuous operators ( iterations), and for the operators with bounded variations ( iterations). Our technique can be applied for solving non-smooth convex minimization problems with known structure. In this case the worst-case complexity bound is iterations. The research results presented in this paper have been supported by a grant “Action de recherche concertè ARC 04/09-315” from the “Direction de la recherche scientifique, Communautè fran?aise de Belgique”. The scientific responsibility rests with its author(s).     

Local smoothing for operators failing the cinematic curvature condition

In this paper, we examine a class of averaging operators which exhibit local smoothing. That is, viewed as a function of space and time variables, the operators yield more smoothing than the fixed-time estimates. Sogge showed in a more general setting that if these operators satisfy a cinematic curvature condition, they will exhibit some local smoothing [C.D. Sogge, Propagation of singularities and maximal functions in the plane, Invent. Math. 104 (1991) 231-251]. Here we translate this condition into the setting of averaging operators in the plane. We prove that cinematic curvature is not necessary for local smoothing to occur, exhibiting a class of operators which fail the cinematic curvature condition but still satisfy a local smoothing estimate. Furthermore, the amount of local smoothing exhibited by these operators is strictly less than that conjectured for operators satisfying the cinematic curvature condition.     

On rubin's harmonic analysis and its related positive definite functions

In this paper, a new formulation of the Rubin's q-translation is given, which leads to a reliable q-harmonic analysis. Next, related q-positive definite functions are introduced and studied, and a Bochner's theorem is proved.     

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield-optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543.     

On a variational problem for radial solutions to extremal elliptic equations

On the ball |x| ≤ 1 of R ^m , m ≥ 2, a radial variational problem, related to a priori estimates for solutions to extremal elliptic equations with fixed ellipticity constant α is investigated. Such a problem has been studied and solved [see Manselli Ann. Mat. Pura Appl. (IV), t. LXXXIX:31–54, 1971] in L ^p spaces, with p ≤ m. In this paper, we assume p > m and we prove the existence of a positive number α ₀ = α ₀(p,m) such that if there exists a smooth function maximizing the problem, whose representation is explicitly determined as in Manselli [Ann. Mat. Pura Appl. (IV), t. LXXXIX:31–54, 1971] This fact is no longer true if 0 < α < α ₀.      

Partial regularity for harmonic maps and related problems

Via gauge theory, we give a new proof of partial regularity for harmonic maps in dimensions m ≥ 3 into arbitrary targets. This proof avoids the use of adapted frames and permits us to consider targets of “minimal” C²‐regularity. The proof we present extends to a large class of elliptic systems. © 2007 Wiley Periodicals, Inc.     

On two problems related to cancellativity

Two decision problems that are related to the properties of right-cancellativity and left-cancellativity, respectively, of the monoidm _T defined by a presentation (Σ;T), are investigated. It is shown that these problems are undecidable in general. In fact, they remain undecidable, even when they are restricted to presentations involving finite Church-Rosser Thue systems. On the other hand, if only finite presentations involving monadic Church-Rosser Thue systems are considered, then these two problems become decidable in polynomial space.     

Compact formulations of the Steiner Traveling Salesman Problem and related problems

The Steiner Traveling Salesman Problem (STSP) is a variant of the TSP that is particularly suitable when routing on real-life road networks. The standard integer programming formulations of both the TSP and STSP have an exponential number of constraints. On the other hand, several compact formulations of the TSP, i.e., formulations of polynomial size, are known. In this paper, we adapt some of them to the STSP, and compare them both theoretically and computationally. It turns out that, just by putting the best of the formulations into the CPLEX branch-and-bound solver, one can solve instances with over 200 nodes. We also briefly discuss the adaptation of our formulations to some related problems.     

Some approximation problems in harmonic analysis

Milan Journal of Mathematics - We consider the question of when certain Banach algebras on the circle group or the integers, which themselves are the closed span of their idempotents, have closed...     

On some problems related to Berezin symbols

The following problem was formulated by Zorboska [Proc. Amer. Math. Soc. 131 (2003) 793–800]: It is not known if the Berezin symbols of a bounded operator on the Bergman space $L_a^2(\mathbf{D})$ must have radial limits almost everywhere on the unit circle. In this Note we solve this problem in the negative, showing that there is a concrete class of diagonal operators for which the Berezin symbol does not have radial boundary values anywhere on the unit circle. A similar result is also obtained in case of the Hardy space $H^2(\mathbf{D})$ over the unit disk D. Moreover, we give an alternative proof to the famous theorem of Beurling on z-invariant subspaces in the Hardy space $H^2(\mathbf{D})$, using the concepts of reproducing kernels and Berezin symbols. To cite this article: M.T. Karaev, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Quadratic programming problems and related linear complementarity problems

This paper investigates the general quadratic programming problem, i.e., the problem of finding the minimum of a quadratic function subject to linear constraints. In the case where, over the set of feasible points, the objective function is bounded from below, this problem can be solved by the minimization of a linear function, subject to the solution set of a linear complementarity problem, representing the Kuhn-Tucker conditions of the quadratic problem.To detect in the quadratic problem the unboundedness from below of the objective function, necessary and sufficient conditions are derived. It is shown that, when these conditions are applied, the general quadratic programming problem becomes equivalent to the investigation of an appropriately formulated linear complementarity problem.This research was supported by the Hungarian Research Foundation, Grant No. OTKA/1044.     

Solvability conditions and monotone iterative scheme for boundary-value problems related to nonlinear monotone potential operators

This article deals with boundary-value problems (BVPs) for the second-order nonlinear differential equations with monotone potential operators of type Au := ??(k(|?u|²)?u(x)) + q(u ²)u(x), x ∈ Ω ? R ⁿ . An analysis of nonlinear problems shows that the potential of the operator A as well as the potential of related BVP plays an important role not only for solvability of these problems and linearization of the nonlinear operator, but also for the strong convergence of solutions of corresponding linearized problems. A monotone iterative scheme for the considered BVP is proposed.     

On Berry-Esseen bounds of summability transforms

Let , , , be a collection of random variables, where for each , , , are independent. Let be a regular summability method. We provide some rates of convergence (Berry-Esseen type bounds) for the weak convergence of summability transform . We show that when is the classical Cesáro summability method, the rate of convergence of the resulting central limit theorem is best possible among all regular triangular summability methods with rows adding up to one. We further provide some summability results concerning -negligibility. An application of these results characterizes the rate of convergence of Schnabl operators while approximating Lipschitz continuous functions.

     

On planar harmonic grid generation

It has been shown that the harmonic map is a diffeomorphism. In some cases, numerical solutions to the equation have been noticed to produce folded grids, however. The folding of the grid is due to truncation error and not an incorrect theorem as has been suggested earlier. Difference approximations are constructed that solve the problem. The difference approximations can be of low order, which shows that the order of the difference approximations is not the key factor. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 305–315, 1999     

On the double commutation method

We provide a complete spectral characterization of the double commutation method for general Sturm-Liouville operators which inserts any finite number of prescribed eigenvalues into spectral gaps of a given background operator. Moreover, we explicitly determine the transformation operator which links the background operator to its doubly commuted version (resulting in extensions and considerably simplified proofs of spectral results even for the special case of Schrödinger-type operators).

     

A new logarithmic-quadratic proximal method for nonlinear complementarity problems

In this paper, we propose a new modified logarithmic-quadratic proximal (LQP) method for solving nonlinear complementarity problems (NCP). We suggest using a prediction-correction method to solve NCP. The predictor is obtained via solving the LQP system approximately under significantly relaxed accuracy criterion and the new iterate is computed by using a new step size α_k. Under suitable conditions, we prove that the new method is globally convergent. We report preliminary computational results to illustrate the efficiency of the proposed method. This new method can be considered as a significant refinement of the previously known methods for solving nonlinear complementarity problems.     

Operators of harmonic analysis in weighted spaces with non-standard growth

Last years there was increasing an interest to the so-called function spaces with non-standard growth, known also as variable exponent Lebesgue spaces. For weighted such spaces on homogeneous spaces, we develop a certain variant of Rubio de Francia's extrapolation theorem. This extrapolation theorem is applied to obtain the boundedness in such spaces of various operators of harmonic analysis, such as maximal and singular operators, potential operators, Fourier multipliers, dominants of partial sums of trigonometric Fourier series and others, in weighted Lebesgue spaces with variable exponent. There are also given their vector-valued analogues.