Change search
ReferencesLink to record
Permanent link

Direct link
An algorithm for approximating convex Pareto surfaces based on dual techniques
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0002-6252-7815
2013 (English)In: INFORMS journal on computing, ISSN 1091-9856, Vol. 25, no 2, 377-393 p.Article in journal (Refereed) Published
Abstract [en]

We consider the problem of approximating Pareto surfaces of convex multicriteria optimization problems by a discrete set of points and their convex combinations. Finding the scalarization parameters that optimally limit the approximation error when generating a single Pareto optimal solution is a nonconvex optimization problem. This problem can be solved by enumerative techniques but at a cost that increases exponentially with the number of objectives. We present an algorithm for solving the Pareto surface approximation problem that is practical with 10 or less conflicting objectives, motivated by an application to radiation therapy optimization. Our enumerative scheme is, in a sense, dual to a family of previous algorithms. The proposed technique retains the quality of the best previous algorithm in this class while solving fewer subproblems. A further improvement is provided by a procedure for discarding subproblems based on reusing information from previous solves. The combined effect of the enhancements is empirically demonstrated to reduce the computational expense of solving the Pareto surface approximation problem by orders of magnitude. For problems where the objectives have positive curvature, an improved bound on the approximation error is demonstrated using transformations of the initial objectives with strictly increasing and concave functions.

Place, publisher, year, edition, pages
2013. Vol. 25, no 2, 377-393 p.
Keyword [en]
multicriteria optimization, Pareto optimality, sandwich algorithms, radiation therapy, Hausdorff distance
National Category
Computational Mathematics
URN: urn:nbn:se:kth:diva-122665DOI: 10.1287/ijoc.1120.0508ISI: 000317966700014ScopusID: 2-s2.0-84877962755OAI: diva2:623181
Swedish Research Council

QC 20130527

Available from: 2013-05-24 Created: 2013-05-24 Last updated: 2013-06-04Bibliographically approved
In thesis
1. Multicriteria optimization for managing tradeoffs in radiation therapy treatment planning
Open this publication in new window or tab >>Multicriteria optimization for managing tradeoffs in radiation therapy treatment planning
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Treatment planning for radiation therapy inherently involves tradeoffs, such as between tumor control and normal tissue sparing, between time-efficiency and dose quality, and between nominal plan quality and robustness. The purpose of this thesis is to develop methods that can facilitate decision making related to such tradeoffs. The main focus of the thesis is on multicriteria optimization methods where a representative set of treatment plans are first calculated and the most appropriate plan contained in this representation then selected by the treatment planner through continuous interpolation between the precalculated alternatives. These alternatives constitute a subset of the set of Pareto optimal plans, meaning plans such that no criterion can be improved without a sacrifice in another.

Approximation of Pareto optimal sets is first studied with respect to fluence map optimization for intensity-modulated radiation therapy. The approximation error of a discrete representation is minimized by calculation of points one at the time at the location where the distance between an inner and outer approximation of the Pareto set currently attains its maximum. A technique for calculating this distance that is orders of magnitude more efficient than the best previous method is presented. A generalization to distributed computational environments is also proposed.

Approximation of Pareto optimal sets is also considered with respect to direct machine parameter optimization. Optimization of this form is used to calculate representations where any interpolated treatment plan is directly deliverable. The fact that finite representations of Pareto optimal sets have approximation errors with respect to Pareto optimality is addressed by a technique that removes these errors by a projection onto the exact Pareto set. Projections are also studied subject to constraints that prevent the dose-volume histogram from deteriorating.

Multicriteria optimization is extended to treatment planning for volumetric-modulated arc therapy and intensity-modulated proton therapy. Proton therapy plans that are robust against geometric errors are calculated by optimization of the worst case outcome. The theory for multicriteria optimization is extended to accommodate this formulation. Worst case optimization is shown to be preferable to a previous more conservative method that also protects against uncertainties which cannot be realized in practice.

Abstract [sv]

En viktig aspekt av planering av strålterapibehandlingar är avvägningar mellan behandlingsmål vilka står i konflikt med varandra. Exempel på sådana avvägningar är mellan tumörkontroll och dos till omkringliggande frisk vävnad, mellan behandlingstid och doskvalitet, och mellan nominell plankvalitet och robusthet med avseende på geometriska fel. Denna avhandling syftar till att utveckla metoder som kan underlätta beslutsfattande kring motstridiga behandlingsmål. Primärt studeras en metod för flermålsoptimering där behandlingsplanen väljs genom kontinuerlig interpolation över ett representativt urval av förberäknade alternativ. De förberäknade behandlingsplanerna utgör en delmängd av de Paretooptimala planerna, det vill säga de planer sådana att en förbättring enligt ett kriterium inte kan ske annat än genom en försämring enligt ett annat.

Beräkning av en approximativ representation av mängden av Paretooptimala planer studeras först med avseende på fluensoptimering för intensitetsmodulerad strålterapi. Felet för den approximativa representationen minimeras genom att innesluta mängden av Paretooptimala planer mellan inre och yttre approximationer. Dessa approximationer förfinas iterativt genom att varje ny plan genereras där avståndet mellan approximationerna för tillfället är som störst. En teknik för att beräkna det maximala avståndet mellan approximationerna föreslås vilken är flera storleksordningar snabbare än den bästa tidigare kända metoden. En generalisering till distribuerade beräkningsmiljöer föreslås även.

Approximation av mängden av Paretooptimala planer studeras även för direkt maskinparameteroptimering, som används för att beräkna representationer där varje interpolerad behandlingsplan är direkt levererbar. Det faktum att en ändlig representation av mängden av Paretooptimala lösningar har ett approximationsfel till Paretooptimalitet hanteras via en metod där en interpolerad behandlingsplan projiceras på Paretomängden. Projektioner studeras även under bivillkor som förhindrar att den interpolerade planens dos-volym histogram kan försämras.

Flermålsoptimering utökas till planering av rotationsterapi och intensitetsmodulerad protonterapi. Protonplaner som är robusta mot geometriska fel beräknas genom optimering med avseende på det värsta möjliga utfallet av de föreliggande osäkerheterna. Flermålsoptimering utökas även teoretiskt till att innefatta denna formulering. Nyttan av värsta fallet-optimering jämfört med tidigare mer konservativa metoder som även skyddar mot osäkerheter som inte kan realiseras i praktiken demonstreras experimentellt.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2013. xvi, 54 p.
Trita-MAT. OS, ISSN 1401-2294 ; 13:07
Optimization, multicriteria optimization, robust optimization, Pareto optimality, Pareto surface approximation, Pareto surface navigation, intensity-modulated radiation therapy, volumetric-modulated arc therapy, intensity-modulated proton therapy, Optimering, flermålsoptimering, robust optimering, Paretooptimalitet, Paretofrontsapproximation, Paretofrontsnavigering, intensitetsmodulerad strålterapi, rotationsterapi, intensitetsmodulerad protonterapi
National Category
Computational Mathematics
urn:nbn:se:kth:diva-122663 (URN)978-91-7501-790-7 (ISBN)
Public defence
2013-06-14, F3, Lindstedtsvägen 26, KTH, Stockholm, 10:00 (English)

QC 20130527

Available from: 2013-05-27 Created: 2013-05-24 Last updated: 2013-05-28Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Bokrantz, RasmusForsgren, Anders
By organisation
Optimization and Systems Theory
In the same journal
INFORMS journal on computing
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 444 hits
ReferencesLink to record
Permanent link

Direct link