Pareto Navigation
– interactive multiobjective
optimisation and its application
in radiotherapy planning
Vom Fachbereich Mathematik
der Universit¨at Kaiserslautern
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
(Doctor rerum naturalium, Dr. rer. nat.)
genehmigte
Dissertation
von
Michael Monz
Juni 2006
Erstgutachter: PD Dr. habil. Karl-Heinz Kufer¨
Zweitgutachter: Prof. Dr. Johannes Jahn
Datum der Disputation: 6. November 2006
D 386Dedicatedtomyparentsfor
their support throughout my life.Acknowledgements
This work was done with the financial support of the Department Optimi-
sation of the Fraunhofer Institute for Industrial Mathematics (ITWM).
I have had the pleasure of working together with a lot of people in the
radiotherapy projects over the last five years. Thus, there are many people
that I am indebted to.
First of all I would like to thank my supervisor Karl-Heinz Kufe¨ r for his sup-
port, his open-mindedness and the resulting freedom I enjoyed in organising
my work, and last but not least for the friendly contact.
The second thanks goes to my colleagues in the radiotherapy group. To
Alexander Scherrer for being a likeable room mate, to Phil Su¨ss for good
vibes, to Fernando Alonso for silently clearing trouble and to Ahmed Saher
Azizi Sultan for sharing ‘Monday morning feelings’. A thanks also goes to
Anton Winterfeld, Volker Maag and Mattias Nissler for outstanding helper
work.
A big thanks goes to Claudia Meißner, Bianca Steinmetz and Juliette Arm-
brecht for the best time I ever had at work.
Furthermore, I would like to thank the other members of Optimisation de-
partment for a amiable working atmosphere.
The amazing user interface for the navigator was designed by Juliette Arm-
brecht and programmed by Fernando Alonso for which I owe them a big
thanks.
I would like to thank our cooperation partners in the German Cancer Re-
search Centre and in particular Christian Thieke for unremitting input.
Besides the cooperation I would also like to thank our cooperation partners
Thomas Bortfeld, Alex Trofimov, Tarek Halabi and David Craft for the
Boston experience.
A thanks also goes to Edwin Romeijn and Jim Dempsey for a memorable
cruise.
I am indebted to Dr. Burkhard Strehl and Prof. Dr. Ralf Korn for good
advice and help. I also would like to thank Teresa Melo for good advice and
her bright manner.Regarding this thesis I owe a big thanks to Roland Fiat, Phil Suss¨ and
Alexander Scherrer for proof-reading my drafts.
Finally, I would like to express deep gratitude to my family for their support.Abstract
In this work a novel interactive multiobjective optimisation method is intro-
duced. Distinct features of the method are the use of very few parameters to
steer the exploration and the explicit manipulation of the underlying partial
order during decision making to control the partial tradeoffs.
The thesis starts with an extensive introduction of the topic that sketches
the main results of the work.
Then, a framework for reference point based scalarisation functions com-
patible with a partial order given by an ordering cone is introduced. The
framework is then analysed, so that valuable properties of the resulting
scalarisation function are linked to properties of the so called cone scalar-
ising function. Among others, efficiency of the outcomes, reachability of
efficient points, convexity of the scalarisation function and semi-continuity
with respect to the reference point are investigated.
Then, Pareto navigation the novel interactive multiobjective optimisation
method is proposed and analysed. It features three mechanisms that ma-
nipulate the upper bounds, the current solution and the bounds on the
partial tradeoffs, respectively. The first two mechanisms just need one ob-
jective and one parameter and the third mechanism just two objectives and
one parameter as input.
Mathematical models for the different mechanisms are introduced and dis-
cussed in detail. It is shown that among the set of possible solutions – which
depends on the chosen cone scalarising function – every efficient outcome
can be reached in a fixed number of steps and that the change of the current
solution is upper semicontinuous with respect to the reference point. The
potential non-efficiency of the outcomes is analysed and demonstrated on a
critical example.
Furthermore, the application of the method as a second phase in a two
phase approach is described. Here, the focus is on the efficient use of the
pre-computed data, so as to turn the mechanisms into real-time procedures.
Finally, the extension of the method to nonconvex cases is presented.The last major topic of the thesis is the application of Pareto navigation to
intensity modulated radiotherapy (IMRT). First, the IMRT planning prob-
lem and its inherent multiobjective character are described. Then, some
modelling options are presented and algorithms and heuristic approaches to
the calculation of the phase one approximation discussed. Finally, the clin-
ical prototype is presented and its graphical user interface visualising the
solution and outcome set information and offering direct, graphical access
to the mechanisms is described.
The thesis ends with a outlook that lists interesting aspects or possible
extensions that would deserve further attention.Contents
1 Introduction 3
2 Achievement scalarising with cones 11
2.1 Themultiobjectiveoptimisationproblem... ... .... .. 13
2.2 Orderingcones ... ... .... ... .... ... .... .. 15
2.3 Conescalarisingfunctions .... ... .... ... .... .. 25
2.4 Conescalarisingoutcomes .... ... .... ... .... .. 37
2.5 Dependenceonreferencepoint . ... .... ... .... .. 46
2.6 Reachability of outcomes . .... ... .... ... .... .. 61
2.7 Example–thePascoletti-Serafiniapproach . ... .... .. 66
2.8 Summary ... ... ... .... ... .... ... .... .. 70
3 Pareto navigation 73
3.1 Interactivemultiobjectiveoptimisation .... ... .... .. 73
3.2 MechanismsofParetonavigation ... .... ... .... .. 75
3.3 Therestrictionmechanism.... ... .... ... .... .. 78
3.3.1 Estimatingtheidealpoint... .... ... .... .. 79
3.3.2 Estimatingthenadirpoint .. .... ... .... .. 81
3.4 Theselectionmechanism. .... ... .... ... .... .. 83
3.4.1 Modelling the selection mechanism . . . . . .... .. 84
3.4.2 Criticalexample . .... ... .... ... .... .. 85
3.4.3 Resultsoftheselectionmechanism .. ... .... .. 87
3.5 Thediscountingmechanism ... ... .... ... .... .. 97
3.6 Two-phaseapproachtoParetonavigation . . ... .... .. 104
3.6.1 Simplifyingtheproblemformulations ... .... .. 105
3.6.2 Updateoftheplanninghorizon.... ... .... .. 107
3.6.3 Selectionanddiscountingmechanism. ... .... .. 109
3.6.4 AnimplementationwithPascoletti-Serafini .... .. 112
3.7 Paretonavigationfornonconvexproblems . . ... .... .. 114
3.8 Summary ... ... ... .... ... .... ... .... .. 116
1