Asymptotic Analysis of Sample Average Approximation for Stochastic Optimization Problems with Joint Chance Constraints via Conditional Value at Risk and Difference of Convex Functions

Conditional Value at Risk (CVaR) has been recently used to approximate a chance constraint. In this paper, we study the convergence of stationary points, when sample average approximation (SAA) method is applied to a CVaR approximated joint chance constrained stochastic minimization problem. Specifically, we prove under some moderate conditions that optimal solutions and stationary points, obtained from solving sample average approximated problems, converge with probability one to their true counterparts. Moreover, by exploiting the recent results on large deviation of random functions and sensitivity results for generalized equations, we derive exponential rate of convergence of stationary points. The discussion is also extended to the case, when CVaR approximation is replaced by a difference of two convex functions (DC-approximation). Some preliminary numerical test results are reported.     

Comparison between Teichmuller and Lipschitz metrics

We study the Lipschitz metric on a Teichmüller space (definedby Thurston) and compare it with the Teichmüller metric.We show that in the thin part of the Teichmüller spacethe Lipschitz metric is approximated up to a bounded additivedistortion by the sup-metric on a product of lower-dimensionalspaces (similar to the Teichmüller metric as shown by Minsky).In the thick part, we show that the two metrics are equal upto a bounded additive error. However, these metrics are notcomparable in general; we construct a sequence of pairs of pointsin the Teichmüller space, with distances that approachzero in the Lipschitz metric while they approach infinity inthe Teichmüller metric.     

Fast approximations for sums of distances, clustering and the Fermat–Weber problem

We describe two data structures that preprocess a set S of n points in (d constant) so that the sum of Euclidean distances of points in S to a query point q can be quickly approximated to within a factor of . This preprocessing technique has several applications in clustering and facility location. Using it, we derive an O(nlogn) time deterministic and O(n) time randomized -approximation algorithm for the so called Fermat–Weber problem in any fixed dimension.     

Final attack ratio in SIR epidemic models for multigroup populations

We analyse an SIR epidemic model in a closed population subdivided in n groups. Population mixing occurs at two levels: within each group, and uniformly in the population. We prove that, if within-group transmission rates are large enough and not all identical to each other, then the final attack ratio is lower than what would occur in a population mixing homogeneously with the average transmission rate. We also show that the opposite may hold for certain parameter values and explore numerically the parameter regions in which the final attack ratio is higher or lower than in the corresponding homogeneous model. Finally, we analyse simulations of the corresponding stochastic model with finite group size, studying how well final attack ratio is approximated by the deterministic outcome and its relations with exponential growth rate.     

An Approximation Scheme for Uncertain Minimax Optimal Control Problems

In this work, we address an uncertain minimax optimal control problem with linear dynamics where the objective functional is the expected value of the supremum of the running cost over a time interval. By taking an independently drawn random sample, the expected value function is approximated by the corresponding sample average function. We study the epi-convergence of the approximated objective functionals as well as the convergence of their global minimizers. Then we define an Euler discretization in time of the sample average problem and prove that the value of the discrete time problem converges to the value of the sample average approximation. In addition, we show that there exists a sequence of discrete problems such that the accumulation points of their minimizers are optimal solutions of the original problem. Finally, we propose a convergent descent method to solve the discrete time problem, and show some preliminary numerical results for two simple examples.     

A BSSS algorithm for the single facility location problem in two regions with different norms

Suppose the plane is divided by a straight line into two regions with different norms. We want to find the location of a single new facility such that the sum of the distances from the existing facilities to this point is minimized. This is in fact a non-convex optimization problem. The main difficulty is caused by finding the distances between points on different sides of the boundary line. In this paper we present a closed form solution for finding these distances. We also show that the optimal solution lies in the rectangular hull of the existing points. Based on these findings then, an efficient big square small square (BSSS) procedure is proposed.     

Interfacial long traveling waves in a two‐layer fluid with variable depth

Long wave propagation in a two‐layer fluid with variable depth is studied for specific bottom configurations, which allow waves to propagate over large distances. Such configurations are found within the linear shallow‐water theory and determined by a family of solutions of the second‐order ordinary differential equation (ODE) with three arbitrary constants. These solutions can be used to approximate the true bottom bathymetry. All such solutions represent smooth bottom profiles between two different singular points. The first singular point corresponds to the point where the two‐layer flow transforms into a uniform one. In the vicinity of this point nonlinear shallow‐water theory is used and the wave breaking criterion, which corresponds to the gradient catastrophe is found. The second bifurcation point corresponds to an infinite increase in water depth, which contradicts the shallow‐water assumption. This point is eliminated by matching the “nonreflecting” bottom profile with a flat bottom. The wave transformation at the matching point is described by the second‐order Fredholm equation and its approximated solution is then obtained. The results extend the theory of internal waves in inhomogeneous stratified fluids actively developed by Prof. Roger Grimshaw, to the new solutions types.     

Horizontal variable-speed interception game solved by forced singular perturbation technique

The time-optimal pursuit-evasion game in the horizontal plane between two airplanes is analyzed by applying the technique of forced singular perturbations (FSPT). Based on the assumption of multiple time scale separation, a zeroth-order closed-form solution is obtained, enabling one to use realistic aerodynamic and propulsion data. Control strategies are approximated by explicit feedback expressions of the state variables and the aircraft performance parameters. The zeroth-order feedback approximation is compared to the optimal openloop solution of the game. This comparison confirms the validity of the FSPT approximation for sufficiently large initial distances of separation.This work was completed during the first author's visit as a Senior NRC Associate at NASA Ames Research Center, Moffett Field, California. Its earlier phase was partially supported by AFSC Contract No. F49620-79-C-0135.     

Landmarks in graphs

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a “graph space”. The robot can locate itself by the presence of distinctively labeled “landmark” nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.

Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a “metric basis”, and the minimum number of landmarks is called the “metric dimension” of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.     

Multi-Level Monte Carlo Path Integral Molecular Dynamics for Thermal Average Calculation in the Nonadiabatic Regime

With the path integral approach, the thermal average in multi-electronic-state quantum systems can be approximated by the ring polymer representation on an extended configuration space, where the additional degrees of freedom are associated with the surface index of each bead. The primary goal of this work is to propose a more efficient sampling algorithm for the calculation of such thermal averages. We reformulate the extended ring polymer approximation according to the configurations of the surface indexes, and by introducing a proper reference measure, the reformulation is recast as a ratio of two expectations of function expansions. By quantitatively estimating the sub-estimators, and minimizing the total variance of the sampled average, we propose a multi-level Monte Carlo path integral molecular dynamics method (MLMC-PIMD) to achieve an optimal balance of computational cost and accuracy.     

Price Expectations and Cobwebs Under Uncertainty

Classical approaches to location problems are based on the minimization of the average distance (the median concept) or the minimization of the maximum distance (the center concept) to the service facilities. The median solution concept is primarily concerned with the spatial efficiency while the center concept is focused on the spatial equity. The k-centrum model unifies both the concepts by minimization of the sum of the k largest distances. In this paper we investigate a solution concept of the conditional median which is a generalization of the k-centrum concept taking into account the portion of demand related to the largest distances. Namely, for a specified portion (quantile) of demand we take into account the entire group of the corresponding largest distances and we minimize their average. It is shown that such an objective, similar to the standard minimax, may be modeled with a number of simple linear inequalities. Equitable properties of the solution concept are examined.     

Probabilisticl p distances in location models

Modelling distances with thel _p norm is very widespread in site selecting location problems. This paper deals with the concept of a probabilisticp parameter which permits uncertainty in the directness of the routes that can be taken between a facility and demand points. This paper establishes the rather surprising result that the expected distances can themselves be closely approximated byl _p distances with appropriately chosenp parameters. This result is very useful when, as is often the case, expected distances are used in the optimization criterion.     

How does geographical distance translate into genetic distance?

Geographic structure can affect patterns of genetic differentiation and speciation rates. In this article, we investigate the dynamics of genetic distances in a geographically structured metapopulation. We model the metapopulation as a weighted directed graph, with $d$ vertices corresponding to $d$ subpopulations that evolve according to an individual based model. The dynamics of the genetic distances is then controlled by two types of transitions — mutation and migration events. We show that, under a rare mutation–rare migration regime, intra subpopulation diversity can be neglected and our model can be approximated by a population based model. We show that under a large population-large number of loci limit, the genetic distance between two subpopulations converges to a deterministic quantity that can asymptotically be expressed in terms of the hitting time between two random walks in the metapopulation graph. Our result shows that the genetic distance between two subpopulations does not only depend on the direct migration rates between them but on the whole metapopulation structure.     

UMTS radio network evaluation and optimization beyond snapshots

A new evaluation scheme for universal mobile telecommunications system (UMTS) radio networks is introduced. The approach takes the complex coupling of coverage and capacity through interference into account. Cell load estimates, otherwise obtained through Monte-Carlo simulation, can now be approximated without time-consuming iterative simulations on user snapshots. The two cornerstones are the generalization of interference coupling matrices from user snapshots to average load and the emulation of load control by an analytical scaling scheme. Building on the new evaluation scheme, two novel radio network optimization algorithms are presented: an efficient local search procedure and a mixed integer program that aims at designing the coupling matrix. Computational experiments for optimizing antenna tilts show that our new approaches outperform traditional snapshot models     

Approximation of Neural Network Dynamics by Reaction-Diffusion Equations

The equations of the Hopfield network, without the constraint of symmetry, can have complex behaviours. Cottet borrowed techniques from particle methods to show that a class of such networks with symmetric, translation-invariant connection matrices may be approximated by a reaction–diffusion equation. This idea is extended to a wider class of network connections yielding a slightly more complex reaction–diffusion equation. It is also shown that the approximation holds rigorously only in certain spatial regions (even for Cottet's special case) but the small regions where it fails, namely within transition layers between regions of high and low activity, are not likely to be critical.     

Indecomposable quasi‐characteristics scheme on pyramidal stencil and its application for numerical simulation of two‐phase flows through heterogeneous porous medium

A new high‐resolution indecomposable quasi‐characteristics scheme with monotone properties based on pyramidal stencil is considered. This scheme is based on consideration of two high‐resolution numerical schemes approximated governing equations on the pyramidal stencil with different kinds of dispersion terms approximation. Two numerical solutions obtained by these schemes are analyzed, and the final solution is chosen according to the special criterion to provide the monotone properties in regions where discontinuities of solutions could arise. This technique allows to construct the high‐order monotone solutions and keeps both the monotone properties and the high‐order approximation in regions with discontinuities of solutions. The selection criterion has a local character suitable for parallel computation. Application of the proposed technique to the solution of the time‐dependent 2D two‐phase flows through the porous media with the essentially heterogeneous properties is considered, and some numerical results are presented. © 2002 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 18: 44–55, 2002     

An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions

The single facility location problem with demand regions seeks for a facility location minimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. \(\ell _1\) or \(\ell _\infty \). We develop an exact combinatorial algorithm running in time \(O(n\log ^c n)\) for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.     

Extensions of saddlepoint-based bootstrap inference

We propose two substantive extensions to the saddlepoint-based bootstrap (SPBB) methodology, whereby inference in parametric models is made through a monotone quadratic estimating equation (QEE). These are motivated through the first-order moving average model, where SPBB application is complicated by the fact that the usual estimators, method of moments (MOME), least squares, and maximum likelihood (MLE), all have mixed distributions and tend to be roots of high-order polynomials that violate the monotonicity requirement. A unifying perspective is provided by demonstrating that these estimators can all be cast as roots of appropriate QEEs. The first extension consists of two double saddlepoint-based Monte Carlo algorithms for approximating the Jacobian term appearing in the approximated density function of estimators derived from a non-monotone QEE. The second extension considers inference under QEEs from exponential power families. The methods are demonstrated for the MLE under a Gaussian distribution, and the MOME under a joint Laplace distribution for the process.     

A 2-approximation polynomial algorithm for a clustering problem

A 2-approximation algorithm is presented for some NP-hard data analysis problem that consists in partitioning a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. The center of the first cluster is the average value of vectors in the cluster, and the center of the second one is the origin.     

Complex Region Spatial Smoother (CReSS)

Conventional smoothing over complicated coastal and island regions may result in errors across boundaries, due to the use of Euclidean distances to measure interpoint similarity. The new Complex Region Spatial Smoother (CReSS) method presented here uses estimated geodesic distances, model averaging, and a local radial basis function to provide improved smoothing over complex domains. CReSS is compared, via simulation, with recent related smoothing techniques, Thin Plate Splines (TPS), geodesic low rank TPS (GLTPS), and the Soap film smoother (SOAP). The GLTPS method cannot be used in areas with islands and SOAP can be hard to parameterize. CReSS is comparable with, if not better than, all considered methods on a range of simulations. Supplementary materials for this article are available online.