Change search
ReferencesLink to record
Permanent link

Direct link
A conjugate-gradient based approach for approximate solutions of quadratic programs
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
(English)In: Annals of Operations Research, ISSN 0254-5330, E-ISSN 1572-9338Article in journal (Refereed) Submitted
Abstract [en]

This paper deals with numerical behaviour and convergence properties of a recently presented column generation approach for optimization of so called step-and-shoot radiotherapy treatment plans. The approach and variants of it have been reported to be efficient in practice, finding near-optimal solutions by generating only a low number of columns. The impact of different restrictions on the columns in a column generation method is studied, and numerical results are given for quadratic programs corresponding to three patient cases. In particular, it is noted that with a bound on the two-norm of the columns, the method is equivalent to the conjugate-gradient method. Further, the above-mentioned column generation approach for radiotherapy is obtained by employing a restriction based on the infinity-norm and non-negativity. The column generation method has weak convergence properties if restricted to generating feasible step-and-shoot plans, with a "tailing-off" effect for the objective values. However, the numerical results demonstrate that, like the conjugate-gradient method, a rapid decrease of the objective value is obtained in the first few iterations. For the three patient cases, the restriction on the columns to generate feasible step-and-shoot plans has small effect on the numerical efficiency.

Keyword [en]
column generation; conjugate-gradient method; intensity-modulated radiation therapy; step-and-shoot delivery
National Category
Computational Mathematics
URN: urn:nbn:se:kth:diva-8186OAI: diva2:13440
QC 20100709Available from: 2008-04-03 Created: 2008-04-03 Last updated: 2012-03-26Bibliographically approved
In thesis
1. Utilizing Problem Structure in Optimization of Radiation Therapy
Open this publication in new window or tab >>Utilizing Problem Structure in Optimization of Radiation Therapy
2008 (English)Doctoral thesis, comprehensive summary (Other scientific)
Abstract [en]

In this thesis, optimization approaches for intensity-modulated radiation therapy are developed and evaluated with focus on numerical efficiency and treatment delivery aspects. The first two papers deal with strategies for solving fluence map optimization problems efficiently while avoiding solutions with jagged fluence profiles. The last two papers concern optimization of step-and-shoot parameters with emphasis on generating treatment plans that can be delivered efficiently and accurately. In the first paper, the problem dimension of a fluence map optimization problem is reduced through a spectral decomposition of the Hessian of the objective function. The weights of the eigenvectors corresponding to the p largest eigenvalues are introduced as optimization variables, and the impact on the solution of varying p is studied. Including only a few eigenvector weights results in faster initial decrease of the objective value, but with an inferior solution, compared to optimization of the bixel weights. An approach combining eigenvector weights and bixel weights produces improved solutions, but at the expense of the pre-computational time for the spectral decomposition. So-called iterative regularization is performed on fluence map optimization problems in the second paper. The idea is to find regular solutions by utilizing an optimization method that is able to find near-optimal solutions with non-jagged fluence profiles in few iterations. The suitability of a quasi-Newton sequential quadratic programming method is demonstrated by comparing the treatment quality of deliverable step-and-shoot plans, generated through leaf sequencing with a fixed number of segments, for different number of bixel-weight iterations. A conclusion is that over-optimization of the fluence map optimization problem prior to leaf sequencing should be avoided. An approach for dynamically generating multileaf collimator segments using a column generation approach combined with optimization of segment shapes and weights is presented in the third paper. Numerical results demonstrate that the adjustment of leaf positions improves the plan quality and that satisfactory treatment plans are found with few segments. The method provides a tool for exploring the trade-off between plan quality and treatment complexity by generating a sequence of deliverable plans of increasing quality. The final paper is devoted to understanding the ability of the column generation approach in the third paper to find near-optimal solutions with very few columns compared to the problem dimension. The impact of different restrictions on the generated columns is studied, both in terms of numerical behaviour and convergence properties. A bound on the two-norm of the columns results in the conjugate-gradient method. Numerical results indicate that the appealing properties of the conjugate-gradient method on ill-conditioned problems are inherited in the column generation approach of the third paper.

Place, publisher, year, edition, pages
Stockholm: KTH, 2008. xi, 32 p.
Trita-MAT. OS, ISSN 1401-2294 ; 08/OS/03
Optimization, intensity-modulated radiation therapy, conjugate-gradient method, step-and-shoot delivery, column generation, quasi-Newton method, regularization, sequential quadratic programming
National Category
Computational Mathematics
urn:nbn:se:kth:diva-4689 (URN)978-91-7178-920-4 (ISBN)
Public defence
2008-04-25, F3, Lindstedtsvägen 26, Stockholm, 10:00
QC 20100709Available from: 2008-04-03 Created: 2008-04-03 Last updated: 2010-07-09Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Carlsson, FredrikForsgren, Anders
By organisation
Optimization and Systems Theory
In the same journal
Annals of Operations Research
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

Total: 62 hits
ReferencesLink to record
Permanent link

Direct link