# Presentation: 550343

## Global Optimization:For Some Problems,There’s HOPEDaniel M. DunlavyUniversity of Maryland, College ParkApplied Mathematics and Scientific Computation

## Outline

- Problem and Existing Methods
- Homotopy Optimization Methods
- Protein Structure Prediction Problem
- Numerical Experiments
- Conclusions/Future Directions

## Problem

- Solve the unconstrained minimization problem
- Function Characteristics
- Solution exists, smooth (                       )
- Complicated (multiple minima, deep local minima)
- Good starting points unknown/difficult to compute
- Challenges
- Finding solution in reasonable amount of time
- Knowing when solution has been found

## Exhaustive/enumerative  search
Stochastic search [Spall, 2003]; adaptive [Zabinsky, 2003]
“Globalized” local search [Pinter, 1996]
Branch and bound [Horst and Tuy, 1996]
Genetic/evolutionary [Voss, 1999]
Smoothing methods [Piela, 2002]
Simulated annealing [Salamon, et al., 2002]
Homotopy/continuation methods [Watson, 2000]

- Stochastic search [Spall, 2003]; adaptive [Zabinsky, 2003]
- “Globalized” local search [Pinter, 1996]
- Branch and bound [Horst and Tuy, 1996]
- Genetic/evolutionary [Voss, 1999]
- Smoothing methods [Piela, 2002]
- Simulated annealing [Salamon, et al., 2002]
- Homotopy/continuation methods [Watson, 2000]

**Some Existing Methods**

## Outline

- Problem and Existing Methods
**Homotopy Optimization Methods**
- Protein Structure Prediction Problem
- Numerical Experiments
- Conclusions/Future Directions

## Goal
Solve complicated nonlinear target system

Steps to solution
Easy template system: 
Define a continuous homotopy function:

Example (convex):   
Trace path of                     from             to  

- Solve complicated nonlinear target system
- Steps to solution
- Easy template system:
- Define a continuous homotopy function:
- Example (convex):
- Trace path of                     from             to

**Homotopy Methods for ****Solving Nonlinear Equations**

## Goal
Minimize complicated nonlinear target function

Steps to solution
Easy template function:
Define a continuous homotopy function:

Example (convex):   
Produce sequence of minimizers of              w.r.t.starting at            and ending at 

- Minimize complicated nonlinear target function
- Steps to solution
- Easy template function:
- Define a continuous homotopy function:
- Example (convex):
- Produce sequence of minimizers of              w.r.t.starting at            and ending at

**Homotopy Optimization ****Methods (HOM)**

## Illustration of HOM

## Homotopy Optimization using Perturbations & Ensembles (HOPE)

- Improvements over HOM
- Produces ensemble of sequences of local minimizers of              by perturbing intermediate results
- Increases likelihood of predicting global minimizer
- Algorithmic considerations
- Maximum ensemble size
- Determining ensemble members

## Illustration of HOPE

## Convergence of HOPE

- pathtracing

- randomwalk

## Convergence of HOPE

## Outline

- Problem and Existing Methods
- Homotopy Optimization Methods
**Protein Structure Prediction Problem**
- Numerical Experiments
- Conclusions/Future Directions

## Protein Structure Prediction

- Amino Acid Sequence

## Protein Structure Prediction

- Given:
- Protein model
- Molecular properties
- Potential energy function (force field)
- Goal:
- Predict lowest energy conformation
- Native structure [Anfinsen, 1973]
- Develop hybrid method, combining:
- Energy minimization [numerical optimization]
- Comparative modeling [bioinformatics]
- Use **template** (known structure) to predict **target** structure

## 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

- 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

**Protein Model: Particle Properties**

- [Veitshans, Klimov, and Thirumalai. *Protein Folding Kinetics*, 1996.]

## Protein Model: Energy Function

## 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 

- 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

**Homotopy Optimization Method ****for Proteins**

## Outline

- Problem and Existing Methods
- Homotopy Optimization Methods
- Protein Structure Prediction Problem
**Numerical Experiments**
- Conclusions/Future Directions

## Numerical Experiments

- 9 chains (22 particles) with known structure

**Loop Region**

**Hydrophobic****	****Hydrophilic****	****Neutral**

- ABCDE F GH I

|  | A | B | C | D | E | F | G | H | I |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| A | 100 |  |  |  |  |  |  |  |  |
| B | 77 | 100 |  |  |  |  |  |  |  |
| C | 86 | 91 | 100 |  |  |  |  |  |  |
| D | 91 | 86 | 77 | 100 |  |  |  |  |  |
| E | 73 | 82 | 73 | 82 | 100 |  |  |  |  |
| F | 68 | 68 | 59 | 77 | 86 | 100 |  |  |  |
| G | 68 | 68 | 59 | 77 | 86 | 100 | 100 |  |  |
| H | 68 | 68 | 59 | 77 | 86 | 100 | 100 | 100 |  |
| I | 73 | 59 | 64 | 68 | 77 | 73 | 73 | 73 | 100 |

**Sequence Matching (%)**

## Numerical Experiments

**Numerical Experiments**

## Numerical Experiments

- 62 template-target pairs
- 10 pairs had identical native structures
- Methods
- HOM vs. Newton’s method w/trust region (N-TR)
- HOPE vs. 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)

- Ensemble SA
- Basin hopping
- T0 = 105
- Cycles = 10
- Berkeley schedule

## Results

## 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
- Protein Structure Prediction Problem
- Numerical Experiments
**Conclusions/Future Directions**

## Conclusions

- Homotopy optimization methods
- More successful than standard minimizers
- HOPE
- For problems with                          readily available
- Solves protein structure prediction problem
- Outperforms ensemble-based simulated annealing
- No fine tuning of SA

## HOPEful Directions

- Protein structure prediction
- Protein Data Bank (templates), TINKER (energy)
- Probabilistic convergence analysis (    )
- HOPE for large-scale problems
- Inherently parallelizable
- Communication: enforce maximum ensemble size
- Sandia
- Protein structure prediction (Bundler)
- LOCA, APPSPACK
- SGOPT

## Other Work/Interests

- Optimization
- Surrogate models in APPSPACK (Sandia)
- Linear Algebra
- Structure preserving eigensolvers
- Quaternion-based Jacobi-like methods
- RF circuit design – efficient DAE solvers
- Preconditioners, harmonic-balance methods
- Information processing/extraction
- Entity recognition/disambiguation
- Persons, locations, organization
- Querying, clustering and summarizing documents

## Acknowledgements

- Dianne O’Leary (UM)
- Advisor
- Dev Thirumalai (UM), Dmitri Klimov (GMU)
- Model, suggestions
- Ron Unger (Bar-Ilan)
- Problem formulation
- National Library of Medicine (NLM)
- Grant: F37-LM008162

**Notes:**
I’d like to thank SIAM for helping me get here, the NLM for supporting my work through a fellowship, and Dev Thirumalai and Dmitri Klimov at the University of Maryland for the use of their model and suggestions throughout the project.

## Thank You

**Daniel Dunlavy – HOPE**
- http://www.math.umd.edu/~ddunlavy
- ddunlavy@math.umd.edu

## HOPE Algorithm

## Homotopy Parameter Functions

- Split low/high frequency dihedral terms
- Homotopy parameter functions for each term

## Different         for individual energy terms

**Homotopy Function for Proteins**

- Template

- Target

## Structural Overlap Function

- Native

- Predicted

## RMSD

- Measures the distance between corresponding particles in the predicted and lowest energy conformations when they are optimally superimposed.

- where           is a rotation and translation of