Groupe d’études et de recherche en analyse des décisions

Interior Point Constraint Generation Algorithm for Semi-Infinite Optimization with a Radiation Therapy Treatment Application

Tamás Terlaky Lehigh University, États-Unis

A linear approximation of a convex optimization problem is generated by calling an oracle to approximate the set of feasible and the set of optimal solutions. The approximation is updated at each iterations. Such an approach can generally be used to solve any convex optimization problems given explicitly or inplicitly by piecewise differentiable fuctions. We propose an interior point constraint generation (IPCG) algorithm for semi-infinite linear optimization (SILO) and prove that the algorithm converges to an epsilon-solution of SILO after a finite number of constraints is generated.

We derive a complexity bound on the number of Newton steps needed to approach the updated mu-center after adding multiple violated constraints, and a complexity bound on the total number of constraints that is required for the overall algorithm to converge.

We implement our algorithm to solve a sector duration optimization model arising in Leksell Gamma Knife r° Perfexion (TM) treatment planning (Elekta, Stockholm Sweden), a highly specialized treatment for brain tumors. Using real patient data provided by the Department of Radiation Oncology at Princess Margaret Hospital in Toronto, we show that our algorithm can efficiently handle problems in real-life healthcare applications. Comparing our results with that of a projected gradient method, we show that our IPCG algorithm obtains a more accurate solution, and is, on average, 7 times faster. We also compare our numerical results with SeDuMi, and show that our IPCG method outperforms classical primal-dual interior point methods on sector duration optimization problems.

This is joint work with Dionne Aleman, Hamid Ghaffary (U. of Toronto) and Mohammad R. Oskooorouchi (California State U. San Marcos).