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
- Summer school:
Decomposition Algorithms in Scientific Computing,
August 21 - September 1, 2000. Teachers: Jens Clausen, IMM,
Jack J. Dongarra, University of Tennessee, USA, and Martin Gander,
McGill University,
Canada.
- Workshop:
First International Workshop
on Surrogate Modelling and Space Mapping for Engineering Applications,
November 16-18, 2000. Approximately 50 international scientists and
representatives from industry attained the workshop.
- Summer school:
Sparse Matrix Computations,
August 13-18, 2001. Teachers: Iain Duff, Rutherford Appleton
Laboratories, and Henk van der Vorst, Utrecht University.
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