Interior Point Methods Can Exploit Structure of Convex Piecewise Linear Functions with Application in Radiation Therapy
研究了凸分段线性函数在优化中引入的辅助变量如何产生块对角加低秩结构，并推导了利用该结构的内点法公式。在Netlib中36%的案例可检测到该结构，在放射治疗逆规划问题中比CPLEX快一个数量级，且剂量分布更优。
Auxiliary variables are often used to model a convex piecewise linear function in the framework of linear optimization. This work shows that such variables yield a block diagonal plus low rank structure in the reduced KKT system of the dual problem. We show how the structure can be detected efficiently and derive the linear algebra formulas for an interior point method which exploits such a structure. The structure is detected in 36% of the cases in Netlib. Numerical results on the inverse planning problem in radiation therapy show an order of magnitude speed-up compared to the state-of-the-art interior point solver CPLEX and considerable improvements in dose distribution compared to current algorithms.