DC Programming Approaches for Distance Geometry Problems

Hoai An Le Thi () and Tao Pham Dinh ()
Additional contact information
Hoai An Le Thi: University of Lorraine, Ile du Saulcy, Laboratory of Theoretical and Applied Computer Science (LITA EA 3097) UFR MIM
Tao Pham Dinh: National Institute for Applied Sciences, Rouen, Laboratory of Mathematics

Chapter Chapter 13 in Distance Geometry, 2013, pp 225-290 from Springer

Abstract: Abstract In this chapter, a so-called DCA method based on a DC (difference of convex functions) optimization approach for solving large-scale distance geometry problems is developed. Two main problems are considered: the exact and the general distance geometry problems. Different formulations of equivalent DC programs are introduced. Substantial subdifferential calculations permit to compute sequences of iterations in the DCA quite simply and allow exploiting sparsity in the large-scale setting. For improving the computational efficiency of the DCA schemes we investigate several techniques. A two-phase algorithm using shortest paths between all pairs of atoms to generate the complete dissimilarity matrix, a spanning trees procedure, and a smoothing technique are investigated in order to compute a good starting point (SP) for the DCAs. An important issue in the DC optimization approach is well exploited, say the nice effect of DC decompositions of the objective functions. For this purpose we propose several equivalent DC formulations based on the stability of Lagrangian duality and the regularization techniques. Finally, many numerical simulations of the molecular optimization problems with up to 12,567 variables are reported which prove the practical usefulness of the nonstandard nonsmooth reformulations, the globality of found solutions, the robustness, and the efficiency of our algorithms.

Keywords: Distance Constraint; Artificial Data; Trust Region Method; Regularization Technique; Lagrangian Duality (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-5128-0_13

Ordering information: This item can be ordered from
http://www.springer.com/9781461451280

DOI: 10.1007/978-1-4614-5128-0_13

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().