Ambiguous chance constrained problems and robust optimization

In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set of the distributions is of the form where ρ_p denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prohorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice. Research partially supported by NSF grant CCR-00-09972. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282, and ONR grant N000140310514.     

On duality gap in linear conic problems

In their paper “Duality of linear conic problems” Shapiro and Nemirovski considered two possible properties (A) and (B) for dual linear conic problems (P) and (D). The property (A) is “If either (P) or (D) is feasible, then there is no duality gap between (P) and (D)”, while property (B) is “If both (P) and (D) are feasible, then there is no duality gap between (P) and (D) and the optimal values val(P) and val(D) are finite”. They showed that (A) holds if and only if the cone K is polyhedral, and gave some partial results related to (B). Later Shapiro conjectured that (B) holds if and only if all the nontrivial faces of the cone K are polyhedral. In this note we mainly prove that both the “if” and “only if” parts of this conjecture are not true by providing examples of closed convex cone in \mathbbR⁴{\mathbb{R}^{4}} for which the corresponding implications are not valid. Moreover, we give alternative proofs for the results related to (B) established by Shapiro and Nemirovski.     

Moment inequalities for sums of random matrices and their applications in optimization

In this paper, we consider various moment inequalities for sums of random matrices—which are well-studied in the functional analysis and probability theory literature—and demonstrate how they can be used to obtain the best known performance guarantees for several problems in optimization. First, we show that the validity of a recent conjecture of Nemirovski is actually a direct consequence of the so-called non-commutative Khintchine’s inequality in functional analysis. Using this result, we show that an SDP-based algorithm of Nemirovski, which is developed for solving a class of quadratic optimization problems with orthogonality constraints, has a logarithmic approximation guarantee. This improves upon the polynomial approximation guarantee established earlier by Nemirovski. Furthermore, we obtain improved safe tractable approximations of a certain class of chance constrained linear matrix inequalities. Secondly, we consider a recent result of Delage and Ye on the so-called data-driven distributionally robust stochastic programming problem. One of the assumptions in the Delage–Ye result is that the underlying probability distribution has bounded support. However, using a suitable moment inequality, we show that the result in fact holds for a much larger class of probability distributions. Given the close connection between the behavior of sums of random matrices and the theoretical properties of various optimization problems, we expect that the moment inequalities discussed in this paper will find further applications in optimization.     

Convexity of chance constrained programming problems with respect to a new generalized concavity notion

In this paper, convexity of chance constrained problems have been investigated. A new generalization of convexity concept, named h-concavity, has been introduced and it has been shown that this new concept is the generalization of the ??-concavity. Then, using the new concept, some of the previous results obtained by Shapiro et al. [in Lecture Notes on Stochastic Programming Modeling and Theory, SIAM and MPS, 2009] on properties of ??-concave functions, have been extended. Next the convexity of chance constraints with independent random variables is investigated. It will be shown how concavity properties of the mapping related to the decision vector have to be combined with suitable properties of decrease or increase for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels and then sufficient conditions for convexity of chance constrained problems which has been introduced by Henrion and Strugarek [in Convexity of chance constraints with independent random variables. Comput. Optim. Appl. 41:263?C276, 2008] has been extended in this paper for a wider class of real functions.     

Triangulating a nonconvex polytope

This paper is concerned with the problem of partitioning a three-dimensional nonconvex polytope into a small number of elementary convex parts. The need for such decompositions arises in tool design, computer-aided manufacturing, finite-element methods, and robotics. Our main result is an algorithm for decomposing a nonconvex polytope of zero genus withn vertices andr reflex edges intoO(n +r ²) tetrahedra. This bound is asymptotically tight in the worst case. The algorithm requiresO(n +r ²) space and runs inO((n +r ²) logr) time.This research was supported in part by the National Science Foundation under Grant CCR-8700917.     

Exploring hypergraphs with martingales

Recently, in [Random Struct Algorithm 41 (2012), 441–450] we adapted exploration and martingale arguments of Nachmias and Peres [ALEA Lat Am J Probab Math Stat 3 (2007), 133–142], in turn based on ideas of Martin‐Löf [J Appl Probab 23 (1986), 265–282], Karp [Random Struct Alg 1 (1990), 73–93] and Aldous [Ann Probab 25 (1997), 812–854], to prove asymptotic normality of the number L₁ of vertices in the largest component of the random r‐uniform hypergraph in the supercritical regime. In this paper we take these arguments further to prove two new results: strong tail bounds on the distribution of L₁, and joint asymptotic normality of L₁ and the number M₁ of edges of in the sparsely supercritical case. These results are used in [Combin Probab Comput 25 (2016), 21–75], where we enumerate sparsely connected hypergraphs asymptotically. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 325–352, 2017     

A variance bound for a general function of independent noncommutative random variables

The main purpose of this paper is to establish a noncommutative analogue of the Efron-Stein inequality, which bounds the variance of a general function of some independent random variables. Moreover, we state an operator version including random matrices, which extends a result of D. Paulin et al., [Ann. Probab. 44(5) (2016), 3431–3473]. Further, we state a Steele type inequality in the framework of noncommutative probability spaces.     

Embedding a polytope in a lattice

We present a special similarity ofR ⁴ⁿ which maps lattice points into lattice points. Applying this similarity, we prove that if a (4n−1)-polytope is similar to a lattice polytope (a polytope whose vertices are all lattice points) inR ⁴ⁿ , then it is similar to a lattice polytope inR ⁴ⁿ⁻¹, generalizing a result of Schoenberg [4]. We also prove that ann-polytope is similar to a lattice polytope in someR ^N if and only if it is similar to a lattice polytope inR ²ⁿ⁺¹, and if and only if sin²(<ABC) is rational for any three verticesA, B, C of the polytope.     

Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for <Emphasis Type="Italic">ρ</Emphasis><<Emphasis Type="Italic">c</Emphasis>

We present an exact simulation algorithm for the stationary distribution of customer delay for FIFO M/G/c queues in which ρ=λ/μ<c. In Sigman (J. Appl. Probab. 48A:209–216, 2011) an exact simulation algorithm was presented but only under the strong condition that ρ<1 (super stable case). We only assume that the service-time distribution G(x)=P(S≤x), x≥0, with mean 0<E(S)=1/μ<∞, and its corresponding equilibrium distribution $G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy$G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy are such that samples of them can be simulated. Unlike the methods used in Sigman (J. Appl. Probab. 48A:209–216, 2011) involving coupling from the past, here we use different methods involving discrete-time processes and basic regenerative simulation, in which, as regeneration points, we use return visits to state 0 of a corresponding random assignment (RA) model which serves as a sample-path upper bound.     

Spread‐out percolation in ℝd

Fix d ≥ 2, and let X be either ℤ^d or the points of a Poisson process in ℝ^d of intensity 1. Given parameters r and p, join each pair of points of X within distance r independently with probability p. This is the simplest case of a “spread‐out” percolation model studied by Penrose [Ann Appl Probab 3 (1993) 253–276], who showed that, as r → ∞, the average degree of the corresponding random graph at the percolation threshold tends to 1, i.e., the percolation threshold and the threshold for criticality of the naturally associated branching process approach one another. Here we show that this result follows immediately from of a general result of [3] on inhomogeneous random graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Random polytopes: Their definition,generation and aggregate properties

The definition of random polytope adopted in this paper restricts consideration to those probability measures satisfying two properties. First, the measure must induce an absolutely continuous distribution over the positions of the bounding hyperplanes of the random polytope; and second, it must result in every point in the space being equally as likely as any other point of lying within the random polytope. An efficient Monte Carlo method for their computer generation is presented together with analytical formulas characterizing their aggregate properties. In particular, it is shown that the expected number of extreme points for such random polytopes increases monotonically in the number of constraints to the limiting case of a polytope topologically equivalent to a hypercube. The implied upper bound of 2 ⁿ wheren is the dimensionality of the space is significantly less than McMullen's attainable bound on the maximal number of vertices even for a moderate number of constraints.     

On a relationship between Uspensky's theorem and poisson approximations

In this paper we show that Uspensky's expansion theorem for the Poisson approximation of the distribution of sums of independent Bernoulli random variables can be rewritten in terms of the Poisson convolution semigroup. This gives rise to exact evaluations and simple remainder term estimations for the deviations of the distributions in study with respect to various probability metrics, generalizing results of Shorgin (1977, Theory Probab. Appl., 22, 846–850). Finally, we compare the sharpness of Poisson versus normal approximations.     

Asymptotic Behavior of a Set-Statistic

The existence theorem of Minkowski for a polytope with given facet normals and areas is adapted to a data-analytic context. More precisely, we show that a centered, random point sample arising from an absolutely continuous distribution in R ^d can be uniquely mapped into such a polytope almost surely. With increasing sample size, the sequence of (scaled) polytopes converges almost surely to a limiting convex body that is associated with the underlying distribution. An accompanying central limit theorem is proved using methods from the theory of empirical processes. Received January 28, 1999, and in revised form April 12, 1999.     

The random integral representation conjecture: a quarter of a century later

In [Z.J. Jurek, Relations between the s-selfdecomposable and selfdecomposable measures, Ann. Probab., 13(2):592–608, 1985] and [Z.J. Jurek, Random integral representation for classes of limit distributions similar to Lévy class L ₀, Probab. Theory Relat. Fields, 78:473–490, 1988] the random integral representation conjecture was stated. It claims that (some) limit laws can be written as the probability distributions of random integrals of the form ò_{( a,b ]}h(t)\textdY_v( r(t) ) \int {_{\left( {a,b} \right]}h(t){\text{d}}{Y_v}\left( {r(t)} \right)} for some deterministic functions h, r, and a Lévy process Y_v(t),  t \geqslant 0 {Y_v}(t),\;t \geqslant 0 . Here we review situations where such a claim holds. Each theorem is followed by a remark that gives references to other related papers, results, and historical comments. Moreover, some open questions are stated.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

Order statistics of uncertain random variables with application to <Emphasis Type="Italic">k</Emphasis>-out-of-<Emphasis Type="Italic">n</Emphasis> system

Uncertain random variables are tools to deal with a mixture of uncertainty and randomness. A new concept of order statistics associated with uncertain random variables is proposed, and is applied to analyze k-out-of-n systems with uncertain random lifetimes. The chance distributions of order statistics of uncertain random variables are derived from the operational law of uncertain random variables. Finally, the reliability of k-out-of-n systems with uncertain random lifetimes is discussed.     

Mapping Zr into Zs with Maximal Contraction

Given any bijection f: Z ^r →f: Z ^s with s≥ r , easy volume comparisons show that there must be a universal constant K>0 (depending only on r and s ) and infinitely many pairs of points x,y∈ Z ^r such that || f(x)-f(y)|| > K|| x-y|| ^r/s . This puts a bound on how much contraction can be achieved for any such bijection. We show that, conversely, for any s≥ r there is a bijection f: Z ^r →Z ^s and a constant C>0 such that for all x,y∈ Z ^r we have || f(x)-f(y)|| <C|| x-y|| ^r/s . Phrased differently there is a bijection f: Z ^r →Z ^s which shrinks the distance between the images of any two points as much as possible, up to a constant factor. This generalizes a construction in fractal image processing and answers in the affirmative a question of Michael Freedman. Received May 15, 1996.     

Monotonicity of the cd-index for polytopes

We prove that the cd-index of a convex polytope satisfies a strong monotonicity property with respect to the cd-indices of any face and its link. As a consequence, we prove for d-dimensional polytopes a conjecture of Stanley that the cd-index is minimized on the d-dimensional simplex. Moreover, we prove the upper bound theorem for the cd-index, namely that the cd-index of any d-dimensional polytope with n vertices is at most that of C(n,d), the d-dimensional cyclic polytope with n vertices. Received September 29, 1998; in final form February 8, 1999