The Gibbs Cloner for Combinatorial Optimization, Counting and Sampling

We present a randomized algorithm, called the cloning algorithm, for approximating the solutions of quite general NP-hard combinatorial optimization problems, counting, rare-event estimation and uniform sampling on complex regions. Similar to the algorithms of Diaconis–Holmes–Ross and Botev–Kroese the cloning algorithm is based on the MCMC (Gibbs) sampler equipped with an importance sampling pdf and, as usual for randomized algorithms, it uses a sequential sampling plan to decompose a “difficult” problem into a sequence of “easy” ones. The cloning algorithm combines the best features of the Diaconis–Holmes–Ross and the Botev–Kroese. In addition to some other enhancements, it has a special mechanism, called the “cloning” device, which makes the cloning algorithm, also called the Gibbs cloner fast and accurate. We believe that it is the fastest and the most accurate randomized algorithm for counting known so far. In addition it is well suited for solving problems associated with the Boltzmann distribution, like estimating the partition functions in an Ising model. We also present a combined version of the cloning and cross-entropy (CE) algorithms. We prove the polynomial complexity of a particular version of the Gibbs cloner for counting. We finally present efficient numerical results with the Gibbs cloner and the combined version, while solving quite general integer and combinatorial optimization problems as well as counting ones, like SAT.     

What can and cannot be done with Diophantine problems

This survey presents various theorems (obtained mainly by specialists in mathematical logic and computability theory) stating the impossibility of algorithms for solving certain Diophantine problems. Often the technique developed for obtaining such “negative” results also allows one to prove many “positive” theorems on the possibility of formulating Diophantine problems with special properties. This survey also lists a number of questions that remain open.     

Some new closures on orders

For each of the relations “less than or equal to”, “less than”, “covered by”, and “covered by or equal to”, we characterize finite orders (also called posets) with the property that the pair of Galois closure operators induced by the relation in question coincides with the pair of closure operators introduced and applied in our previous paper in 2007. We also consider the “less than or equal to” relation between the set of join-irreducible elements and the set of meet-irreducible elements, and we show that the above-mentioned pairs of closure operators coincide for finite modular lattices.     

Squared polynomial extrapolation methods with cycling: an application to the positron emission tomography problem

Roland and Varadhan (Appl. Numer. Math., 55:215–226, 2005) presented a new idea called “squaring” to improve the convergence of Lemaréchal’s scheme for solving nonlinear fixed-point problems. Varadhan and Roland (Squared extrapolation methods: A new class of simple and efficient numerical schemes for accelerating the convergence of the EM algorithm, Department of Biostatistics Working Paper. Johns Hopkins University, , 2004) noted that Lemaréchal’s scheme can be viewed as a member of the class of polynomial extrapolation methods with cycling that uses two fixed-point iterations per cycle. Here we combine these two ideas, cycled extrapolation and squaring, and construct a new class of methods, called squared polynomial methods (SQUAREM), for accelerating the convergence of fixed-point iterations. Our main goal is to evaluate whether the squaring device is effective in improving the rate of convergence of cycled extrapolation methods that use more than two fixed-point iterations per cycle. We study the behavior of the new schemes on an image reconstruction problem for positron emission tomography (PET) using simulated data. Our numerical experiments show the effectiveness of first- and higher-order squared polynomial extrapolation methods in accelerating image reconstruction, and also their relative superiority compared to the classical, “unsquared” vector polynomial methods.     

Efficient solution approaches for a discrete multi-facility competitive interaction model

In this paper, we present efficient solution approaches for discrete multi-facility competitive interaction model. Applying the concept of “Tangent Line Approximation” presented by the authors in their previous work, we develop efficient computational approaches—both exact and approximate (with controllable error bound α). Computational experiments show that the approximate approach (with small α) performs extremely well solving large scale problems while the exact approach performs very well for small to medium-sized problems.     

A Newton-like method for nonlinear system of equations

Tanabe (1988) proposed a variation of the classical Newton method for solving nonlinear systems of equations, the so-called Centered Newton method. His idea was based on a deviation of the Newton direction towards a variety called “Central Variety”. In this paper we prove that the Centered Newton method is locally convergent and we present a globally convergent method based on the centered direction used by Tanabe. We show the effectiveness of our proposal for solving nonlinear system of equations and compare with the Newton method with line search.     

Convergence of fluctuation-splitting schemes for two dimensional scalar conservation laws with a kinetic solver

Summary. The “fluctuation-splitting schemes” (FSS in short) have been introduced by Roe and Sildikover to solve advection equations on rectangular grids and then extended to triangular grids by Roe, Deconinck, Struij... For a two dimensional nonlinear scalar conservation law, we consider the case of a triangular grid and of a kinetic approach to reduce the discretization of the nonlinear equation to a linear equation and apply a particular FSS called N-scheme. We show that the resulting scheme converges strongly in in a finite volume sense. Received February 25, 1997 / Revised version received November 8, 1999 / Published online August 24, 2000     

The “walk in hemispheres” process and its applications to solving boundary value problems

Representations of solutions of boundary value problems for simple domains in the Monte Carlo algorithms are widely distributed [2]. In particular, widespread use is made of such a representation for the ball. It allows one to formally write an integral equation of the second kind for the required function in an arbitrary domain with regular boundary. Moreover, with the involvement of the joining conditions [1], one can picture a possible construction of a random process to “solve” the problem. However, the “walk in spheres” process, which solves the first boundary value problem for the Poisson equation, results in ɛ-biased estimators, and so the introduction of a regularization parameter is required. The authors investigate in detail the “walk in hemispheres” method, which has been proposed earlier by A. S. Sipin [10] without full justification. The use of the Green’s function for the hemisphere makes it possible to obtain estimators for the first and the third boundary value problems, as well as for the problem with discontinuous derivative; for a broad class of domains, these estimators are shown to be unbiased. The algorithms proposed feature a high degree of parallelism. Results of solving model problems are presented.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

A consistent value for games with n players and r alternatives

In Bolger [1993], an efficient value was obtained for a class of games called games with n players and r alternatives. In these games, each of the n players must choose one and only one of the r alternatives. This value can be used to determine a player’s “a priori” value in such a game. In this paper, we show that the value has a consistency property similar to the “consistency” for TU games in Hart/Mas-Colell [1989] and we present a set of axioms (including consistency) which characterizes this value.  The games considered in this paper differ from the multi-choice games considered by Hsiao and Raghavan [1993]. They consider games in which the actions of the players are ordered in the sense that, if i >j, then action i carries more “weight” than action j.  These games also differ from partition function games in that the worth of a coalition depends not only on the partitioning of the players but also on the action chosen by each subset of the partition. Received: April 1994/final version: June 1999     

Reversible stopping (“switching”) implies super contact

This note shows that the second derivative of the value function exists (across a stopping threshold, short “super contact”) if reversibly stopping and entering involves no cost, called “switching”. This holds for discrete (real option) as well as for continuous stochastic control problems and proves particularly suitable in real option set ups since it provides the lacking boundary condition. However, super contact does not hold in dynamic games. A simple example documents the applicability of this condition. This paper was written during my visit of the University of Technology, Sydney (UTS) and I am grateful for the hospitality of and the stimulus at the School of Finance and Economics, in particular to Carl Chiarella. I also acknowledge many helpful discussions with Thomas Dangl on related issues, valuable suggestions from a referee and last but not least encouragement by Josef Kallrath     

Orthogonal and bounded orthogonal spectral representations

The concept of an orthogonal spectral representation (OTSR) of a Hilbert spaceH relative to a spectral measureE(.) is introduced and it is shown that every Hilbert space admits an OTSR relative to a given spectral measure. Apart from the various results obtained about OTSRs, the principal result of Allan Brown (1974) is deduced as an easy consequence of this study. A new complete system of unitary invariants called the “equivalence of OTSRs”, is given for spectral measures. Two special types of OTSRs called “BOTSR” and “COBOTSR” are introduced and characterized respectively in terms of the “GCGS-property” and “CGS-property” of the associated spectral measure. Various complete systems of unitary invariants are given for spectral measures with the GCGS-property. Finally, the Wecken-Plesner-Rohlin theorem on hermitian operators with simple spectra is generalized to arbitrary spectral measures.     

On the Parametric Cubic Spline Approach for Solving Second Order Boundary Value Problems

In this article some comments on the paper “parametric cubic spline approach to the solution of a system of second order boundary value problems” in (Khan and Aziz, J. Optim. Theory Appl. 118:45–54, 2003) are given. This paper concerns with a numerical method for solving a second order boundary value problem associated with obstacle, unilateral and contact problems. Corrections are given for the convergence analysis of the numerical method and the computational experiments.     

Local Linear Convergence for Alternating and Averaged Nonconvex Projections

The idea of a finite collection of closed sets having “linearly regular intersection” at a point is crucial in variational analysis. This central theoretical condition also has striking algorithmic consequences: in the case of two sets, one of which satisfies a further regularity condition (convexity or smoothness, for example), we prove that von Neumann’s method of “alternating projections” converges locally to a point in the intersection, at a linear rate associated with a modulus of regularity. As a consequence, in the case of several arbitrary closed sets having linearly regular intersection at some point, the method of “averaged projections” converges locally at a linear rate to a point in the intersection. Inexact versions of both algorithms also converge linearly. Research of A.S. Lewis supported in part by National Science Foundation Grant DMS-0504032. Research of D.R. Luke supported in part by National Science Foundation Grant DMS-0712796.     

How to Play M 13?

A puzzle called “M ₁₃” J. H. Conway has described recently is explained. We report an implementation of the puzzle in the programming language Java. The program allows the human user to “play M ₁₃” interactively (and to cheat by solving it automatically). The program is an example on how to bring to life a nice piece of discrete mathematics. In this sense it presents not only a didactical way of seeing “mathematics at work”, but also displays the stabilizer chain method developed by C. Sims to solve group theoretic puzzles, the most famous of which being Rubik's cube.     

On the Structure of the Ergosurface of Pomeransky-Senkov Black Rings

We study the properties of the ergosurface of the Pomeransky–Senkov black rings, and show that it splits into an “inner” and an “outer” region. As for the singular set, the topology of the “outer ergosurface” depends upon the value of parameters.     

The island confinement method for reducing search space in local search methods

Typically local search methods for solving constraint satisfaction problems such as GSAT, WalkSAT, DLM, and ESG treat the problem as an optimisation problem. Each constraint contributes part of a penalty function in assessing trial valuations. Local search examines the neighbours of the current valuation, using the penalty function to determine a “better” neighbour valuation to move to, until finally a solution which satisfies all the constraints is found. In this paper we investigate using some of the constraints as “hard” constraints, that are always satisfied by every trial valuation visited, rather than as part of a penalty function. In this way these constraints reduce the possible neighbours in each move and also the overall search space. The treating of some constraints as hard requires that the space of valuations that are satisfied is “connected” in order to guarantee that a solution can be found from any starting position within the region; thus the concept of islands and the name “island confinement method” arises. Treating some constraints as hard provides new difficulties for the search mechanism since the search space becomes more jagged, and there are more deep local minima. A new escape strategy is needed. To demonstrate the feasibility and generality of our approach, we show how the island confinement method can be incorporated in, and significantly improve, the search performance of two successful local search procedures, DLM and ESG, on SAT problems arising from binary CSPs. A preliminary version of this paper appeared in AAAI’2002.     

Optimal Control of PDEs with Regularized Pointwise State Constraints

This paper addresses the regularization of pointwise state constraints in optimal control problems. By analyzing the associated dual problem, it is shown that the regularized problems admit Lagrange multipliers in L²-spaces. Under a certain boundedness assumption, the solution of the regularized problem converges to the one of the original state constrained problem. The results of our analysis are confirmed by numerical tests. Supported by the DFG Research Center “Mathematics for key technologies” (FZT 86) in Berlin.     

Viscosity approximation methods for nonexpansive multimaps in Banach spaces

We prove strong convergence of the viscosity approximation process for nonexpansive nonself multimaps. Furthermore, an explicit iteration process which converges strongly to a fixed point of multimap T is constructed. It is worth mentioning that, unlike other authors, we do not impose the condition ＂Tz = {z}＂ on the map T.     

A KAM phenomenon for singular holomorphic vector fields

Let X be a germ of holomorphic vector field at the origin of Cⁿ and vanishing there. We assume that X is a good perturbation of a “nondegenerate” singular completely integrable system. The latter is associated to a family of linear diagonal vector fields which is assumed to have nontrivial polynomial first integrals (they are generated by the so called “resonant monomials”). We show that X admits many invariant analytic subsets in a neighborhood of the origin. These are biholomorphic to the intersection of a polydisc with an analytic set of the form “resonant monomials = constants”. Such a biholomorphism conjugates the restriction of X to one of its invariant varieties to the restriction of a linear diagonal vector field to a toric variety. Moreover, we show that the set of “frequencies” defining the invariant sets is of positive measure.