Action minimization and sharp-interface limits for the stochastic Allen-Cahn equation

We study the action minimization problem that is formally associated to phase transformation in the stochastically perturbed Allen-Cahn equation. The sharp-interface limit is related to (but different from) the sharp-interface limits of the related energy functional and deterministic gradient flows. In the sharp-interface limit of the action minimization problem, we find distinct “most likely switching pathways,” depending on the relative costs of nucleation and propagation of interfaces. This competition is captured by the limit of the action functional, which we derive formally and propose as the natural candidate for the Γ-limit. Guided by the reduced functional, we prove upper and lower bounds for the minimal action that agree on the level of scaling. © 2006 Wiley Periodicals, Inc.     

Large buffer asymptotics for generalized processor sharing queues with Gaussian inputs

In this paper we derive large-buffer asymptotics for a two-class Generalized Processor Sharing (GPS) model. We assume both classes to have Gaussian characteristics. We distinguish three cases depending on whether the GPS weights are above or below the average rate at which traffic is sent. First, we calculate exact asymptotic upper and lower bounds, then we calculate the logarithmic asymptotics, and finally we show that the decay rates of the upper and lower bound match. We apply our results to two special Gaussian models: the integrated Gaussian process and the fractional Brownian motion. Finally we derive the logarithmic large-buffer asymptotics for the case where a Gaussian flow interacts with an on-off flow. AMS Subject Classification Primary—60K25; Secondary—68M20, 60G15     

Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds

Resource-constrained project scheduling under a net present value objective attracts growing interest. Because this is an NP-hard problem, it is unlikely that optimum solutions can be computed for large instances within reasonable computation time. Thus, heuristics have become a popular research field. Up to now, however, upper bounds are not well researched. Therefore, most researchers evaluate their heuristics on the basis of a best known lower bound, but it is unclear how good the performance really is. With this contribution we close this gap and derive tight upper bounds on the basis of a Lagrangian relaxation of the resource constraints. We also use this approach as a basis for a heuristic and show that our heuristic as well as the cash flow weight heuristic proposed by Baroum and Patterson yield solutions very close to the optimum result. Furthermore, we discuss the proper choice of a test-bed and emphasize that discount rates must be carefully chosen to give realistic instances.     

Isoperimetric bounds for the first eigenvalue of the Laplacian

In this paper, generalizing an earlier result by Payne–Rayner, we prove an isoperimetric lower bound for the first eigenvalue of the Laplacian in the fixed membrane problem on a compact minimal surface in a Euclidean space R ⁿ with weakly connected boundary. We also prove an isoperimetric upper bound for the first eigenvalue of the Laplacian of an embedded closed hypersurface in R ⁿ .     

On countable completions of quotient ordered semigroups

A poset is said to be ω-chain complete if every countable chain in it has a least upper bound. It is known that every partially ordered set has a natural ω-completion. In this paper we study the ω-completion of partially ordered semigroups, and the topological action of such a semigroup on its ω-completion. We show that, for partially ordered semigroups, ω-completion and quotient with respect to congruences are two operations that commute with each other. This contrasts with the case of general partially ordered sets.     

Copolymer–homopolymer blends: global energy minimisation and global energy bounds

We study a variational model for a diblock copolymer–homopolymer blend. The energy functional is a sharp-interface limit of a generalisation of the Ohta–Kawasaki energy. In one dimension, on the real line and on the torus, we prove existence of minimisers of this functional and we describe in complete detail the structure and energy of stationary points. Furthermore we characterise the conditions under which the minimisers may be non-unique. In higher dimensions we construct lower and upper bounds on the energy of minimisers, and explicitly compute the energy of spherically symmetric configurations.     

Stability Analysis of an Optimal Control Problem for a Hyperbolic Equation

In this paper, we derive some results concerning the continuous dependence on parameters of optimal solutions to an optimal control problem that involves a quasilinear hyperbolic differential equation with a boundary condition and a nonlinear integral functional of action; continuous dependence of such kind is sometimes referred to as stability or sensitivity. To present a sufficient condition for the continuous dependence, we use the Kuratowski–Painlevé upper limit of a sequence of sets. Also offered is a technical interpretation of the results.     

Asymptotic solution of the Turán problem for some hypergraphs

Taking an ordinary graphL ² and replacing each of its vertices by a group ofr/2 vertices (r is even), we get anr-uniform hypergraphL′. In the casex(L ²)=2^m+1, we solve asymptotically the Turán problem forL′. Ifx(L ²)#2^m+1, the upper bound is still valid but proper constructions are not known.     

Dimensions of random recursive sets

We prove a theorem that generalizes the equality among the packing, Hausdorff, and upper and lower Minkowski dimensions for a general class of random recursive constructions, and apply it to constructions with finite memory. Then we prove an upper bound on the packing dimension of certain random distribution functions on [0, 1]. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 328, 2005, pp. 20–26.     

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     

A Reilly inequality for the first Steklov eigenvalue

Let M be a compact submanifold with boundary of a Euclidean space or a Sphere. In this paper, we derive an upper bound for the first non-zero eigenvalue p₁ of Steklov problem on M in terms of the r-th mean curvatures of its boundary ∂M. The upper bound obtained is sharp.     

Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

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.     

Comparison of ‘Tail Method’ Exact Confidence Limits for the Difference of Binomial Probabilities

Suppose that Y ₁ and Y ₂ are independent and have Binomial(n ₁,p ₁) and Binomial (n ₂,p ₂) distributions respectively. Also suppose that θ=p ₁−p ₂ is the parameter of interest. We consider the problem of finding an exact confidence limit (either upper or lower) for θ. The solution to this problem is very important for statistical practice in the health and life sciences. The ‘tail method’ provides a solution to this problem. This method finds the exact confidence limit by exact inversion of a hypothesis test based on a specified test statistic. Buehler (J. Am. Stat. Assoc. 52, 482–493, 1957) described, for the first time, a finite-sample optimality property of this confidence limit. Consequently, this confidence limit is sometimes called a Buehler confidence limit. An early tail method confidence limit for θ was described by Santner and Snell (J. Am. Stat. Assoc. 75, 386–394, 1980) who used the maximum likelihood estimator of θ as the test statistic. This confidence limit is known to be very inefficient (see e.g. Cytel Software, StatXact, version 6, vol. 2, 2004). The efficiency of the confidence limit resulting from the tail method depends greatly on the test statistic on which it is based. We use the results of Kabaila (Stat. Probab. Lett. 52, 145–154, 2001) and Kabaila and Lloyd (Aust. New Zealand J. Stat. 46, 463–469, 2004, J. Stat. Plan. Inference 136, 3145–3155, 2006) to provide a detailed explanation for the dependence of this efficiency on the test statistic. We consider test statistics that are estimators, Z-statistics and approximate upper confidence limits. This explanation is used to find the situations in which the tail method exact confidence limits based on test statistics that are estimators or Z-statistics are least efficient.     

Higher moments of certain <Emphasis Type="Italic">L</Emphasis>-functions on the critical line

We study the sixth-power moments of certain L-functions belonging to a sub-class of the Selberg’s class on the critical line and, using this, we conclude an upper bound for the fourth-power moments of certain L-functions related to GL ₃ on the critical line. This is an analogue of the upper bound for the twelfth-power moment of the Riemann zeta-function on the critical line. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 341–380, July–September, 2007.     

An Optimization Model for Stochastic Project Networks with Cash Flows

Project networks – or PERT networks – can be characterized by random completion times of activities and positive or negative cash flows throughout the project. In these cases the decision maker’s problem consists of determining a feasible activities schedule, to maximize the project financial value, where the financial value is measured by the net present value (npv) of cash flows.The analysis of these networks is a difficult computational task for the following reason. First, suppose that a schedule is fixed using a heuristic rule. Then the expected npv is calculated. But, due to stochastic job completion times, this problem belongs to the ♯-P complete difficulty class, e.g. problems that involve finding all the Hamiltonian cycles in a network. The problem is such that evaluating one project alone is not sufficient, but the optimal one has to be selected. This involves a further increase in computational time.This paper proposes a stochastic optimization model to determine a heuristic scheduling rule, that provides an approximate solution to finding the optimal project npv. A feature of this approach is that the scheduling rule is completely deterministic and defined when the project begins. Therefore an upper bound of the expected npv, that is an optimistic estimate, can be calculated through linear programming and a lower bound, that is a pessimistic estimate, can be calculated using simulation before the project begins.     

Nonexistence of Certain Spherical Designs of Odd Strengths and Cardinalities

A spherical τ -design on S ^n-1 is a finite set such that, for all polynomials f of degree at most τ , the average of f over the set is equal to the average of f over the sphere S ^n-1 . In this paper we obtain some necessary conditions for the existence of designs of odd strengths and cardinalities. This gives nonexistence results in many cases. Asymptotically, we derive a bound which is better than the corresponding estimation ensured by the Delsarte—Goethals—Seidel bound. We consider in detail the strengths τ =3 and τ =5 and obtain further nonexistence results in these cases. When the nonexistence argument does not work, we obtain bounds on the minimum distance of such designs. Received January 30, 1997, and in revised form November 29, 1997.     

An effective heuristic for large-scale capacitated facility location problems

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facilities with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. The heuristic is based on a Lagrangean relaxation which is used to select a subset of “promising” variables forming the core problem and on a Branch-and-Cut algorithm that solves the core problem. Computational results on very large scale instances (up to 4 million variables) are reported.     

Unitary designs and codes

A unitary design is a collection of unitary matrices that approximate the entire unitary group, much like a spherical design approximates the entire unit sphere. In this paper, we use irreducible representations of the unitary group to find a general lower bound on the size of a unitary t-design in U(d), for any d and t. We also introduce the notion of a unitary code—a subset of U(d) in which the trace inner product of any pair of matrices is restricted to only a small number of distinct absolute values—and give an upper bound for the size of a code with s inner product values in U(d), for any d and s. These bounds can be strengthened when the particular inner product values that occur in the code or design are known. Finally, we describe some constructions of designs: we give an upper bound on the size of the smallest weighted unitary t-design in U(d), and we catalogue some t-designs that arise from finite groups.