Convex duality and the Skorokhod Problem. I

The solution to the Skorokhod Problem defines a deterministic mapping, referred to as the Skorokhod Map, that takes unconstrained paths to paths that are confined to live within a given domain G⊂ℝ ⁿ . Given a set of allowed constraint directions for each point of ∂G and a path ψ, the solution to the Skorokhod Problem defines the constrained version φ of ψ, where the constraining force acts along one of the given boundary directions using the “least effort” required to keep φ in G. The Skorokhod Map is one of the main tools used in the analysis and construction of constrained deterministic and stochastic processes. When the Skorokhod Map is sufficiently regular, and in particular when it is Lipschitz continuous on path space, the study of many problems involving these constrained processes is greatly simplified. We focus on the case where the domain G is a convex polyhedron, with a constant and possibly oblique constraint direction specified on each face of G, and with a corresponding cone of constraint directions at the intersection of faces. The main results to date for problems of this type were obtained by Harrison and Reiman [22] using contraction mapping techniques. In this paper we discuss why such techniques are limited to a class of Skorokhod Problems that is a slight generalization of the class originally considered in [22]. We then consider an alternative approach to proving regularity of the Skorokhod Map developed in [13]. In this approach, Lipschitz continuity of the map is proved by showing the existence of a convex set that satisfies a set of conditions defined in terms of the data of the Skorokhod Problem. We first show how the geometric condition of [13] can be reformulated using convex duality. The reformulated condition is much easier to verify and, moreover, allows one to develop a general qualitative theory of the Skorokhod Map. An additional contribution of the paper is a new set of methods for the construction of solutions to the Skorokhod Problem. These methods are applied in the second part of this paper [17] to particular classes of Skorokhod Problems. Received: 17 April 1998 / Revised version: 8 January 1999     

A Multiclass Feedback Queueing Network with a Regular Skorokhod Problem

We consider a four-class two-station network with feedback, with fluid inputs and a head-of-the-line generalized processor sharing discipline at each station. We derive the Skorokhod Problem associated with the network and obtain algebraic sufficient conditions for Lipschitz continuity of the associated Skorokhod Map. This provides the first example of a multiclass network with feedback for which the associated Skorokhod Problem has been proved to be regular. As an elementary application, we show that under the conditions which guarantee Lipschitz continuity the network is stable if and only if the usual load conditions apply.     

Convex duality and the Skorokhod Problem. II

In this paper we consider Skorokhod Problems on polyhedral domains with a constant and possibly oblique constraint direction specified on each face of the domain, and with a corresponding cone of constraint directions at the intersection of faces. In part one of this paper we used convex duality to develop new methods for the construction of solutions to such Skorokhod Problems, and for proving Lipschitz continuity of the associated Skorokhod Maps. The main alternative approach to Skorokhod Problems of this type is the reflection mapping technique introduced by Harrison and Reiman [8]. In this part of the paper we apply the theory developed in part one to show that the reflection mapping technique of [8] is restricted to a slight generalization of the class of problems originally considered in [8]. We further illustrate the power of the duality approach by applying it to two other classes of Skorokhod Problems – those with normal directions of constraint, and a new class that arises from a model of processor sharing in communication networks. In particular, we prove existence of solutions to and Lipschitz continuity of the Skorokhod Maps associated with each of these Skorokhod Problems. Received: 17 April 1998 / Revised: 8 January 1999     

Some Results on Skorokhod Embedding and Robust Hedging with Local Time

In this paper, we provide some results on Skorokhod embedding with local time and its applications to the robust hedging problem in finance. First we investigate the robust hedging of options depending on the local time by using the recently introduced stochastic control approach, in order to identify the optimal hedging strategies, as well as the market models that realize the extremal no-arbitrage prices. As a by-product, the optimality of Vallois’ Skorokhod embeddings is recovered. In addition, under appropriate conditions, we derive a new solution to the two-marginal Skorokhod embedding as a generalization of the Vallois solution. It turns out from our analysis that one needs to relax the monotonicity assumption on the embedding functions in order to embed a larger class of marginal distributions. Finally, in a full-marginal setting where the stopping times given by Vallois are well ordered, we construct a remarkable Markov martingale which provides a new example of fake Brownian motion.     

Pathwise uniqueness for reflecting Brownian motion in Euclidean domains

For a bounded C ^1,α domain in ℝ ^d we show that there exists a strong solution to the multidimensional Skorokhod equation and that weak uniqueness holds for this equation. These results imply that pathwise uniqueness and strong uniqueness hold for the Skorokhod equation. Received: 3 February 1999 / Revised version: 2 September 1999 /?Published online: 11 April 2000     

Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice

In Eurocrypt 2004 Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem (PR). Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well.      

Discretisation and duality of optimal Skorokhod embedding problems

We prove a strong duality result for a linear programming problem which has the interpretation of being a discretised optimal Skorokhod embedding problem, and we recover this continuous time problem as a limit of the discrete problems. With the discrete setup we show that for a suitably chosen objective function, the optimiser takes the form of a hitting time for a random walk. In the limiting problem we then reprove the existence of the Root, Rost, and cave embedding solutions of the Skorokhod embedding problem.The main strength of this approach is that we can derive properties of the discrete problem more easily than in continuous time, and then prove that these properties hold in the limit. For example, a consequence of the strong duality result is that dual optimisers exist, and our limiting arguments can be used to derive properties of the continuous time dual functions. These arguments are applied in Cox and Kinsley (2017), where the existence of dual solutions is required to prove characterisation results for optimal barriers in a financial application.     

Applying an Extended Guided Local Search to the Quadratic Assignment Problem

In this paper, we show how an extended Guided Local Search (GLS) can be applied to the Quadratic Assignment Problem (QAP). GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms, to help guide them out of local minima. We present empirical results of applying several extended versions of GLS to the QAP, and show that these extensions can improve the range of parameter settings within which Guided Local Search performs well. Finally, we compare the results of running our extended GLS with some state of the art algorithms for the QAP.     

State space collapse and stability of queueing networks

We study the stability of subcritical multi-class queueing networks with feedback allowed and a work-conserving head-of-the-line service discipline. Assuming that the fluid limit model associated to the queueing network satisfies a state space collapse condition, we show that the queueing network is stable provided that any solution of an associated linear Skorokhod problem is attracted to the origin in finite time. We also give sufficient conditions ensuring this attraction in terms of the reflection matrix of the Skorokhod problem, by using an adequate Lyapunov function. State space collapse establishes that the fluid limit of the queue process can be expressed in terms of the fluid limit of the workload process by means of a lifting matrix.     

Large deviations for multi-dimensional reflected fractional Brownian motion

By proving the continuity of multi-dimensional Skorokhod maps in a quasi-linearly discounted uniform norm on the doubly infinite time interval R, and strengthening know sample path large deviation principles for fractional Brownian motion to this topology, we obtain large deviation principles for the image of multi-dimensional fractional Brownian motions under Skorokhod maps as an immediate consequence of the contraction principle. As an application, we explicitly calculate large deviation decay rates for steady-state tail probabilities of certain queueing systems in multi-dimensional heavy traffic models driven by fractional Brownian motions.     

Solving the Probabilistic TSP with Ant Colony Optimization

In this paper, we describe new ways to apply Ant Colony Optimization (ACO) to the Probabilistic Traveling Salesperson Problem (PTSP). PTSP is a stochastic extension of the well known Traveling Salesperson Problem (TSP), where each customer will require a visit only with a certain probability. The goal is to find an a priori tour visiting all customers with minimum expected length, customers not requiring a visit simply being skipped in the tour.We show that ACO works well even when only an approximative evaluation function is used, which speeds up the algorithm, leaving more time for the actual construction. As we demonstrate, this idea can also be applied successfully to other state-of-the-art heuristics. Furthermore, we present new heuristic guidance schemes for ACO, better adapted to the PTSP than what has been used previously. We show that these modifications lead to significant improvements over the standard ACO algorithm, and that the resulting ACO is at least competitive to other state-of-the-art heuristics.     

On converse Lyapunov theorems for fluid network models

We consider the class of closed generic fluid network (GFN) models, which provides an abstract framework containing a wide variety of fluid networks. Within this framework a Lyapunov method for stability of GFN models was proposed by Ye and Chen. They proved that stability of a GFN model is equivalent to the existence of a functional on the set of paths that is decaying along paths. This result falls short of a converse Lyapunov theorem in that no state-dependent Lyapunov function is constructed. In this paper we construct state-dependent Lyapunov functions in contrast to path-wise functionals. We first show by counterexamples that closed GFN models do not provide sufficient information that allow for a converse Lyapunov theorem. To resolve this problem we introduce the class of strict GFN models by forcing closed GFN models to satisfy a concatenation and a semicontinuity condition. For the class of strict GFN models we define a state-dependent Lyapunov function and show that a converse Lyapunov theorem holds. Finally, it is shown that common fluid network models, like general work-conserving and priority fluid network models as well as certain linear Skorokhod problems define strict GFN models.     

On the computation of protein backbones by using artificial backbones of hydrogens

NMR experiments provide information from which some of the distances between pairs of hydrogen atoms of a protein molecule can be estimated. Such distances can be exploited in order to identify the three-dimensional conformation of the molecule: this problem is known in the literature as the Molecular Distance Geometry Problem (MDGP). In this paper, we show how an artificial backbone of hydrogens can be defined which allows the reformulation of the MDGP as a combinatorial problem. This is done with the aim of solving the problem by the Branch and Prune (BP) algorithm, which is able to solve it efficiently. Moreover, we show how the real backbone of a protein conformation can be computed by using the coordinates of the hydrogens found by the BP algorithm. Formal proofs of the presented results are provided, as well as computational experiences on a set of instances whose size ranges from 60 to 6000 atoms.     

An explicit solution to the Skorokhod embedding problem for functionals of excursions of Markov processes

We develop an explicit non-randomized solution to the Skorokhod embedding problem in an abstract setup of signed functionals of excursions of Markov processes. Our setting allows us to solve the Skorokhod embedding problem, in particular, for the age process of excursions of a Markov process, for diffusions and their signed age processes, for Azéma’s martingale and for Bessel processes of dimension smaller than 2.This work is a continuation and an important generalization of Obłój and Yor [J. Obłój, M. Yor, An explicit Skorokhod embedding for the age of Brownian excursions and Azéma martingale, Stochastic Process. Appl. 110 (1) (2004) 83–110]. Our methodology is based on excursion theory and the solution to the Skorokhod embedding problem is described in terms of the Itô measure of the functional. We also derive an embedding for positive functionals and we correct a mistake in the formula of Obłój and Yor [J. Obłój, M. Yor, An explicit Skorokhod embedding for the age of Brownian excursions and Azéma martingale, Stochastic Process. Appl. 110 (1) (2004) 83–110] for measures with atoms.     

Variational Inequality and Complementarity Problem for Set－Valued Mapping with Application

ＶａｒｉａｔｉｏｎａｌＩｎｅｑｕａｌｉｔｙａｎｄＣｏｍｐｌｅｍｅｎｔａｒｉｔｙＰｒｏｂｌｅｍｆｏｒＳｅｔ－ＶａｌｕｅｄＭａｐｐｉｎｇｗｉｔｈＡｐｐｌｉｃａｔｉｏｎ￥ＺｈａｎｇＣｏｎｇｊｕｎ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，Ｈｕａｉｂｅ...     

A generalized stochastic goal programming model

In this paper we show how one can get stochastic solutions of Stochastic Multi-objective Problem (SMOP) using goal programming models. In literature it is well known that one can reduce a SMOP to deterministic equivalent problems and reduce the analysis of a stochastic problem to a collection of deterministic problems. The first sections of this paper will be devoted to the introduction of deterministic equivalent problems when the feasible set is a random set and we show how to solve them using goal programming technique. In the second part we try to go more in depth on notion of SMOP solution and we suppose that it has to be a random variable. We will present stochastic goal programming model for finding stochastic solutions of SMOP. Our approach requires more computational time than the one based on deterministic equivalent problems due to the fact that several optimization programs (which depend on the number of experiments to be run) needed to be solved. On the other hand, since in our approach we suppose that a SMOP solution is a random variable, according to the Central Limit Theorem the larger will be the sample size and the more precise will be the estimation of the statistical moments of a SMOP solution. The developed model will be illustrated through numerical examples.     

关于模糊数空间的Skorokhod拓扑的注记

首先考察模糊数空间中Skorokhod度量与紧承下方图度量之间的关系,然后说明了文献[4]中的关于Skorokhod拓扑紧致性的例子是错误的并给出了正确的例子.     

An $$\mathcal{O}(m\log n)$$ algorithm for the weighted stable set problem in claw-free graphs with $$\alpha ({G}) \le 3$$

Mathematical Programming - In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with $$\alpha (G) \le 3$$ in time $$\mathcal{O}(|E|\log...     

Stochastic processes with independent increments for random mappings

Using additive functions defined on the combinatorial structure of all mappings of anN set into itself, we define paths in the space endowed with the Skorokhod topology. Taking a mapping with equal probability, we get a sequence of random processes. Necessary and sufficient conditions for the weak convergence of this sequence to a stochastic process with independent increments are established. It is shown that the class of such processes contains all possible limits, provided that, on the components of a mapping, the additive functions have values small in average. Partially supported by the Lithuanian State Science and Studies Foundation. Vilnius University, Naugarduko 24, 2006 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 4, pp. 498–516, October–December, 1999. Translated by E. Manstavičius     

A recipe for semidefinite relaxation for (0,1)-quadratic programming

We review various relaxations of (0,1)-quadratic programming problems. These include semidefinite programs, parametric trust region problems and concave quadratic maximization. All relaxations that we consider lead to efficiently solvable problems. The main contributions of the paper are the following. Using Lagrangian duality, we prove equivalence of the relaxations in a unified and simple way. Some of these equivalences have been known previously, but our approach leads to short and transparent proofs. Moreover we extend the approach to the case of equality constrained problems by taking the squared linear constraints into the objective function. We show how this technique can be applied to the Quadratic Assignment Problem, the Graph Partition Problem and the Max-Clique Problem. Finally we show our relaxation to be best possible among all quadratic majorants with zero trace.The research was partially supported by GAR 201/93/0519.Research support by Christian Doppler Laboratorium für Diskrete Optimierung.Research support by the National Science and Engineering Research Council Canada.