A Stochastic Optimization Method for Partially Decomposable Problems, with Application to Analysis of NMR Spectra
Many real-life optimization problems have structures that one may be able to exploit to solve the problem efficiently. A common structure is partial decomposability, which decomposes the original problem into a set of weakly coupled sub-problems that are each relatively easy to solve.
However, due to the coupling, the solution to each sub-problem must also incorporate information from the other sub-problems.
We designed the Cross Entropy method Exploiting (partial) Decomposability (CEED ) to address such problems, especially analyzing 1H Nuclear Magnetic Resonance (NMR) spectra of mixtures. This analysis involves finding the concentration of chemicals in a complex liquid mixture.
Each chemical's signature is a set of clusters of peaks, that shift horizontally in a bounded domain and scale vertically proportional to the chemical's concentration.
Therefore when each chemical's signature is known, the task is to best match a nonlinear model, by finding appropriate shift and concentration values.
This could be formulated as a nonlinear optimization problem involving hundreds of variables.
Since chemical signatures have `local' effects on each other, the problem is decomposable to loosely coupled sub-problems that are easier to solve.
Experimental results show superior performance of CEED to other common optimization methods as well as a state-of-the-art systems for analysis of NMR.
We also apply CEED to the SAT and Sudoku combinatorial optimization problems to show the generality of our method and its superiority to the original Cross Entropy method.
Citation
S. Ravanbakhsh.
"A Stochastic Optimization Method for Partially Decomposable Problems, with Application to Analysis of NMR Spectra". MSc Thesis, September 2009.
BibTeX
@mastersthesis{Ravanbakhsh:09,
author = {Siamak Ravanbakhsh},
title = {A Stochastic Optimization Method for Partially Decomposable
Problems, with Application to Analysis of NMR Spectra},
year = 2009,
}Last Updated: September 30, 2010
Submitted by Siamak (Mohsen) Ravanbakhsh 
