Subgradient optimization methods in integer programming with an application to a radiation therapy problem [Elektronische Ressource] / Berhanu Guta

Sujets

• Mathematics
• Gesundheit

Informations

• Publié par: technische_universitat_kaiserslautern
• Publié le: 01 janvier 2003
• Nombre de lectures: 25
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Berhanu Guta
Subgradient Optimization Methods in
Integer Programming with an Application to a
Radiation Therapy Problem
Vom Fachbereich Mathematik
der Universit¨at Kaiserslautern
genehmigte
Dissertation
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
(Doctor rerum naturalium, Dr. rer. nat.)
Gutachter: Prof. Dr. Horst W. Hamacher
Prof. Dr. Francesco Maffioli
Datum der Disputation: 17. September 2003
D 386iiiii
Acknowledgments
I would like to express my sincere gratitude to my supervisor Prof. Dr. Horst W.
Hamacher for making this research work possible. His guidance, valuable suggestions
and great support has been a good influence for this work to be successfully done. I
want to express my thanks also to Prof. Dr. Francesco Maffioli for his good will and
effort to read and evaluate my thesis. I am indebted also to Prof. Dr. Helmut Neunzert
who not only gave me the chance to come to Germany but also genuinely and fatherly
concerned about my personal life, in general, and academic work, in particular. I would
also like to thank Prof. Dr. Dietmar Schweigert for his support during the beginning
of my Ph.D studies.
Many thanks go to all my colleagues at Optimization Group, AGHamacher, in the Uni-
versity of Kaiserslautern for the good working atmosphere as well as for their friendly
and unreserved support which have always made me to feel like being in my family at
home.
I am also very grateful to DAAD (German Academic Exchange Service) for the finan-
cial support.
Finally, special thanks to my wife Asefash Geleta for her various supports and encour-
agements. I would like to thank also my son Naol and my daughter Hana for their
patience and understanding while I was preparing the thesis.ivCONTENTS
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Lagrangian Relaxation and Duality . . . . . . . . . . . . . . . . . . . . 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Properties of the Dual Problem and Dual Function . . . . . . . . 12
3. Subgradient Optimization Methods . . . . . . . . . . . . . . . . . . . . 27
3.1 The Pure Subgradient Method . . . . . . . . . . . . . . . . . . . . 29
3.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 The Pure Subgradient Algorithm . . . . . . . . . . . . . . 33
3.2 The Deflected Subgradient Method . . . . . . . . . . . . . . . . . 44
3.3 Conditional Subgradient Method . . . . . . . . . . . . . . . . . . 55
3.3.1 Conditional Subgradient Algorithm . . . . . . . . . . . . . 62
3.3.2 Conditional Subgradient Procedure for the Lagrangian Dual 67
3.4 Bundle Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4. A Zigzag-Free Subgradient Procedure . . . . . . . . . . . . . . . . . . 75
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2 A Generic Hybrid Subgradient Procedure . . . . . . . . . . . . . 76
4.3 Hybrid Subgradient Procedure for the Lagrangian Dual . . . . . . 84
5. Primal Solutions Within the Subgradient Procedures . . . . . . . . . . 87
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87Contents vi
5.2 The Volume Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.1 Similarities with the Bundle Method . . . . . . . . . . . . 101
5.3 ErgodicPrimalSolutionwithintheConditionalSubgradientMethod103
6. Minimization of Treatment Time of a Radiation Therapy . . . . . . . 111
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2 Decomposition of Intensity Matrix into Segments . . . . . . . . . 116
6.3 The Hamacher-Boland Network Flow Model
of the MLC Problem . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.4 Minimizing Total Delivery Time for Radiation Therapy . . . . . 131
6.4.1 Max-Level Halving Algorithm . . . . . . . . . . . . . . . . 131
6.4.2 Worst-Case Bound on the Number of Segments . . . . . . 136
6.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.5.1 Some Preprocessing Techniques . . . . . . . . . . . . . . . 142
6.5.2 Numerical Tests . . . . . . . . . . . . . . . . . . . . . . . 146
7. Conclusions and Future Research . . . . . . . . . . . . . . . . . . . . . 151
Bibilography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1551. INTRODUCTION
The focus of this thesis is on the subgradient optimization methods which are
used to solve nonsmooth optimization problems. We are particularly concerned
withsolvingintegerprogrammingproblemsusingthemethodologyofLagrangian
relaxation and dualization. This involves the problem of maximization of a La-
grangian dual function which is concave but nondifferentiable. The subgradient
methods are suitable to solve such a problem since these procedures can make
use of the concavity of the objective function. The goal of the thesis is to employ
the subgradient optimization techniques to solve a large-scale practical radiation
therapy planning problem which involves certain difficult constraints but imbed-
ded in some tractable nice mathematical structures.
Integer optimization problems are generally difficult to solve because of their
inherent combinatorial complexity. Unfortunately, almost all important generic
classes of integer programming problems are NP-hard. Furthermore, many in-
teger programming problems of practical relevance are of large-size. Hence, the
scale at which these problems arise in applications and the explosive exponential
complexity of their search spaces preclude the use of simplistic enumeration and
search techniques.
Therefore, inordertosolve practicalintegerprogrammingproblems wemayneed
to resort to approximation schemes and problem specific algorithms which can
exploit some special structures of the problem at hand. Indeed, many practically
relevant integer programming problems are usually composed ofsome nice math-
ematicalstructuresadjoinedwithcertaincomplicatingconditions(orconstraints)1. Introduction 2
which make any solution procedure difficult. The method of Lagrangian relax-
ation lifts these complicating constraints and makes use of the special structure
to solve the relaxed problem. This produces a lower bound for a minimization
problem. At least a good approximate solution or the best (tight) bound can
be obtained by subgradient optimization methods where a subgradient vector is
obtained by minimizing the relaxed primal problem and the dual variables are
updated iteratively along the direction of this subgradient vector. This approach
has received recognition and is proven to be a very useful tool to solve various
difficult discrete optimization problems since the first successful works of Held
and Karp in 1970’s ([44], [45]). They used Lagrangian relaxation approach based
on minimum spanning trees to devise a successful algorithm for the travelling
salesman problem.
In Chapter 2, we will review some important techniques in the approach of the
Lagrangian relaxation of integer programming problems and formulate the re-
lated Lagrangian dual problem. We also discuss properties of the dual problem,
optimality conditions as well as the general structure of the dual objective func-
tion.
A major challenge in the method of Lagrangian relaxation of a minimization
problem of an integer programming problem is to maximize effectively the La-
grangian dual function which is defined only implicitly and is nondifferentiable,
concave, andpiecewise affine. Thesubgradientmethodisfrequentlyusedtosolve
such problems since this method does not demand differentiability. In fact, it is
an iterative procedure which searches for an optimal solution using the direction
ofthe gradient vector at each point where the gradient ofthe function exists; but
replaces thegradientvectorbyasubgradient vectoratapointwherethegradient
does not exist. The subgradient of a function at a point is generally not unique
and the functional value of the objective function may not be improved along a
given subgradient direction. Consequently, line search techniques as in the gra-1. Introduction 3
dient methods of the case of minimizing smooth functions can not be suitable for
subgradient methods. Hence, subgradient methods are not directly analogous to
the gradient methods of smooth nonlinear optimization problems. Depending on
the particular strategy of determining a step direction, there are different kinds
of subgradient procedures which differ in their performance. These procedures
will be discussed in detail.
In Chapter 3, different variants of subgradient methods will be investigated and
a unified presentation of the methods will be given. Their optimality conditions
and convergency properties will be also analyzed. The central drawback of this
methods is that their convergence is usually slow which is mainly caused by the
so called zigzagging phenomena. The slow convergence is a crucial problem, par-
ticularly, in view of the need to solve large-scale problems. Various versions of
subgradient methods such as the modified subgradient method [21], the average
direction strategy [77], and conditional subgradient methods [53] have been de-
veloped with the intent t