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.     

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.     

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.     

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.     

Pattern discrete and mixed Hit-and-Run for global optimization

We develop new Markov chain Monte Carlo samplers for neighborhood generation in global optimization algorithms based on Hit-and-Run. The success of Hit-and-Run as a sampler on continuous domains motivated Discrete Hit-and-Run with random biwalk for discrete domains. However, the potential for efficiencies in the implementation, which requires a randomization at each move to create the biwalk, lead us to a different approach that uses fixed patterns in generating the biwalks. We define Sphere and Box Biwalks that are pattern-based and easily implemented for discrete and mixed continuous/discrete domains. The pattern-based Hit-and-Run Markov chains preserve the convergence properties of Hit-and-Run to a target distribution. They also converge to continuous Hit-and-Run as the mesh of the discretized variables becomes finer, approaching a continuum. Moreover, we provide bounds on the finite time performance for the discrete cases of Sphere and Box Biwalks. We embed our samplers in an Improving Hit-and-Run global optimization algorithm and test their performance on a number of global optimization test problems.     

An analytically derived cooling schedule for simulated annealing

We present an analytically derived cooling schedule for a simulated annealing algorithm applicable to both continuous and discrete global optimization problems. An adaptive search algorithm is used to model an idealized version of simulated annealing which is viewed as consisting of a series of Boltzmann distributed sample points. Our choice of cooling schedule ensures linearity in the expected number of sample points needed to become arbitrarily close to a global optimum.     

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.