# Presentation: 090125

## Global Optimization: For Some Problems, There's HOPEDaniel M. DunlavySandia National Laboratories, Albuquerque, NM, USA Dianne P. O’LearyDept. of Computer Science and UMIACSUniversity of Maryland, College Park, MD, USACopper Mountain Conference on Iterative MethodsApril 3, 2006SAND2006-2001C

- Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company,for the United States Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.

## Outline

**Unconstrained Minimization Problem**
**Homotopy Optimization Methods**
**Numerical Experiments**
**Protein Structure Prediction Problem**
**Numerical Experiments**
**Concluding Remarks**

**Notes:**
The talk will be presented in two parts. In the first part we concentrate on the unconstrained minimization problem, the new homotopy methods we are presenting for solving this problem, and numerical experiments performed on standard test problems using these methods. In the second part, we focus on the protein structure prediction problem and  the application of our new methods to this problem, and present the results of numerical experiments. We will end the talk with some concluding remarks and present possible future directions.

## Problem

**Solve the ****unconstrained minimization ****problem**
**Function Characteristics**
- Solution exists
- Smooth (                       )
- Multimodal, deep local minima
- Good starting points unavailable

**Notes:**
We will be presenting new methods for solving the unconstrained minimization problem, where the goal is to find a point, x star, that minimizes a scalar function, f. This point is called a global minimizer of f. A point that minimizes a function only in a small neighborhood is called a local minimizer. Note, though, that our goal is finding a point at which the function attains its minimum value over the entire domain. We are interested in solving this problem for smooth functions where a solution exists. By smooth, we mean that f is twice continuously differentiable, as denoted here. Furthermore, f is assumed to contain multiple minima, and some of the local minima may have deep, narrow basins of attraction. Lastly, good points for starting a minimization method may not be available. Some of the challenges faced in developing a numerical method to solve this problem are finding a solution in a reasonable amount of time, and knowing when a solution is found.

## Some Related Methods

**Stochastic search methods **
- Random perturbations
**Simulated annealing**
- Perturbations, acceptance criterion, schedule
**Evolutionary algorithms**
- Ensembles/populations
**Smoothing methods**
- Deformation of function being minimized
**Homotopy/continuation methods**
- Nonlinear equations,

## Outline

**Unconstrained Minimization Problem**
**Homotopy Optimization Methods**
**Numerical Experiments**
**Protein Structure Prediction Problem**
**Numerical Experiments**
**Concluding Remarks**

## Homotopy Optimization Method (HOM)

**Goal**
- Minimize complicated nonlinear target function
**Steps to solution**
- Easy template function:      ,       is a known local min.
- Define a continuous homotopy function:
- Produce sequence of minimizers of               w.r.t.starting at            and ending at

## Illustration of HOM

**Illustration of HOM**

## Homotopy Optimization using Perturbations & Ensembles (HOPE)

**Improvements over HOM**
- Produce ensembles of  local minimizers of                          by perturbing intermediate results
- Increase likelihood of predicting a global minimizer
**Algorithmic considerations**
- Maximum ensemble size
- Determining ensemble members

## Illustration of HOPEMaximum ensemble size = 2

**Illustration of HOPE****Maximum ensemble size = 2**

## Considerations using HOPE

**Template function**
- Known solution, relation to target function
**Homotopy function**
- Continuous, but smoothness may help
**Parameters**
- Maximum ensemble size
- Perturbation function/amount of perturbation
- Number of perturbed versions produced
- Number of steps taken in
**Metric for choosing ensemble members**

## Convergence of HOPE 

**HOPE parameterized as existing methods**
- Probability-one homotopy methods for NLPs
- Stochastic search methods
- Pure Adaptive Search/Improving Hit-and-Run
- Simulated Annealing
**HOPE converges in probability**
- Smooth homotopy:
- Closed form for probability
- Conditions for convergence with probability one
**Extension to general homotopy maps**
- One spatial dimension,
- Basins of attraction must be known

## Outline

**Unconstrained Minimization Problem**
**Homotopy Optimization Methods**
**Numerical Experiments**
**Protein Structure Prediction Problem**
**Numerical Experiments**
**Concluding Remarks**

## Numerical Experiments

**Test Problems**
*N*-modal sine function:
- Moré, Garbow, Hillstrom test functions
- 5 functions where local methods failed
- Pintér test function
- Random multimodal functions, unique minimizer known
**Standard homotopy functions**
- Convex, probability-one
**Comparisons with local and stochastic search**
- More computation using HOM/HOPE
- Better results **and** ensembles of local minimizers

## Outline

**Unconstrained Minimization Problem**
**Homotopy Optimization Methods**
**Numerical Experiments**
**Protein Structure Prediction Problem**
**Numerical Experiments**
**Concluding Remarks**

## Protein Structure Prediction

- Amino Acid Sequence

## Protein Structure Prediction:Computational Methods

**Molecular dynamics**
- Langevin dynamics approximated using stochastic differential equation
**Bioinformatics**
- Sequence/structure matches to experimentally determined native structures
- Comparative modeling (threading, homology modeling)
**Energy Minimization**
- Find lowest energy conformation
- Native structure [Anfinsen, 1973]

## Some Existing Energy Minimization Methods

**Local methods**
- Truncated Newton and quasi-Newton methods
- Memory efficient (second derivatives not stored)
**Global methods**
- Stochastic search, simulated annealing,evolutionary algorithms, and smoothing methods
- Other methods
- Convex global underestimation
- Stochastic tunneling
- Packet annealing
- Derivative-free pattern search

## Energy Minimization using HOM

**Goal**
- Minimize energy function of target protein
**Steps to solution**
- Energy of template protein:
- Define a homotopy function:
- Deforms template protein into target protein
- Produce sequence of minimizers of                 starting at             and ending at

## Energy Minimization using HOPE

**Extensions of HOM**
- Perturbations
- Specific to protein structure
- Bond length, bond angle, and particle perturbations
- Ensembles
- Ensembles chosen using homotopy function value
**Benefits over existing minimization methods**
- Take advantage of sequence-related structural properties of template and target proteins

## Outline

**Problem and Existing Methods**
**Homotopy Optimization Methods**
**Numerical Experiments**
**Protein Structure Prediction Problem**
**Numerical Experiments**
**Concluding Remarks**

## Backbone Model: Particle Properties

**Backbone Model: Particle Properties**

**Backbone model**
-  Single chain of particles with residue attributes
-  Particles model C atoms in proteins
**Properties of particles**
-  Hydrophobic, Hydrophilic, Neutral
-  Diverse hydrophobic-hydrophobic interactions

- [Veitshans, *et al.,* 1996.]

## Backbone Model: Energy Function

## Backbone Model: Energy Function

## Backbone Model: Experiments

**9 chains (22 particles) with known structure**

## Backbone Model: Experiments

**62 template-target pairs**
- 10 pairs had identical native structures
**Methods**
- HOM vs. Newton’s method w/trust region (N-TR)
- HOPE vs. ensemble-based simulated annealing (SA)
- Different ensemble sizes (2,4,8,16)
- Averaged over 10 runs
- Perturbations where sequences differ
**Measuring success**
- Structural overlap function:
- Percentage of interparticle distances off by more   than 20% of the average bond length (   )
- Root mean-squared deviation (RMSD)

## Backbone Model: Results

## Backbone Model: Results

**Backbone Model: Results**

**Success of HOPE and SA with ensembles of size 16 for each template-target pair. The size of each circle represents the percentage of successful predictions over the 10 runs.**

**SA**

**HOPE**

## Outline

**Problem and Existing Methods**
**Homotopy Optimization Methods**
**Numerical Experiments**
**Protein Structure Prediction Problem**
**Numerical Experiments**
**Concluding Remarks**

## Conclusion

**New homotopy optimization methods**
- HOM: sequence of minimizers vs. path tracing
- HOPE: perturbations and ensembles
- Convergence (cast as existing methods)
**Numerical Experiments**
- HOM/HOPE outperform several standard methods
- Standard test functions
- Standard homotopy functions used
- Protein structure prediction
- Problem-specific homotopy functions
- Take advantage of sequence-related protein properties

## Future Directions

**Protein structure prediction**
- More realistic energy functions (AMBER, CHARMM)
- Protein Data Bank (templates)
- Different size chains for template/target
**HOPE for large-scale problems**
- Inherently parallelizable
- Communication: initializing ensembles at each step
**HOPE for other optimization problems**
- Constrained problems
**HOPE for other applications**

## Thank You

**Daniel M. Dunlavy – HOPE**
- dmdunla@sandia.gov
**Publications**
- D.M. Dunlavy, D.P. O'Leary, D. Klimov, and D. Thirumalai _[HOPE: A Homotopy Optimization Method for Protein Structure Prediction](http://www.liebertonline.com/doi/abs/10.1089/cmb.2005.12.1275)__ _*J. Comput. Biol.*, 12(10):1275-1288. Dec. 2005
- D. M. Dunlavy and D.P. O'Leary_[Homotopy Optimization Methods for Global Optimization](http://gaston.sandia.gov/cfupload/ccim_pubs_prod/057495.pdf)_ Sandia National Laboratories, SAND2005-7495. Dec. 2005
- D.M. Dunlavy_[Homotopy Optimization Methods and Protein Structure Prediction](mailto:dmdunla@sandia.gov?subject=Request%20for%20copy%20of%20dissertation)__Ph.D. Thesis, University of Maryland, College Park, Aug. 2005_
- D.M. Dunlavy_[Global Optimization of a Simplified Protein Energy Model](mailto:dmdunla@sandia.gov?subject=Request%20for%20copy%20of%20Global%20Optimization%20on%20a%20Simplified%20Protein%20Energy%20Model%20paper)_*In preparation*