Pure adaptive search in monte carlo optimization

Pure adaptive search constructs a sequence of points uniformly distributed within a corresponding sequence of nested regions of the feasible space. At any stage, the next point in the sequence is chosen uniformly distributed over the region of feasible space containing all points that are equal or superior in value to the previous points in the sequence. We show that for convex programs the number of iterations required to achieve a given accuracy of solution increases at most linearly in the dimension of the problem. This compares to exponential growth in iterations required for pure random search.     

Pure adaptive search in global optimization

Pure adaptive seach iteratively constructs a sequence of interior points uniformly distributed within the corresponding sequence of nested improving regions of the feasible space. That is, at any iteration, the next point in the sequence is uniformly distributed over the region of feasible space containing all points that are strictly superior in value to the previous points in the sequence. The complexity of this algorithm is measured by the expected number of iterations required to achieve a given accuracy of solution. We show that for global mathematical programs satisfying the Lipschitz condition, its complexity increases at mostlinearly in the dimension of the problem.This work was supported in part by NATO grant 0119/89.     

The interacting-particle algorithm with dynamic heating and cooling

We consider an interacting-particle algorithm which is population-based like genetic algorithms and also has a temperature parameter analogous to simulated annealing. The temperature parameter of the interacting-particle algorithm has to cool down to zero in order to achieve convergence towards global optima. The way this temperature parameter is tuned affects the performance of the search process and we implement a meta-control methodology that adapts the temperature to the observed state of the samplings. The main idea is to solve an optimal control problem where the heating/cooling rate of the temperature parameter is the control variable. The criterion of the optimal control problem consists of user defined performance measures for the probability density function of the particles’ locations including expected objective function value of the particles and the spread of the particles’ locations. Our numerical results indicate that with this control methodology the temperature fluctuates (both heating and cooling) during the progress of the algorithm to meet our performance measures. In addition our numerical comparison of the meta-control methodology with classical cooling schedules demonstrate the benefits in employing the meta-control methodology.     

Pattern Hit-and-Run for sampling efficiently on polytopes

Pattern Hit-and-Run (PHR) is a Markov chain Monte Carlo sampler for a target distribution that was originally designed for general sets embedded in a box. A specific set of interest to many applications is a polytope intersected with discrete or mixed continuous/discrete lattices. PHR requires an acceptance/rejection mechanism along a bidirectional walk to guarantee feasibility. We remove this inefficiency by utilizing the linearity of the constraints defining the polytope, so each iteration of PHR can be efficiently implemented even though the variables are allowed to be integer valued. Moreover, PHR converges to a uniform distribution in polynomial time for a class of discrete polytopes.     

A branch and bound algorithm for dynamic resource allocation in population disease management

We embed an approximate dynamic program into a branch-and-bound framework to solve sequential resource allocation problems in population disease management. The proposed algorithm is capable of providing an optimality guarantee and getting bounds on the optimality gap of healthcare interventions. A numerical study on screening and treatment policy implementation for chronic hepatitis C virus (HCV) infection provides useful insights regarding HCV elimination for baby boomers.     

Constructing large feasible suboptimal intervals for constrained nonlinear optimization

An algorithm for finding a large feasiblen-dimensional interval for constrained global optimization is presented. Then-dimensional interval is iteratively enlarged about a seed point while maintaining feasibility. An interval subdivision method may be used to check feasibility of the growing box. The resultant feasible interval is constrained to lie within a given level set, thus ensuring it is close to the optimum. The ability to determine such a feasible interval is useful for exploring the neighbourhood of the optimum, and can be practically used in manufacturing considerations. The numerical properties of the algorithm are tested and demonstrated by an example problem.This work was supported by Grants OTKA 2879/1991 and OTKA 2675/1991, and in part by NSF Grant DDM-9211001.     

Pure adaptive search for finite global optimization

Pure Adaptive Search is a stochastic algorithm which has been analyzed for continuous global optimization. When a uniform distribution is used in PAS, it has been shown to have complexity which is linear in dimension. We define strong and weak variations of PAS in the setting of finite global optimization and prove analogous results. In particular, for then-dimensional lattice {1,,k} ⁿ , the expected number of iterations to find the global optimum is linear inn. Many discrete combinatorial optimization problems, although having intractably large domains, have quite small ranges. The strong version of PAS for all problems, and the weak version of PAS for a limited class of problems, has complexity the order of the size of the range.The authors would like to thank the Department of Mathematics and Statistics at the University of Canterbury for support of this research.