Sequential Monte Carlo simulated annealing

In this paper, we propose a population-based optimization algorithm, Sequential Monte Carlo Simulated Annealing (SMC-SA), for continuous global optimization. SMC-SA incorporates the sequential Monte Carlo method to track the converging sequence of Boltzmann distributions in simulated annealing. We prove an upper bound on the difference between the empirical distribution yielded by SMC-SA and the Boltzmann distribution, which gives guidance on the choice of the temperature cooling schedule and the number of samples used at each iteration. We also prove that SMC-SA is more preferable than the multi-start simulated annealing method when the sample size is sufficiently large.     

Optimizing human activity patterns using global sensitivity analysis

Implementing realistic activity patterns for a population is crucial for modeling, for example, disease spread, supply and demand, and disaster response. Using the dynamic activity simulation engine, DASim, we generate schedules for a population that capture regular (e.g., working, eating, and sleeping) and irregular activities (e.g., shopping or going to the doctor). We use the sample entropy (SampEn) statistic to quantify a schedule’s regularity for a population. We show how to tune an activity’s regularity by adjusting SampEn, thereby making it possible to realistically design activities when creating a schedule. The tuning process sets up a computationally intractable high-dimensional optimization problem. To reduce the computational demand, we use Bayesian Gaussian process regression to compute global sensitivity indices and identify the parameters that have the greatest effect on the variance of SampEn. We use the harmony search (HS) global optimization algorithm to locate global optima. Our results show that HS combined with global sensitivity analysis can efficiently tune the SampEn statistic with few search iterations. We demonstrate how global sensitivity analysis can guide statistical emulation and global optimization algorithms to efficiently tune activities and generate realistic activity patterns. Though our tuning methods are applied to dynamic activity schedule generation, they are general and represent a significant step in the direction of automated tuning and optimization of high-dimensional computer simulations.     

Comparison of Swendsen‐Wang and heat‐bath dynamics

We prove that the spectral gap of the Swendsen‐Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single‐spin dynamics. This implies rapid mixing for the two‐dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Ising model. After this we introduce a modified version of the Swendsen‐Wang algorithm for planar graphs and prove rapid mixing for the two‐dimensional Potts models at all non‐critical temperatures. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 520–535, 2013     

Resampling Markov Chain Monte Carlo Algorithms: Basic Analysis and Empirical Comparisons

Sampling from complex distributions is an important but challenging topic in scientific and statistical computation. We synthesize three ideas, tempering, resampling, and Markov moving, and propose a general framework of resampling Markov chain Monte Carlo (MCMC). This framework not only accommodates various existing algorithms, including resample-move, importance resampling MCMC, and equi-energy sampling, but also leads to a generalized resample-move algorithm. We provide some basic analysis of these algorithms within the general framework, and present three simulation studies to compare these algorithms together with parallel tempering in the difficult situation where new modes emerge in the tails of previous tempering distributions. Our analysis and empirical results suggest that generalized resample-move tends to perform the best among all the algorithms studied when the Markov kernels lead to fast mixing or even locally so toward restricted distributions, whereas parallel tempering tends to perform the best when the Markov kernels lead to slow mixing, without even converging fast to restricted distributions. Moreover, importance resampling MCMC and equi-energy sampling perform similarly to each other, often worse than independence Metropolis resampling MCMC. Therefore, different algorithms seem to have advantages in different settings.     

Path-following gradient-based decomposition algorithms for separable convex optimization

A new decomposition optimization algorithm, called path-following gradient-based decomposition, is proposed to solve separable convex optimization problems. Unlike path-following Newton methods considered in the literature, this algorithm does not require any smoothness assumption on the objective function. This allows us to handle more general classes of problems arising in many real applications than in the path-following Newton methods. The new algorithm is a combination of three techniques, namely smoothing, Lagrangian decomposition and path-following gradient framework. The algorithm decomposes the original problem into smaller subproblems by using dual decomposition and smoothing via self-concordant barriers, updates the dual variables using a path-following gradient method and allows one to solve the subproblems in parallel. Moreover, compared to augmented Lagrangian approaches, our algorithmic parameters are updated automatically without any tuning strategy. We prove the global convergence of the new algorithm and analyze its convergence rate. Then, we modify the proposed algorithm by applying Nesterov’s accelerating scheme to get a new variant which has a better convergence rate than the first algorithm. Finally, we present preliminary numerical tests that confirm the theoretical development.     

Simple, robust, selftuning controller

This paper proposes a robust method for automatic tuning of parameters of a discrete PID controller. The tuning rules for SISO and MIMO systems are based on automatic determination of critical gain and critical frequency from the estimated model parameters. The plant model can be expressed by a transfer function in continuous and/or discrete form or by differential and/or difference equation. A simple control law using Takahashi discrete form is proposed. Simulations results prove that it is easy to use being able to handle minimum and nonminimum phase plant as well.     

An optimal replenishment policy for deteriorating items with effective investment in preservation technology

In this paper, considering the amount invested in preservation technology and the replenishment schedule as decision variables, we formulate an inventory model with a time-varying rate of deterioration and partial backlogging. The objective is to find the optimal replenishment and preservation technology investment strategies while maximizing the total profit per unit time. For any given preservation technology cost, we first prove that the optimal replenishment schedule not only exists but is unique. Next, under given replenishment schedule, we show that the total profit per unit time is a concave function of preservation technology cost. We then provide a simple algorithm to figure out the optimal preservation technology cost and replenishment schedule for the proposed model. We use numerical examples to illustrate the model.     

Retailer’s optimal pricing and lot-sizing policies for deteriorating items with partial backlogging

Pricing is a major strategy for a retailer to obtain its maximum profit. Therefore, in this paper, we establish an economic order quantity model for a retailer to determine its optimal selling price, replenishment number and replenishment schedule with partial backlogging. We first prove that the optimal replenishment schedule not only exists but also is unique, for any given selling price. Next, we show that the total profit is a concave function of p when the replenishment number and schedule are given. We then provide a simple algorithm to find the optimal selling price, replenishment number and replenishment timing for the proposed model. Finally, we use a couple of numerical examples to illustrate the algorithm.     

Erratum to: Scheduling UET-tasks on a star network: complexity and approximation

In this article we investigate complexity and approximation on a processor network where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no polynomial-time heuristic with a performance guarantee smaller than \frac65{\frac{6}{5}} (respectively \frac1413{\frac{14}{13}}) for minimization of the makespan (respectively the total job completion time) on a processor network represented by a star. Moreover, we design an efficient polynomial-time approximation algorithm with a worst-case ratio of four. We also prove that a polynomial-time algorithm exists for a schedule with a length of at most four. Lastly, we generalize all previous results on complexity and approximation.     

Free Energy Wells and Overlap Gap Property in Sparse PCA

We study a variant of the sparse PCA (principal component analysis) problem in the “hard” regime, where the inference task is possible yet no polynomial-time algorithm is known to exist. Prior work, based on the low-degree likelihood ratio, has conjectured a precise expression for the best possible (subexponential) runtime throughout the hard regime. Following instead a statistical physics-inspired point of view, we show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. These free energy wells imply hitting time lower bounds that corroborate the low-degree conjecture: we show that a class of natural MCMC (Markov chain Monte Carlo) methods (with worst-case initialization) cannot solve sparse PCA with less than the conjectured runtime. These lower bounds apply to a wide range of values for two tuning parameters: temperature and sparsity misparametrization. Finally, we prove that the overlap gap property (OGP), a structural property that implies failure of certain local search algorithms, holds in a significant part of the hard regime. © 2022 Wiley Periodicals, Inc.     

Tuning a parametric Clarke–Wright heuristic via a genetic algorithm

Almost all heuristic optimization procedures require the presence of a well-tuned set of parameters. The tuning of these parameters is usually a critical issue and may entail intensive computational requirements. We propose a fast and effective approach composed of two distinct stages. In the first stage, a genetic algorithm is applied to a small subset of representative problems to determine a few robust parameter sets. In the second stage, these sets of parameters are the starting points for a fast local search procedure, able to more deeply investigate the space of parameter sets for each problem to be solved. This method is tested on a parametric version of the Clarke and Wright algorithm and the results are compared with an enumerative parameter-setting approach previously proposed in the literature. The results of our computational testing show that our new parameter-setting procedure produces results of the same quality as the enumerative approach, but requires much shorter computational time.     

Implementing the Nelder-Mead simplex algorithm with?adaptive parameters

In this paper, we first prove that the expansion and contraction steps of the Nelder-Mead simplex algorithm possess a descent property when the objective function is uniformly convex. This property provides some new insights on why the standard Nelder-Mead algorithm becomes inefficient in high dimensions. We then propose an implementation of the Nelder-Mead method in which the expansion, contraction, and shrink parameters depend on the dimension of the optimization problem. Our numerical experiments show that the new implementation outperforms the standard Nelder-Mead method for high dimensional problems.     

The linearization method and new classes of exact solutions in cosmology

We develop a method for constructing exact cosmological solutions of the Einstein equations based on representing them as a second-order linear differential equation. In particular, the method allows using an arbitrary known solution to construct a more general solution parameterized by a set of 3N constants, where N is an arbitrary natural number. The large number of free parameters may prove useful for constructing a theoretical model that agrees satisfactorily with the results of astronomical observations. Cosmological solutions on the Randall-Sundrum brane have similar properties. We show that three-parameter solutions in the general case already exhibit inflationary regimes. In contrast to previously studied two-parameter solutions, these three-parameter solutions can describe an exit from inflation without a fine tuning of the parameters and also several consecutive inflationary regimes. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 158, No. 2, pp. 312–320, February, 2009.     

A Confidence Region Approach to Tuning for Variable Selection

We develop an approach to tuning of penalized regression variable selection methods by calculating the sparsest estimator contained in a confidence region of a specified level. Because confidence intervals/regions are generally understood, tuning penalized regression methods in this way is intuitive and more easily understood by scientists and practitioners. More importantly, our work shows that tuning to a fixed confidence level often performs better than tuning via the common methods based on Akaike information criterion (AIC), Bayesian information criterion (BIC), or cross-validation (CV) over a wide range of sample sizes and levels of sparsity. Additionally, we prove that by tuning with a sequence of confidence levels converging to one, asymptotic selection consistency is obtained, and with a simple two-stage procedure, an oracle property is achieved. The confidence-region-based tuning parameter is easily calculated using output from existing penalized regression computer packages. Our work also shows how to map any penalty parameter to a corresponding confidence coefficient. This mapping facilitates comparisons of tuning parameter selection methods such as AIC, BIC, and CV, and reveals that the resulting tuning parameters correspond to confidence levels that are extremely low, and can vary greatly across datasets. Supplemental materials for the article are available online.     

Lagrangian Penalization Scheme with Parallel Forward–Backward Splitting

We propose a new iterative algorithm for the numerical approximation of the solutions to convex optimization problems and constrained variational inequalities, especially when the functions and operators involved have a separable structure on a product space, and exhibit some dissymmetry in terms of their component-wise regularity. Our method combines Lagrangian techniques and a penalization scheme with bounded parameters, with parallel forward–backward iterations. Conveniently combined, these techniques allow us to take advantage of the particular structure of the problem. We prove the weak convergence of the sequence generated by this scheme, along with worst-case convergence rates in the convex optimization setting, and for the strongly non-degenerate monotone operator case. Implementation issues related to the penalization of the constraint set are discussed, as well as applications in image recovery and non-Newtonian fluids modeling. A numerical illustration is also given, in order to prove the performance of the algorithm.     

Matlab implementation of a moving grid method based on the equidistribution principle

The objective of this paper is to report on the development of a method of lines (MOL) toolbox within MATLAB, and especially, on the implementation and test of a moving grid algorithm based on the equidistribution principle. This new implementation includes various spatial approximation schemes based on finite differences and slope limiters, the choice between several monitor functions, automatic grid adaptation to the initial condition, and provides a relatively easy tuning for the non-expert user. Several issues, including the sensitivity of the numerical results to the tuning parameters, are discussed. A few test problems characterized by solutions with steep moving fronts, including the Buckley-Leverett equation and an extended Fisher-Kolmogorov equation, are investigated so as to demonstrate the algorithm and software performance.     

On the swapping algorithm

The Metropolis‐coupled Markov chain method (or “Swapping Algorithm”) is an empirically successful hybrid Monte Carlo algorithm. It alternates between standard transitions on parallel versions of the system at different parameter values, and swapping two versions. We prove rapid mixing for two bimodal examples, including the mean‐field Ising model. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 66–97, 2002     

Periodic schedules for linear precedence constraints

We consider the computation of periodic cyclic schedules for linear precedence constraints graphs: a linear precedence constraint is defined between two tasks and induces an infinite set of usual precedence constraints between their executions such that the difference of iterations is a linear function. The objective function is the minimization of the maximal period of a task.We recall first that this problem may be modelled using linear programming. A polynomial algorithm is then developed to solve it for a particular class of linear precedence graphs called unitary graphs. We also show that a periodic schedule may not exist for unitary graphs. In the general case, a decomposition of the linear precedence graph into unitary components is computed and we assume that a periodic schedule exists for each of these components. Lower bounds on the periods are exhibited and we show that an optimal periodic schedule may not achieve them. The notion of quasi-periodic schedule is then introduced and we prove that this new class of schedules always reaches these bounds.     

A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem

In real life scheduling, variations of the standard traveling salesman problem are very often encountered. The aim of this work is to present a new heuristic method for solving three such special instances with a common approach. The proposed algorithm uses a variant of the threshold accepting method, enhanced with intense local search, while the candidate solutions are produced through an insertion heuristic scheme. The main characteristic of the algorithm is that it does not require modifications and parameter tuning in order to cope with the three different problems. Computational results on a variety of real life and artificial problems are presented at the end of this work and prove the efficiency and the ascendancy of the proposed method over other algorithms found in the literature.     

P|rj,on-line|∑Cj的一类在线算法与竞争比分析

本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法SSPT是此问题的一类在线算法,论文引入一个拟时间表,此时间表具有SRPT时间表的部分性质,论文通过此辅助时间表证明了SSPT算法是(3-(1/m))-competitive的.