SCOSI: Scientific Computing in Optimization, Simulation, and Inversion
SCOSI

Scientific Computing in
Optimization, Simulation, and Inversion

Sponsored by a grant from the Danish Natural Science Research Council (SNF).


The Research Statement

The goal of this research collaboration is to strengthen our research in scientific computing and algorithm development with emphasis on nonlinear and combinatorial optimization, simulation, and inversion. Among the most promising algorithms today are those based on various splitting techniques for subdivision of the problem as well as the algorithm, and there is a significant overlap between the splitting techniques currently in use within the above areas.

In this project we will coordinate the algorithm development within our specific research areas and thus be able to draw collectively upon progress in the individual areas. The focus of our research will lie on the following areas:

  • new splitting techniques for branch-and-bound algorithms in optimization
  • space-mapping techniques for complex optimization problems
  • application of domain decomposition and approximation theory in simulation algorithms
  • preconditioning techniques (based on domain decomposition and multilevel algorithms) for inversion algorithms
  • methods for including prior knowledge/side constraints in linear and nonlinear inversion algorithms.
The current research project involves some of the collaborators from the SNF-funded project EPOS (Efficient Parallel algorithms for Optimization and Simulation), which ended in 1999.

Research Activities

Final Report.

Space-Mapping Techniques in Optimization

Kaj Madsen, Hans Bruun Nielsen, Jacob Søndergaard.

Collaborator: Professor John W. Bandler, McMaster University, Canada.

  • John W. Bandler visited DTU in November 2000, February and November 2002, and March 2003.
  • Jacob Søndergaard visited McMaster University May 2001.
  • Kaj Madsen visited McMastermUniversity June 2000 and June 2002.
The goal of this project is to improve theory and to implement robust algorithms of space mapping techniques in the context of optimization of expensive functions. Experimental and working algorithms are implemented in Matlab; the final algorithms will be implemented in C, and possibly provided with a Matlab user interface.

References: [BaMa01], [BBMS00], [BBMS01a], [BBMS01b], [BBRM00], [BMBMJ02], [Pede01], [Sønd03].

Algorithms for Global Optimization

Kaj Madsen.

Collaborator: Professor Antanas Zilinskas, Vytautas Magnus University, Lithuania.

  • Kaj Madsen visited Vytautas Magnus University in June 2002.
Student programmers: Jørn Bratland, Jesper Frimodt.

The purpose is to develop robust optimization algorithms that, within a specified time frame, searches the parameter space as efficiently as possible in the search for the global optimum. The algorithms are based on ideas from interval analysis, and combined with classical optimization algorithms. Some algorithms lend themselves naturally to a parallel implementation, and these algorithms are currently being implemented on DTU's new parallel computing system.

References: [MaZi00a], [MaZi00b].

Modular Regularization Algorithms

Per Christian Hansen, Michael Jacobsen, Jan Marthedal Rasmussen.

Collaborators: Dr. James Nagy, Department of Mathematics and Computer Science, Emory Univeristy, Atlanta, Georgia, USA; Prof. Michael A. Saunders, Stanford University, USA.

  • Michael Jacobsen spent January-June 2002 at Emory University, Atlanta.
  • Jan M. Rasmussen spent September-December 2002 at Universidad Complutense de Madrid, Spain.
  • Juan Gutierrez Aguardo, PhD student at University of Valencia, visited DTU April-May 2001.
  • Daniela Calvetti, James Nagy and Lothar Reichel visited DTU in June 2001.
  • Michael Saunders, Stanford University, visited DTU August 2001.
  • Per Chr. Hansen visited Emory University, Atlanta i April 2002.
The goal of this project is to develop modular software for regularization in a variety of versions, with emphasis on other norms than the 2-norm. We are willing to sacrifice some efficiency for modularity, such that the users - with the aid of this software - can experiment with different regularization schemes without the burden of writing 1000s of lines of code. Our algorithms are implemented in Matlab using Matlab's object-oriented programming tools, with interfaces to computational modules written in C.

References: [CaHR02], [Jaco00], [Jaco01], [JaHS02], [Rasm01].

Parallel Algorithms

Per Christian Hansen, Kaj Madsen.

We study the efficient parallel implementation of large-scale algorithms in global optimization and iterative regularization.

References: [ReRH00], [Øste01].

Depth Resolution in 3D Geomagnetic Inversion

Per Christian Hansen, Michael Jacobsen.

Forskningsassistent: Marie Lund Andersen.

Collaborators: Prof. Maurizio Fedi and Valeria Paoletti, University of Napoli, Italy; Assoc. Prof. Klaus Mosegaard, Center for Planetary Science, Univ. of Copenhagen, Denmark.

  • Valeria Paoletti visited DTU in May-June 2000; February-March and and June-July 2001; January, June and August-September 2002.
  • Maurizio Fedi visited DTU June 2000 and June 2001.
  • Per Chr. Hansen visited University of Naples in October 2001 and July 2002.
  • Marie Lund Andersen visited University of Naples in October 2001 and July 2002.
The purpose of this project is to study the depth resolution which can be obtained from analytical continuation of 3D geomagnetic data. In addition we develop efficient iterative solution methods that can take advantage of the stucture of the problem.

References: [Ande02a], [ande02b], [AFHP02], [AFHOR02].

Nonlinear and Constrained Regularization Problems

Ann-Charlotte Berglund, Per Christian Hansen, Kaj Madsen.

Collaborator: Dr. Marielba Rojas, Wake Forest University, USA and CERFACS, Toulouse, France.

  • Dr. Elena Charkaeva visited DTU October-December 2000.
  • Dr. Marielba Rojas visited DTU in March 2001; March and June 2002.
  • Prof. Jan S. Hesthaven was visiting professor at DTU in August 2001.
  • Per Chr. Hansen visited CERFACS, Toulouse in August 2001 and July 2002.
In this project we develop large-scale algorithms for two kinds of problems: nonlinear unconstrained regularization problems linear inequality constrained regularization problems. The algorithms are tested on real-size problems from geophysics and homogenization.

References: [ChMZ02], [MaNS02].

Rank-Revealing Decompositions

Per Christian Hansen.

Collaborators: Dr. Ricardo D. Fierro, California State University San Marcos, USA; Dr. Plamen Y. Yalamov, University of Russe, Bulgaria.

  • Plamen Yalamov visited UNI-C January-March 2000.
  • Ricardo Fierro visited DTU January 2001.
  • Per Chr. Hansen visited California State University San Marcos in July 2001.
  • Adam W. Bojanczyk visited DTU in November 2001.
We develop specialized algorithms for computing rank-revealing decompositions of symmetric semidefinite and indefinite matrices, and we study their use in noise reduction and inverse problems. Current work includes a study of sparse versions of the algorithms and their use in large constrainted optimization problems.

References: [BrFr02], [FiHa01a], [FiHa01b], [HaYa01a], [HaYa01b].

Inverse Problems in Sound Source Reconstruction

Per Christian Hansen.

Collaborators: Jørgen Hald and Andreas P. Schuhmacher, Brüel & Kjær Sound and Vibration Measurements, Denmark.

The goal of this project is to develop a system for computing vibrations on a complex surface based on measurements of the acoustic field at some distance from the surface. The system uses a boundary element formulation of the acoustic problem, combined with a regularization algorithm based on the L-curve criterion or other data-driven parameter-choice algorithms. A prototype is being developed, and the influence of various error sources are studied.

References: [Hans02], [Kjel02], [ScHa01], [SHRH01].

Algorithms for Regularization Parameter Selection

Per Christian Hansen.

Collaborator: Prof. Misha E. Kilmer, Tufts University, Massachusetts, USA.

  • Misha E. Kilmer visited DTU in August 2000 and November 2001.
  • Per Chr. Hansen visited Tufts University in April and September 2002.
The goal of this work is to develop algorithms for a data-driven choice of the regularization parameter in regularization methods. Our methods are based on tools from statistics and signal processing, and the key idea is to extract the necessary information from the residual for the regularized solution.

References: [Hans01], [HaKK02], [Kjel02].

Parallel Branch-and-Bound Algorithms

Jens Clausen.

Collaborator: Professor Antanas Zilinskas, Vytautas Magnus University, Lithuania.

  • Andrea Sterbini visited DTU in 2000.
Branch-and-bound algorithms lend themselves naturally to parallel implementation, and experiments have demonstrated that the depth-first strategy for searching the search tree is superior in practise to the best-first strategy. Current work aims at the use ofaxiomatization in proving properties of different generic branch-and-bound algorithms, both sequential and parallel.

References: [ClRK00], [CHLL01], [ClZi02], [ThCl02], [SøCl00].

Partitioned Systems and Decoupled Integration Formulas

Stig Skelboe.

Collaborator: Zahari Zlatev, National Environmeltal Research Institute, Denmark.

Dynamical systems can often be decomposed into loosely coupled or partitioned subsystems. The system of ODEs can then be partitioned corresponding to the subsystems, and the loose couplings can be exploited by special integration methods to solve the problem using a parallel computer. The project aims at developing decoupled integration schemes with variable step size to control the local error and adaptive seclection of the partitionings.

References: [Skel00], [Skel02].

The Principal Investigators

The principal investigators and their areas of expertise are: Associated Ph.D. students are: Master projects connected to SCOSI research are:

Related Research Projects and Collaborations

The principal investigators also participate in the following research projects related to the SCOSI project.

Major SCOSI Activities

Publications

  • [Ande02a] M.L. Andersen, Depth Resolution Studies for 3D Inverse Geomagnetic Problems, Master Thesis, IMM, 2002.
  • [Ande02b] M.L. Andersen, Subspace preconditioned LSQR in 3-D geomagnetic reconstruction, report IMM-2002-15, 2002 (35 pages).
  • [AFHP02] M.L. Andersen, M. Fedi, P.C. Hansen and V. Paoletti, SVD and GSVD analysis of depth resolution in 3D multi-level potential field inversion, in preparation for Geophysics.
  • [AFHPA02] M. L. Andersen, M. Fedi, P. C. Hansen, V. Paolietti and A. Rapolla, Computational Properties of Algorithms for Multi-Level Inversion of 3-D Potential Fields, report IMM-2002-16, October 2002 (19 pages).
  • [BBMS00] M.H. Bakr, J.W. Bandler, J.E. Rayas-Sanchez, K. Madsen and J. Søndergaard, Review of the space mapping approach to engineering optimization and modeling, Optimization and Engineering, 1 (2000), pp. 241-276.
  • [BBMS01a] M.H. Bakr, J.W. Bandler, K. Madsen and J. Søndergaard, A New Introduction to the Space Mapping Technique, Optimization and Engineering, 2 (2001), pp. 369-384.
  • [BBMS01b] M.H. Bakr, J.W. Bandler, K. Madsen and J. Søndergaard, Space Mapping Optimization of Microwave Circuits Exploiting Surrogate Models, IEEE Trans. Microwave Theory Tech., MTT-48 (2000), pp. 2297-2306.
  • [BaMa01] J.W. Bandler, K. Madsen, Surrogate Modelling and Space Mapping for Engineering Design, Optimization and Engineering, 2 (2001), pp. 367-368.
  • [BMBMJ02] J.W. Bandler, A.S. Mohamed, M.H. Bakr, K. Madsen and J. Søndergaard, EM-Based Optimization Exploiting Partial Space Mapping and Exact Sensitivities, IEEE Trans. Microwave Theory Tech., to appear.
  • [BBRM00] M.H. Bakr, J.W. Bandler, J.E. Rayas-Sánchez, K. Madsen and J. Søndergaard, Space mapping optimization of microwave circuits exploiting surrogate models, IEEE Trans. Microwave Theory Tech., MTT-48 (2000), pp. 2297-2306.
  • [BrFr02] J. Bratland and J. Frimodt, Sparse symmetric rank-revealing decompositions, Master Thesis, IMM, 2002.
  • [CaHR02] D. Calvetti, P.C. Hansen and L. Reichel, L-curve curvature bounds via Lanczos bidiagonalization, Elec. Trans. Numer. Anal., 14 (2002), pp. 134-149.
  • [ChKZ02] B. Chen, K. Madsen and S. Zhang, On characterization of quadratic splines, submitted to J. Optimiz. Theory and Applic., 2002.
  • [CHLL01] J. Clausen, J. Hansen, J. Larsen and A. Larsen, Disruption management, OR/MS Today, 28 (2001), pp. 40-43.
  • [ClKR00] J. Clausen, S.E. Karish and F. Rendel, Solving graph bisection problems with semidefinite programming bounds, INFORMS J. Computing 12 (2000), pp. 177-191.
  • [ClZi02] J. Clausen and A. Zilinskas, Subdivision, sampling, and initialization strategies for simplical branch and bound in global optimization, Computers and Mathematics with Applications 44 (2002), pp. 943-955.
  • [FiHa01a] R.D. Fierro and P.C. Hansen, Truncated VSV solutions to symmetric rank-deficient problems, BIT, 42 (2002), pp. 531-540.
  • [FiHa01b] R.D. Fierro and P.C. Hansen, Recent developments in the use of rank revealing and Lanczos methods for solving TLS-related problems, Proc. 3. International Workshop on TLS and Errors-in-Variables Modeling, August 2001, Leuven, Belgium; Kluwer Academic Publishers, Dordrecht, 2002; pp. 47-56.
  • [Hans02] P. C. Hansen, Deconvolution and regularization with Toeplitz matrices (58 pages), Numerical Algorithms, 29 (2002), pp. 323-378.
  • [Hans01] P. C. Hansen, The L-curve and its use in the numerical treatment of inverse problems; invited chapter in P. Johnston (Ed.), Computational Inverse Problems in Electrocardiology, WIT Press, Southampton, 2001; pp. 119-142.
  • [HaKK02] P.C. Hansen, M. Kilmer and R.H. Kjeldsen, Exploiting residual information in the regularization of discrete ill-posed problems, report IMM-2002-18, 2002 (20 pages); submitted to SIAM J. Sci. Comp.
  • [HaYa01a] P. C. Hansen and P. Y. Yalamov, Computing symmetric rank-revealing decompositions via triangular factorization, SIAM J. Matrix Anal. Appl. 23 (2001), pp. 849-867.
  • [HaYa01b] P. C. Hansen and P. Y. Yalamov, Rank-revealing decompositions of symmetric Toeplitz matrices; in V. Olshevsky (Ed.), Structured Matrices in Mathematics, Computer Science, and Engineering II, Contemporary Mathematics, Vol. 281, American Mathematical Society, 2001; pp. 163-171.
  • [Jaco00] M. Jacobsen, Two-Grid Iterative Methods for Ill-Posed Problems, Master Thesis IMM-EKS-2000-27 (175 pages), Sept. 2000.
  • [Jaco01] M. Jacobsen, Tikhonov regularization and non-Euclidean norms, working paper, IMM, 2001.
  • [JaHS02] M. Jacobsen, P.C. Hansen and M.A. Saunders, Subspace Preconditions LSQR for Discrete Ill-Posed Problems, report IMM-2002-17, 2002 (16 pages); BIT, to appear.
  • [Kjel02] R.H. Kjeldsen, Residual Information in the Regularization of Discrete Ill-Posed Problems, Master Thesis, IMM, 2002.
  • [MaNS02] K. Madsen, H.B. Nielsen and J. Søndergaard, Robust subroutines for non-linear optimization, report IMM-2002-02, 2002 (54 pages).
  • [MaZi00a] K. Madsen and J. Zilinskas, Evaluating performance of attraction based subdivision methods for global optimization, 2nd International Conference on Simulation, Gaming, Training and Business Reengineering in Operations, Riga, 2000, pp. 38-42.
  • [MaZi00b] K. Madsen and J. Zilinskas, Testing real and interval methods for global optimization, report IMM-2000-05, 2000 (21 pages).
  • [Pede01] F.Ø. Pedersen, Advances on the Space Mapping Optimization Method, Master Thesis IMM-THESIS-2001-35 (78 pages), August 2001.
  • [Rasm01] J.M. Rasmussen, Compact Linear Operators and Krylov Subspace Methods, Master Thesis IMM-EKS-2001-9 (184 pages), February 2001.
  • [ReRH00] J.K. Reid, J.M. Rasmussen and P.C. Hansen, The LINPACK benchmark in Co-Array Fortran; in B. J. Jesson (Ed.), Proc. 6th European SGI/Cray MPP Workshop, September 2000, Manchester, UK.
  • [SHRH01] A. Schuhmacher, J. Hald, K.B. Rasmussen and P.C. Hansen, Sound source reconstruction using inverse boundary element calculations, J. Acoust. Soc. Am., 113 (2003), pp. 114-127.
  • [ScHa01] A. Schuhmacher and P.C. Hansen, Sound source reconstruction using inverse BEM; in R. Boone (Ed.), InterNoise 2001, The Hague, Holland, 2001; pp. 2109-2112.
  • [Skel00] S. Skelboe, Accuracy of decoupled implicit integration formulas, SIAM J. Sci. Comp., 21 (2000), pp. 2206-2224.
  • [Skel02] S. Skelboe, Partitioning techniques for ODEs for decoupled implicit integration formulars, DIKU report, 2002; in preparation for SIAM J.\ Sci.\ Comp.
  • [Sønd03] J. Søndergaard, Optimization Using Surrogate Models - by the Space Mapping Technique, Ph.D. Thesis, IMM, 2003.
  • [SøCl00] M.D. Sørensen and J. Clausen, Decentralized ground staff scheduling, report IMM-REP-2000-15, 2000 (25 pages).
  • [ThCl02] T. Thomadsen and J. Clausen, Hierarchical network design using simulated annealing, report IMM-2002-14, 2002 (29 pages).
  • [Øste01] J. Østergaard, Autonomous Distributed Computing, Master Thesis IMM-EKS-2001-28, August 2001.

Some Relevant Links