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.     

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.     

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.     

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.     

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.     

Variational optimization via chattering

We develop a chattering approach to solve variational problems that lack traditional properties such as differentiable everywhere and convexity conditions. We prove that our chattering approximation approaches the true relaxed solution as the intervals get smaller. Our chattering approach suggests a nonlinear optimization problem that can be easily solved to recover the optimal trajectory. A numerical example demonstrates our approach.