HOMOTOPY OPTIMIZATION METHODS AND PROTEIN STRUCTURE PREDICTION

The focus of this dissertation is a new method for solving unconstrained min-imization problems|homotopy optimization using perturbations and ensembles (HOPE). HOPE is a homotopy optimization method that finds a sequence of minimizers of a homotopy function that maps a template function to the target function, the function from our minimization problem. To increase the likelihood of finding a global minimizer, points in the sequence are perturbed and used as starting points to find other minimizers. Points in the resulting ensemble of minimizers are used as starting points to find minimizers of the homotopy function as it deforms the template function into the target function. We show that certain choices of the parameters used in HOPE lead to instances of existing methods: probability-one homotopy methods, stochastic search methods, and simulated annealing. We use these relations and further analysis to demonstrate the convergence properties of HOPE. The development of HOPE was motivated by the protein folding problem, the problem of predicting the structure of a protein as it exists in nature, given it