Further PDE methods for weak KAM theory

We introduce and make estimates for several new approximations that in appropriate asymptotic limits yield the key PDE for weak KAM theory, namely a Hamilton–Jacobi type equation for a potential u and a coupled transport equation for a measure σ. We revisit as well a singular variational approximation introduced in Evans (Calc Vari Partial Differ Equ 17:159–177, 2003) and demonstrate “approximate integrability” of certain phase space dynamics related to the Hamiltonian flow. Other examples include a pair of strongly coupled PDE suggested by the Lions–Lasry theory (Lasry and Lions in Japan J Math 2:229–260, 2007) of mean field games and a new and extremely singular elliptic equation suggested by sup-norm variational theory. Supported in part by NSF Grant DMS-0500452.     

Estimates for weighted eigenvalues of a fourth-order elliptic operator with variable coefficients

We investigate the Dirichlet weighted eigenvalue problem for a fourth-order elliptic operator with variable coefficients in a bounded domain in \mathbbRⁿ {\mathbb{R}^n} . We establish a sharp inequality for its eigenvalues. It yields an estimate for the upper bound of the (k + 1)th eigenvalue in terms of the first k eigenvalues. Moreover, we also obtain estimates for some special cases of this problem. In particular, our results generalize the Wang–Xia inequality (J. Funct. Anal., 245, No. 1, 334–352 (2007)) for the clamped-plate problem to a fourth-order elliptic operator with variable coefficients.     

Single-point condensation phenomena for a four-dimensional biharmonic Ren–Wei problem

We continue to study the asymptotic behavior of least energy solutions to the following fourth order elliptic problem (E _p ): as p gets large, where Ω is a smooth bounded domain in R ⁴ . In our earlier paper (Takahashi in Osaka J. Math., 2006), we have shown that the least energy solutions remain bounded uniformly in p and they have one or two “peaks” away form the boundary. In this note, following the arguments in Adimurthi and Grossi (Proc. AMS 132(4):1013–1019, 2003) and Lin and Wei (Comm. Pure Appl. Math. 56:784–809, 2003), we will obtain more sharper estimates of the upper bound of the least energy solutions and prove that the least energy solutions must develop single-point spiky pattern, under the assumption that the domain is convex.     

The optimal convergence of the h–p version of the boundary element method with quasiuniform meshes for elliptic problems on polygonal domains

In the framework of the Jacobi-weighted Besov spaces, we analyze the lower and upper bounds of errors in the h–p version of boundary element solutions on quasiuniform meshes for elliptic problems on polygons. Both lower bound and upper bound are optimal in h and p, and they are of the same order. The optimal convergence of the h–p version of boundary element method with quasiuniform meshes is proved, which includes the optimal rates for h version with quasiuniform meshes and the p version with quasiuniform degrees as two special cases. Dedicated to Professor Charles Micchelli on the occasion of his sixtieth birthday Mathematics subject classification (2000) 65N38. Benqi Guo: The work of this author was supported by NSERC of Canada under Grant OGP0046726 and was complete during visiting Newton Institute for Mathematical Sciences, Cambridge University for participating in special program “Computational Challenges in PDEs” in 2003. Norbert Heuer: This author is supported by Fondecyt project No. 1010220 and by the FONDAP Program (Chile) on Numerical Analysis. Current address: Mathematical Sciences, Brunel University, Uxbridge, U.K.     

Backward SDEs and Cauchy problem for semilinear equations in divergence form

 We extend the definition of solutions of backward stochastic differential equations to the case where the driving process is a diffusion corresponding to symmetric uniformly elliptic divergence form operator. We show existence and uniqueness of solutions of such equations under natural assumptions on the data and show its connections with solutions of semilinear parabolic partial differential equations in Sobolev spaces. Received: 22 January 2002 / Revised version: 10 September 2002 / Published online: 19 December 2002 Research supported by KBN Grant 0253 P03 2000 19. Mathematics Subject Classification (2002): Primary 60H30; Secondary 35K55 Key words or phrases: Backward stochastic differential equation – Semilinear partial differential equation – Divergence form operator – Weak solution     

A simpler characterization of a spectral lower bound on the clique number

Given a simple, undirected graph G, Budinich (Discret Appl Math 127:535–543, 2003) proposed a lower bound on the clique number of G by combining the quadratic programming formulation of the clique number due to Motzkin and Straus (Can J Math 17:533–540, 1965) with the spectral decomposition of the adjacency matrix of G. This lower bound improves the previously known spectral lower bounds on the clique number that rely on the Motzkin–Straus formulation. In this paper, we give a simpler, alternative characterization of this lower bound. For regular graphs, this simpler characterization allows us to obtain a simple, closed-form expression of this lower bound as a function of the positive eigenvalues of the adjacency matrix. Our computational results shed light on the quality of this lower bound in comparison with the other spectral lower bounds on the clique number.     

Marino—Prodi perturbation type results and Morse indices of minimax critical points for a class of functionals in Banach spaces

In this work, we study a class of Euler functionals defined in Banach spaces, associated with quasilinear elliptic problems involving p-Laplace operator (p > 2). First we obtain perturbation results in the spirit of the remarkable paper by Marino and Prodi (Boll. U.M.I. (4) 11(Suppl. fasc. 3): 1–32, 1975), using the new definition of nondegeneracy given in (Ann. Inst. H. Poincaré: Analyse Non Linéaire. 2:271–292, 2003). We also extend Morse index estimates for minimax critical points, introduced by Lazer and Solimini (Nonlinear Anal. T.M.A. 12:761–775, 1988) in the Hilbert case, to our Banach setting. Mathematics Subject Classification (1991) 58E05, 35B20, 35J60, 35J70     

A posteriori error estimates for mixed finite element approximations of parabolic problems

We derive residual based a posteriori error estimates for parabolic problems on mixed form solved using Raviart–Thomas–Nedelec finite elements in space and backward Euler in time. The error norm considered is the flux part of the energy, i.e. weighted L ²(Ω) norm integrated over time. In order to get an optimal order bound, an elementwise computable post-processed approximation of the scalar variable needs to be used. This is a common technique used for elliptic problems. The final bound consists of terms, capturing the spatial discretization error and the time discretization error and can be used to drive an adaptive algorithm.     

The heterogeneous multiscale finite element method for elliptic homogenization problems in perforated domains

In this contribution we analyze a generalization of the heterogeneous multiscale finite element method for elliptic homogenization problems in perforated domains. The method was originally introduced by E and Engquist (Commun Math Sci 1(1):87–132, 2003) for homogenization problems in fixed domains. It is based on a standard finite element approach on the macroscale, where the stiffness matrix is computed by solving local cell problems on the microscale. A-posteriori error estimates are derived in L ²(Ω) by reformulating the problem into a discrete two-scale formulation (see also, Ohlberger in Multiscale Model Simul 4(1):88–114, 2005) and using duality methods afterwards. Numerical experiments are given in order to numerically evaluate the efficiency of the error estimate.     

Boundary estimates for elliptic systems with L<Superscript>1</Superscript>–data

We obtain boundary estimates for the gradient of solutions to elliptic systems with Dirichlet or Neumann boundary conditions and L ¹–data, under some condition on the divergence of the data. Similar boundary estimates are obtained for div–curl and Hodge systems.     

Convergence rate analysis of iteractive algorithms for solving variational inequality problems

 We present a unified convergence rate analysis of iterative methods for solving the variational inequality problem. Our results are based on certain error bounds; they subsume and extend the linear and sublinear rates of convergence established in several previous studies. We also derive a new error bound for $\gamma$-strictly monotone variational inequalities. The class of algorithms covered by our analysis in fairly broad. It includes some classical methods for variational inequalities, e.g., the extragradient, matrix splitting, and proximal point methods. For these methods, our analysis gives estimates not only for linear convergence (which had been studied extensively), but also sublinear, depending on the properties of the solution. In addition, our framework includes a number of algorithms to which previous studies are not applicable, such as the infeasible projection methods, a separation-projection method, (inexact) hybrid proximal point methods, and some splitting techniques. Finally, our analysis covers certain feasible descent methods of optimization, for which similar convergence rate estimates have been recently obtained by Luo [14]. Received: April 17, 2001 / Accepted: December 10, 2002 Published online: April 10, 2003 RID="⋆" ID="⋆" Research of the author is partially supported by CNPq Grant 200734/95–6, by PRONEX-Optimization, and by FAPERJ. Key Words. Variational inequality – error bound – rate of convergence Mathematics Subject Classification (2000): 90C30, 90C33, 65K05     

Universal bounds on the selfaveraging of random diffraction measures

 We consider diffraction at random point scatterers on general discrete point sets in ℝ^ν, restricted to a finite volume. We allow for random amplitudes and random dislocations of the scatterers. We investigate the speed of convergence of the random scattering measures applied to an observable towards its mean, when the finite volume tends to infinity. We give an explicit universal large deviation upper bound that is exponential in the number of scatterers. The rate is given in terms of a universal function that depends on the point set only through the minimal distance between points, and on the observable only through a suitable Sobolev-norm. Our proof uses a cluster expansion and also provides a central limit theorem. Received: 10 October 2001 / Revised version: 26 January 2003 / Published online: 15 April 2003 Work supported by the DFG Mathematics Subject Classification (2000): 78A45, 82B44, 60F10, 82B20 Key words or phrases: Diffraction theory – Random scatterers – Random point sets – Quasicrystals – Large deviations – Cluster expansions     

Smoothed analysis of termination of linear programming algorithms

 We perform a smoothed analysis of a termination phase for linear programming algorithms. By combining this analysis with the smoothed analysis of Renegar's condition number by Dunagan, Spielman and Teng (http://arxiv.org/abs/cs.DS/0302011) we show that the smoothed complexity of interior-point algorithms for linear programming is O(m ³ log(m/Σ)). In contrast, the best known bound on the worst-case complexity of linear programming is O(m ³ L), where L could be as large as m. We include an introduction to smoothed analysis and a tutorial on proof techniques that have been useful in smoothed analyses. Received: December 10, 2002 / Accepted: April 28, 2003 Published online: June 5, 2003 Key words. smoothed analysis – linear programming – interior-point algorithms – condition numbers Mathematics Subject Classification (1991): 90C05, 90C51, 68Q25     

Maximum principle for fully nonlinear equations via the iterated comparison function method

We present various versions of generalized Aleksandrov–Bakelman–Pucci (ABP) maximum principle for L ^p -viscosity solutions of fully nonlinear second-order elliptic and parabolic equations with possibly superlinear-growth gradient terms and unbounded coefficients. We derive the results via the “iterated” comparison function method, which was introduced in our previous paper (Koike and Święch in Nonlin. Diff. Eq. Appl. 11, 491–509, 2004) for fully nonlinear elliptic equations. Our results extend those of (Koike and Święch in Nonlin. Diff. Eq. Appl. 11, 491–509, 2004) and (Fok in Comm. Partial Diff. Eq. 23(5–6), 967–983) in the elliptic case, and of (Crandall et al. in Indiana Univ. Math. J. 47(4), 1293–1326, 1998; Comm. Partial Diff. Eq. 25, 1997–2053, 2000; Wang in Comm. Pure Appl. Math. 45, 27–76, 1992) and (Crandall and Święch in Lecture Notes in Pure and Applied Mathematics, vol. 234. Dekker, New York, 2003) in the parabolic case. Dedicated to Hitoshi Ishii on the occasion of his 60th birthday.     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

Adaptive estimation of the intensity of inhomogeneous Poisson processes via concentration inequalities

 In this paper, we establish oracle inequalities for penalized projection estimators of the intensity of an inhomogeneous Poisson process. We study consequently the adaptive properties of penalized projection estimators. At first we provide lower bounds for the minimax risk over various sets of smoothness for the intensity and then we prove that our estimators achieve these lower bounds up to some constants. The crucial tools to obtain the oracle inequalities are new concentration inequalities for suprema of integral functionals of Poisson processes which are analogous to Talagrand's inequalities for empirical processes. Received: 24 April 2001 / Revised version: 9 October 2002 / Published online: 15 April 2003 Mathematics Subject Classification (2000): 60E15, 62G05, 62G07 Key words or phrases: Inhomogeneous Poisson process – Concentration inequalities – Model selection – Penalized projection estimator – Adaptive estimation     

Optimization in forestry

 Optimization models and methods have been used extensively in the forest industry. In this paper we describe the general wood-flow in forestry and a variety of planning problems. These cover planning periods from a fraction of a second to more than one hundred years. The problems are modelled using linear, integer and nonlinear models. Solution methods used depend on the required solution time and include for example dynamic programming, LP methods, branch & bound methods, heuristics and column generation. The importance of modelling and qualitative information is also discussed. Received: January 15, 2003 / Accepted: April 24, 2003 Published online: May 28, 2003 Key words. Forestry – modelling – routing – transportation – production planning Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Exponential estimate for reaction diffusion models

Summary. We consider the superposition of a speeded up symmetric simple exclusion process with a Glauber dynamics, which leads to a reaction diffusion equation. Using a method introduced in [Y] based on the study of the time evolution of the H ₋₁ norm, we prove that the mean density of particles on microscopic boxes of size N ^α , for any 12/13<α<1, converges to the solution of the hydrodynamic equation for times up to exponential order in N, provided the initial state is in the basin of attraction of some stable equilibrium of the reaction–diffusion equation. From this result we obtain a lower bound for the escape time of a domain in the basin of attraction of the stable equilibrium point. Received: 3 March 1995 / In revised form: 2 February 1996     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee