An interior point constraint generation algorithm for semi-infinite optimization with healthcare application

Abstract

We propose an interior point constraint generation (IPCG) algorithm for semi-infinite linear optimization (SILO) and prove that the algorithm converges to an $ε$-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 $μ$−center after adding multiple violating constraints, and a complexity bound on the total number of con- straints that is required for the overall algorithm to converge. To illustrate the power of our algorithm in practice we implement it on sector duration optimization model arising in Gamma Knife⃝r PerfexionTM treatment planning, a highly specialized treatment for brain tumors. Using real patient data provided by Department of Radiation Oncology of Princess Margaret Hospital in Toronto, Canada, we show that our algorithm can efficiently handle problems in real-life healthcare appli- cations. We also compare our numerical results with SeDuMi and show that our IPCG method outperforms classical primal-dual interior point methods on a class of large-scale SOCO problems.