Stochastic Enumeration Method for Counting Trees

The problem of estimating the size of a backtrack tree is an important but hard problem in the computational sciences. An efficient solution of this problem can have a major impact on the hierarchy of complexity classes. The first randomized procedure, which repeatedly generates random paths through the tree, was introduced by Knuth. Unfortunately, as was noted by Knuth and a few other researchers, the estimator can introduce a large variance and become ineffective in the sense that it underestimates the cost of the tree. Recently, a new sequential algorithm called Stochastic Enumeration (SE) method was proposed by Rubinstein et al. The authors showed numerically that this simple algorithm can be very efficient for handling different counting problems, such as counting the number of satisfiability assignments and enumerating the number of perfect matchings in bipartite graphs. In this paper we introduce a rigorous analysis of SE and show that it results in significant variance reduction as compared to Knuth’s estimator. Moreover, we establish that for almost all random trees the SE algorithm is a fully polynomial time randomized approximation scheme (FPRAS) for the estimation of the overall tree size.     

Two NP-Hard Art-Gallery Problems for Ortho-Polygons

D. T. Lee and A. K. Lin [2] proved that VERTEX-GUARDING and POINT-GUARDING are NP-hard for simple polygons. We prove that those problems are NP-hard for ortho-polygons, too.     

Universal Method for Stochastic Composite Optimization Problems

A fast gradient method requiring only one projection is proposed for smooth convex optimization problems. The method has a visual geometric interpretation, so it is called the method of similar triangles (MST). Composite, adaptive, and universal versions of MST are suggested. Based on MST, a universal method is proposed for the first time for strongly convex problems (this method is continuous with respect to the strong convexity parameter of the smooth part of the functional). It is shown how the universal version of MST can be applied to stochastic optimization problems.     

Stochastic Particle Method for Nonlinear Hyperbolic Problems

In this paper, we present a new method based on stochastic particles, which allows us to compute solutions of a system of nonlinear transport equations arising in the modeling of immiscible displacement in porous pedia. In this approach, we use different particles for different phases and move them according to the stochastic rules for which the probability density function depends on the spatial distribution of the particles. Our motivation for such a method is a Lagrangian modeling framework in which one can describe certain physical phenomena more naturally than in an Eulerian framework. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stochastic Enumeration with Importance Sampling

Many hard problems in the computational sciences are equivalent to counting the leaves of a decision tree, or, more generally, by summing a cost function over the nodes. These problems include calculating the permanent of a matrix, finding the volume of a convex polyhedron, and counting the number of linear extensions of a partially ordered set. Many approximation algorithms exist to estimate such sums. One of the most recent is Stochastic Enumeration (SE), introduced in 2013 by Rubinstein. In 2015, Vaisman and Kroese provided a rigorous analysis of the variance of SE, and showed that SE can be extended to a fully polynomial randomized approximation scheme for certain cost functions on random trees. We present an algorithm that incorporates an importance function into SE, and provide theoretical analysis of its efficacy. We also present the results of numerical experiments to measure the variance of an application of the algorithm to the problem of counting linear extensions of a poset, and show that introducing importance sampling results in a significant reduction of variance as compared to the original version of SE.     

Parallelizable Preprocessing Method for Multistage Stochastic Programming Problems

Stochastic programming has extensive applications in practical problems such as production planning and portfolio selection. Typically, the model has very large size and some techniques are often used to exploit the special structure of the programs. It has been noticed that the coefficient matrix may not be of full rank in the well-known scenario formulation of stochastic programming; thus, the preprocessing is often necessary in developing rapid decomposition methods. In this paper, we propose a parallelizable preprocessing method, which exploits effectively the structure of the formulation. Although the underlying idea is simple, the method turns out to be very useful in practice, since it may help us to select the nonanticipativity constraints efficiently. Some numerical results are reported confirming the usefulness of the method.This work was partially supported by the Informatics Research Center for Development of Knowledge Society Infrastructure, Graduate School of Informatics, Kyoto University, Kyoto, Japan. The work of the first author was also supported in part by the National Science Foundation of China, Grant 10571039. The work of the second author was also supported in part by the Scientific Research Grant-in-Aid from the Japan Society for the Promotion of Science. The authors are grateful to the referees for careful reading of the paper and helpful comments.This author’s work was done while he was visiting Kyoto University.     

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

An Adaptive Hybrid Spectral Method for Stochastic Helmholtz Problems

The implementation of an adaptive hybrid spectral method for Helmholtz equations with random parameters is addressed in this work. New error indicators for generalized polynomial chaos for stochastic approximations and spectral element methods for physical approximations are developed, and systematic adaptive strategies are proposed associated with these error indicators. Numerical results show that these error indicators provide effective estimates for the approximation errors, and the overall adaptive procedure results in efficient approximation method for the stochastic Helmholtz equations.     

Expected Residual Minimization Method for Stochastic Variational Inequality Problems

This paper considers a stochastic variational inequality problem (SVIP). We first formulate SVIP as an optimization problem (ERM problem) that minimizes the expected residual of the so-called regularized gap function. Then, we focus on a SVIP subclass in which the function involved is assumed to be affine. We study the properties of the ERM problem and propose a quasi-Monte Carlo method for solving the problem. Comprehensive convergence analysis is included as well. This work was supported in part by SRF for ROCS, SEM and Project 10771025 supported by NSFC.     

Stochastic Method for the Solution of Unconstrained Vector Optimization Problems

We propose a new stochastic algorithm for the solution of unconstrained vector optimization problems, which is based on a special class of stochastic differential equations. An efficient algorithm for the numerical solution of the stochastic differential equation is developed. Interesting properties of the algorithm enable the treatment of problems with a large number of variables. Numerical results are given.     

二阶锥约束随机变分不等式问题的数值方法研究

本文研究二阶锥约束随机变分不等式(SOCCSVI)问题,运用样本均值近似(SAA)方法结合光滑Fischer-Burmeister互补函数来求解该问题.首先,将SOCCSVI问题的Karush-Kuhn-Tucker系统转化为与之等价的方程组,并证明了该方程组的雅可比矩阵的非奇异性.其次,构造了光滑牛顿算法求解该方程组.最后,文章给出了两个数值实验证明了算法的有效性.     

Stochastic Methods for Ill-Posed Problems

This paper is devoted to the numerical analysis of ill-posed problems of evolution equations in Banach spaces using certain classes of stochastic one-step methods. The linear stability properties of these methods are studied. Regularisation is given by the choice of the regularisation parameter as = , where _n is the stepsize and provides the convergence on smooth initial data. The case of the approximation of well-posed problems is also considered.     

Convergence Results of the ERM Method for Nonlinear Stochastic Variational Inequality Problems

This paper considers the expected residual minimization (ERM) method proposed by Luo and Lin (J. Optim. Theory Appl. 140:103–116, 2009) for a class of stochastic variational inequality problems. Different from the work mentioned above, the function involved is assumed to be nonlinear in this paper. We first consider a quasi-Monte Carlo method for the case where the underlying sample space is compact and show that the ERM method is convergent under very mild conditions. Then, we suggest a compact approximation approach for the case where the sample space is noncompact. This work was supported in part by Project 10771025 supported by NSFC and SRFDP 20070141063 of China.     

Counting Function of Magnetic Resonances for Exterior Problems

We study the asymptotic distribution of the resonances near the Landau levels \({\Lambda_q =(2q+1)b}\), \({q \in \mathbb{N}}\), of the Dirichlet (resp. Neumann, resp. Robin) realization in the exterior of a compact domain of \({\mathbb{R}^3}\) of the 3D Schrödinger operator with constant magnetic field of scalar intensity \({b > 0}\). We investigate the corresponding resonance counting function and obtain the main asymptotic term. In particular, we prove the accumulation of resonances at the Landau levels and the existence of resonance-free sectors. In some cases, it provides the discreteness of the set of embedded eigenvalues near the Landau levels.     

Feasible Semismooth Newton Method for a Class of Stochastic Linear Complementarity Problems

We consider a class of stochastic linear complementarity problems (SLCPs) with finitely many realizations. In this paper we reformulate this class of SLCPs as a constrained minimization (CM) problem. Then, we present a feasible semismooth Newton method to solve this CM problem. Preliminary numerical results show that this CM reformulation may yield a solution with high safety for SLCPs.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

Singular Stochastic Control Problems Solved by a Sparse Simplex Method

Numerical solutions of singular stochastic control problemsin bounded intervals are obtained by a sparse linear-programmingalgorithm. The algorithm terminates in a finite number of iterationsin the absence of roundoff errors. Applications to other problemsin control theory are discussed.