On the convergence of general regularization and smoothing schemes for mathematical programs with complementarity constraints

We extend the convergence analysis of a smoothing method [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg.] to a general class of smoothing functions and show that a weak second-order necessary optimality condition holds at the limit point of a sequence of stationary points found by the smoothing method. We also show that convergence and stability results in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] hold for a relaxation problem suggested by Scholtes [S. Scholtes (2003). Private communications.] using a class of smoothing functions. In addition, the relationship between two technical, yet critical, concepts in [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg; S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] for the convergence analysis of the smoothing and regularization methods is discussed and a counter-example is provided to show that the stability result in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] cannot be extended to a weaker regularization.     

Smolyak cubature of given polynomial degree with few nodes for increasing dimension

Summary. Some recent investigations (see e.g., Gerstner and Griebel [5], Novak and Ritter [9] and [10], Novak, Ritter and Steinbauer [11], Wasilkowski and Woźniakowski [18] or Petras [13]) show that the so-called Smolyak algorithm applied to a cubature problem on the d-dimensional cube seems to be particularly useful for smooth integrands. The problem is still that the numbers of nodes grow (polynomially but) fast for increasing dimensions. We therefore investigate how to obtain Smolyak cubature formulae with a given degree of polynomial exactness and the asymptotically minimal number of nodes for increasing dimension d and obtain their characterization for a subset of Smolyak formulae. Error bounds and numerical examples show their good behaviour for smooth integrands. A modification can be applied successfully to problems of mathematical finance as indicated by a further numerical example. Received September 24, 2001 / Revised version received January 24, 2002 / Published online April 17, 2002 RID="*" ID="*" The author is supported by a Heisenberg scholarship of the Deutsche Forschungsgemeinschaft     

A counterexample to a 1961 “theorem” in homological algebra

In 1961, Jan-Erik Roos published a “theorem”, which says that in an [AB4^*] abelian category, lim¹ vanishes on Mittag–Leffler sequences. See Propositions 1 and 5 in [4]. This is a “theorem” that many people since have known and used. In this article, we outline a counterexample. We construct some strange abelian categories, which are perhaps of some independent interest.?These abelian categories come up naturally in the study of triangulated categories. A much fuller discussion may be found in [3]. Here we provide a brief, self contained, non–technical account. The idea is to make the counterexample easy to read for all the people who have used the result in their work.?In the appendix, Deligne gives another way to look at the counterexample. Oblatum 22-I-2001 & 15-XII-2001?Published online: 1 February 2002     

A Class of Hamilton—Jacobi Equations with Unbounded Coefficients in Hilbert Spaces

We establish existence and comparison theorems for a class of Hamilton—Jacobi equations. The class of Hamilton—Jacobi equations includes and is broader than those studied in [8] We apply the existence and uniqueness results to characterizing the value functions associated with the optimal control of systems governed by partial differential equations of parabolic type. Accepted 11 May 2001. Online publication 5 October 2001.     

Enclosure theorems for generalized mean curvature flows

We define a generalized notion of mean curvature for regular hypersurfaces in . This enables us to introduce a new class of geometric curvature flows for which we prove enclosure theorems, using methods of Dierkes [D] and Hildebrandt [H]. In particular, we obtain “neck-pinching” results that generalize previous observations by Ecker [E] concerning the classical mean curvature flow. Received: 8 October 2001 / Accepted: 1 March 2002 / Published online: 23 May 2002     

Contraction-free sequent calculi for geometric theories with an application to Barr's theorem

 Geometric theories are presented as contraction- and cut-free systems of sequent calculi with mathematical rules following a prescribed rule-scheme that extends the scheme given in Negri and von Plato (1998). Examples include cut-free calculi for Robinson arithmetic and real closed fields. As an immediate consequence of cut elimination, it is shown that if a geometric implication is classically derivable from a geometric theory then it is intuitionistically derivable. Received: 18 April 2001 / Published online: 10 October 2002 Mathematics Subject Classification (2000): 03F05, 18C10, 18B15 Key words or phrases: Cut elimination – Geometric theories – Barr's theorem     

On the Characterization of Preinvex Functions

In Refs. [J. Math. Anal. Appl. 258:287–308, [2001]; J. Math. Anal. Appl. 256:229–241, [2001]], Yang and Li presented a characterization of preinvex functions and semistrictly preinvex functions under a certain set of conditions. In this note, we show that the same results or even more general ones can be obtained under weaker assumptions; we also give a characterization of strictly preinvex functions under mild conditions. This research was supported by the National Natural Science Foundation of China under Grants 70671064 and 60673177, and the Education Department Foundation of Zhejiang Province Grant 20070306. The authors thank Professor F. Giannessi for valuable comments on the original version of this paper.     

Itô's formula for C 1,λ -functions of a càdlàg process and related calculus

 This article develops a framework of stochastic calculus with respect to a càdlàg finite quadratic variation process. We apply it to the study of a generalization of a semimartingale driven SDE studied by Kurtz, Pardoux and Protter [KPP]. We prove an It?'s formula for functions f(X) of a semimartingale with jumps when f has weak smoothness properties. Examples of X for which this formula is valid are time reversible semimartingales and solutions of [KPP] equations driven by Lévy processes, provided the sum of the absolute values of the jumps, raised to the power 1 + λ, is a.s. finite, where λ takes values between 0 and 1. Received: 1 March 1999 / Revised version: 15 April 2001 / Published online: 11 December 2001     

Mean field bounds on Lyapunov exponents in Z d at the critical energy

We further develop the supersymmetric formalism initiated in [W1] (see also [SjW]). We obtain the optimal mean field bounds at the critical energy for Lyapunov exponents of random walks in random potentials in Z ^d at weak disorder. This extends some of the results in [W1]. Received: 9 December 1999 / Revised version: 8 May 2000 /?Published online: 15 February 2001     

Uniform Distribution and Fractal Dimensions for Generalized Cantor Products By

 For any and , let be a generalized Cantor product. The Hausdorff dimension of certain sets concerning are considered. Let be defined as in [11], the exceptional set of values of x for which is not uniformly distributed modulo 1 is also determined. (Received 22 May 2001; in revised form 7 September 2001)     

Generic well-posedness of minimization problems with mixed continuous constraints

In this paper we study mathematical programming problems with mixed constraints in a Banach space and show that most of the problems (in the Baire category sense) are well-posed. Our result is a generalization of a result of Ioffe et al. [SIAM J. Optim. 12 (2001) 461–478] obtained for finite-dimensional Banach spaces.     

The spin $^{\bf c}$ Dirac operator on high tensor powers of a line bundle

We study the asymptotic of the spectrum of the Dirac operator on high tensor powers of a line bundle. As application, we get a simple proof of the main result of Guillemin–Uribe [13, Theorem 2], which was originally proved by using the analysis of Toeplitz operators of Boutet de Monvel and Guillemin [10]. Received: 6 June 2001; in final form: 18 September 2001 / Published online: 28 February 2002     

Anomalous behaviour for the random corrections to the cumulants of random walks in fluctuating random media

The Central Limit Theorem for a model of discrete-time random walks on the lattice ℤ^ν in a fluctuating random environment was proved for almost-all realizations of the space-time nvironment, for all ν > 1 in [BMP1] and for all ν≥ 1 in [BBMP]. In [BMP1] it was proved that the random correction to the average of the random walk for ν≥ 3 is finite. In the present paper we consider the cases ν = 1,2 and prove the Central Limit Theorem as T→∞ for the random correction to the first two cumulants. The rescaling factor for theaverage is for ν = 1 and (ln T), for ν=2; for the covariance it is , ν = 1,2. Received: 25 November 1999 / Revised version: 7 June 2000 / Published online: 15 February 2001     

Towards Martins minimum

We show that it is consistent with MA + ?CH that the Forcing Axiom fails for all forcing notions in the class of ω^ω–bounding forcing notions with norms of [17]. Received: 28 April 1999 / Published online: 12 December 2001     

On mappings whose sum is monotone

Proposition 1 of this article points at a gap in the proof of Kuhlmann’s characterization of algebraically maximal valued fields [2]. The author [1] showed how to fill this gap. His arguments involved tools of mathematical logic and infinite combinatorics. Proposition 2 of this article provides us with a simple proof of the key fact of Kuhlmann’s characterization.     

On the Expected Condition Number of Linear Programming Problems

Summary.   Let A be an n×m real matrix and consider the linear conic system

On homogenization of time-dependent random flows

We study a diffusion with a random, time dependent drift. We prove the invariance principle when the spectral measure of the drift satisfies a certain integrability condition. This result generalizes the results of [13, 7]. Received: 25 February 2000 / Revised version: 11 December 2000 /?Published online: 14 June 2001     

On the weak Freese–Nation property of ?(ω)

Continuing [6], [8] and [16], we study the consequences of the weak Freese-Nation property of (?(ω),⊆). Under this assumption, we prove that most of the known cardinal invariants including all of those appearing in Cichoń's diagram take the same value as in the corresponding Cohen model. Using this principle we could also strengthen two results of W. Just about cardinal sequences of superatomic Boolean algebras in a Cohen model. These results show that the weak Freese-Nation property of (?(ω),⊆) captures many of the features of Cohen models and hence may be considered as a principle axiomatizing a good portion of the combinatorics available in Cohen models. Received: 7 June 1999 / Revised version: 17 October 1999 /?Published online: 15 June 2001     

On the discovery of the “good Broyden” method

This short note traces the events that led to the unsymmetric rank one formula known as the “good Broyden” update [5, 6], which is widely used within derivative-free mathematical software for solving a system of nonlinear equations. Received: February 5, 2000 / Accepted: February 19, 2000?Published online March 15, 2000     

Anisotropic error estimates for elliptic problems

Summary.  Moving from the anisotropic interpolation error estimates derived in [12], we provide here both a-priori and a-posteriori estimates for a generic elliptic problem. The a-priori result is deduced by following the standard finite element theory. For the a-posteriori estimate, the analysis extends to anisotropic meshes the theory presented in [3–5]. Numerical test-cases validate the derived results. Received July 22, 2001 / Revised version received March 20, 2002 / Published online July 18, 2002 Mathematics Subject Classification (1991): 65N15, 65N50