Enlargement of the Wiener filtration by an absolutely continuous random variable via Malliavin’s calculus

Summary. The analytic treatment of problems related to the asymptotic behaviour of random dynamical systems generated by stochastic differential equations suffers from the presence of non-adapted random invariant measures. Semimartingale theory becomes accessible if the underlying Wiener filtration is enlarged by the information carried by the orthogonal projectors on the Oseledets spaces of the (linearized) system. We study the corresponding problem of preservation of the semimartingale property and the validity of a priori inequalities between the norms of stochastic integrals in the enlarged filtration and norms of their quadratic variations in case the random element F enlarging the filtration is real valued and possesses an absolutely continuous law. Applying the tools of Malliavin’s calculus, we give smoothness conditions on F under which the semimartingale property is preserved and a priori martingale inequalities are valid. Received: 12 April 1995 / In revised form: 7 March 1996     

Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

The Brownian snake and solutions of Δu=u 2 in a domain

Summary We investigate the connections between the path-valued process called the Brownian snake and nonnegative solutions of the partial differential equation u=u ² in a domain of ^d . In particular, we prove two conjectures recently formulated by Dynkin. The first one gives a complete characterization of the boundary polar sets, which correspond to boundary removable singularities for the equation u=u ². The second one establishes a one-to-one correspondence between nonnegative solutions that are bounded above by a harmonic function, and finite measures on the boundary that do not charge polar sets. This correspondence can be made explicit by a probabilistic formula involving a special class of additive functionals of the Brownian snake. Our proofs combine probabilistic and analytic arguments. An important role is played by a new version of the special Markov property, which is of independent interest.     

Change of generalized indices of stationary solutions. to multiparametric optimization

We study the local change of the generalized index, which is a modification of the Morse index and the stationary index, for the multiparametric optimization. Under the Regular Value Condition, the change of the generalized index around a triplet (x,v,t) is locally bounded by the dimension of the parameter vector t, where x is a variable vector and v a vector of the Lagrange multiplier space. We also discuss the local change of the generalized index around a pair (x,t). Received: March 27, 1998 / Accepted: January 29, 2000?Published online April 20, 2000     

Optimization via enumeration: a new algorithm for the Max Cut Problem

We present a polynomial time algorithm to find the maximum weight of an edge-cut in graphs embeddable on an arbitrary orientable surface, with integral weights bounded in the absolute value by a polynomial of the size of the graph.</ The algorithm has been implemented for toroidal grids using modular arithmetics and the generalized nested dissection method. The applications in statistical physics are discussed. Received: June 1999 / Accepted: December 2000?Published online March 22, 2001     

Exponential ergodicity and regularity for equations with Lévy noise

We prove exponential convergence to the invariant measure, in the total variation norm, for solutions of SDEs driven by α-stable noises in finite and in infinite dimensions. Two approaches are used. The first one is based on Liapunov’s function approach by Harris, and the second on Doeblin’s coupling argument in [8]. Irreducibility and uniform strong Feller property play an essential role in both approaches. We concentrate on two classes of Markov processes: solutions of finite dimensional equations, introduced in [27], with Hölder continuous drift and a general, non-degenerate, symmetric α-stable noise, and infinite dimensional parabolic systems, introduced in [29], with Lipschitz drift and cylindrical α-stable noise. We show that if the nonlinearity is bounded, then the processes are exponential mixing. This improves, in particular, an earlier result established in [28], with a different method.     

Hypersurfaces of prescribed mean curvature in central projection-I

We consider the Dirichlet-problem associated with H-surfaces in central projection. By using a variational approach in the space of functions of bounded variation, and in connection with the theory of minimal sets, we obtain very general existence and regularity results provided the mean curvature H fulfils a certain monotony condition. Received: 11 February 2003     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

On the complexity of a class of combinatorial optimization problems with uncertainty

We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})² m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty but is polynomially solvable in the case of the interval representation of uncertainty. Received: July 1998 / Accepted: May 2000?Published online March 22, 2001     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

First exit time probability for multidimensional diffusions: A PDE-based approach

First exit time distributions for multidimensional processes are key quantities in many areas of risk management and option pricing. The aim of this paper is to provide a flexible, fast and accurate algorithm for computing the probability of the first exit time from a bounded domain for multidimensional diffusions. First, we show that the probability distribution of this stopping time is the unique (weak) solution of a parabolic initial and boundary value problem. Then, we describe the algorithm which is based on a combination of the sparse tensor product finite element spaces and an hp-discontinuous Galerkin method. We illustrate our approach with several examples. We also compare the numerical results to classical Monte Carlo methods.     

Characterization of the finite variation property for a class of stationary increment infinitely divisible processes

We characterize the finite variation property for stationary increment mixed moving averages driven by infinitely divisible random measures. Such processes include fractional and moving average processes driven by Lévy processes, and also their mixtures. We establish two types of zero–one laws for the finite variation property. We also consider some examples to illustrate our results.     

Conditions ensuring the applicability of cutting-plane methods for solving variational inequalities

Let VIP(F,C) denote the variational inequality problem associated with the mapping F and the closed convex set C. In this paper we introduce weak conditions on the mapping F that allow the development of a convergent cutting-plane framework for solving VIP(F,C). In the process we introduce, in a natural way, new and useful notions of generalized monotonicity for which first order characterizations are presented. Received: September 25, 1997 / Accepted: March 2, 1999?Published online July 20, 2000     

Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization

The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces. Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999     

On the existence of positive solutions for semilinear elliptic equations with singular lower order coefficients and Dirichlet boundary conditions

We give sufficient conditions for the existence of positive solutions to some semilinear elliptic equations in bounded domains with Dirichlet boundary conditions. We impose mild conditions on the domains and lower order (nonlinear) coefficients of the equations in that the bounded domains are only required to satisfy an exterior cone condition and we allow the coefficients to have singularities controlled by Kato class functions. Our approach uses an implicit probabilistic representation, Schauder's fixed point theorem, and new a priori estimates for solutions of the corresponding linear elliptic equations. In the course of deriving these a priori estimates we show that the Green functions for operators of the form on D are comparable when one modifies the drift term b on a compact subset of D. This generalizes a previous result of Ancona [2], obtained under an condition on b, to a Kato condition on . Received: 21 April 1998 / in final form 26 March 1999     

A probabilistic analysis of a measure of combinatorial complexity for the central curve

We investigate certain combinatorial properties of the central curve associated with interior point methods for linear optimization. We define a measure of complexity for the curve in terms of the number of turns, or changes of direction, that it makes in a geometric sense, and then perform an average case analysis of this measure for P-matrix linear complementarity problems. We show that the expected number of nondegenerate turns taken by the central curve is bounded by n ²-n, where the expectation is taken with respect to a sign-invariant probability distribution on the problem data. As an alternative measure of complexity, we also consider the number of times the central curve intersects with a wide class of algebraic hypersurfaces, including such objects as spheres and boxes. As an example of the results obtained, we show that the primal and dual variables in each coordinate of the central curve cross each other at most once, on average. As a further example, we show that the central curve intersects any sphere centered at the origin at most twice, on average. Received May 28, 1998 / Revised version received October 12, 1999?Published online December 15, 1999     

A cutting plane algorithm for the General Routing Problem

The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it is capable of providing very strong lower bounds and, in most cases, optimal solutions. Received: November 1998 / Accepted: September 2000?Published online March 22, 2001     

积分第一、二中值定理的中间点的渐近性质的一般性定理

把关于积分第一中值定理的中间点ξ的渐近性质的较多有关结果,归纳推广为一个弱条件下的一般性定理,并且在此弱条件下给出一种简洁的证明;而且,对于较少讨论的积分第二中值定理的中间点ξ的渐近性质,也得到相应的弱条件下的一般性定理,并且同样给出简洁证明.     

Self-regular functions and new search directions for linear and semidefinite optimization

In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension of the above results to semidefinite optimization (SDO) is also presented. Received: March 2000 / Accepted: December 2001?Published online April 12, 2002     

Global error bounds with fractional exponents

Using the partial order induced by a proper weakly lower semicontinuous function on a reflexive Banach space X we give a sufficient condition for f to have error bounds with fractional exponents. Application is given to identify the set of such exponents for quadratic functions. Received: August 20, 1999 / Accepted: March 20, 2000?Published online July 20, 2000