Optimization Online


A conjugate-gradient based approach for approximate solutions of quadratic programs

Fredrik Carlsson (fcar***at***kth.se)
Anders Forsgren (andersf***at***kth.se)

Abstract: 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.

Keywords: column generation, conjugate-gradient method, intensity-modulated radiation therapy, step-and-shoot delivery

Category 1: Applications -- Science and Engineering (Biomedical Applications )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: TRITA-MAT-2008-OS2, Department of Mathematics, Royal Institute of Technology, February 2008

Download: [PDF]

Entry Submitted: 02/29/2008
Entry Accepted: 02/29/2008
Entry Last Modified: 02/29/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society