Title: “Global Optimization:  For Some Problems, There's HOPE”

Speaker: Daniel M. Dunlavy, Graduate Research Assistant, University of Maryland, John Von Neumann Research Fellowship Candidate

Date/Time: Tuesday, March 1, 2005, 11:00–12:15 am (MST)

Location: Building 980, Room 95 (Sandia NM), Building 915, Room S101 (Sandia CA)

Brief Abstract: A new method for solving unconstrained nonlinear optimization problems will be presented. The method, homotopy optimization using perturbations and ensembles (HOPE), is an extension of previously-developed homotopy optimization methods and has been used successfully to solve the protein structure prediction problem---a challenging optimization problem in biochemistry---for several protein models.

Given a template function for which the global minimizer is known or easy to compute and a target function to be minimized, HOPE generates a sequence of local minimizers of a continuous homotopy function between the two functions, starting at the global minimizer of the template function.  To increase the likelihood of finding the global minimizer of the target function, points in the sequence are perturbed and used as starting points for generating new sequences, creating an ensemble of sequences in the end. Each convergent subsequence leads to a local minimizer of the target function, and HOPE chooses the best of these local minimizers as its approximation to the global minimizer.

A brief discussion of the convergence properties of HOPE will be given, followed by a comparison of HOPE with simulated annealing and Newton's method (with a trust region) applied to solving the protein structure prediction problem.