Technical Summary: Multi-Criteria Inverse Robustness in Radiotherapy Planning Using Semidefinite Programming

Problem Statement

Radiotherapy planning is inherently a multi-criteria optimization problem involving conflicting objectives, primarily maximizing radiation dose to the tumor while minimizing dose to Organs at Risk (OARs). A critical challenge in this domain is uncertainty, arising from factors such as organ motion, setup errors, and range errors. These uncertainties are typically modeled within the dose-influence matrix ($D$), which relates radiation fluence to absorbed dose.

Traditional approaches often rely on worst-case formulations that can be overly conservative, or they require iterative computations for different fixed levels of robustness. This paper addresses the need for a quantitative approach that allows decision-makers to balance tumor dose, OAR dose, and the level of robustness adaptively. The specific problem formulated is a Multi-Criteria Optimization problem subject to interval uncertainty in the dose-influence matrix, aiming to maximize the volume of the uncertainty set (inverse robustness) while maintaining Pareto-optimality for other objectives.

Methodology

The proposed methodology transforms the radiotherapy planning problem into a tractable optimization framework through the following steps:

1. Problem Formulation and Uncertainty Modeling

• Linear Model: The base problem is formulated as a linear program (LP) where the dose vector $d$ is calculated as $d = Dx$.
• Interval Uncertainty: Uncertainty in the dose-influence matrix entries is modeled using interval matrices ($\mathbf{A} = [\underline{A}, \overline{A}]$).
• Inverse Robustness: Instead of fixing a robustness level, the authors introduce inverse robustness as an additional objective. This involves maximizing a utility function $\vartheta(W)$ (specifically a scaling parameter $r$) over the uncertainty set $W(r)$. This transforms the problem into a Quadratically Constrained Quadratic Program (QCQP). The constraint $Ax \leq b$ for all $(A,b) \in W(r)$ is converted into a quadratic constraint using the properties of strong solutions for interval systems.

2. SDP Relaxation

Since QCQPs are generally non-convex and NP-hard, the authors employ a Semidefinite Programming (SDP) relaxation:

• The QCQP is reformulated using matrix variables $Z = zz^T$, dropping the non-convex rank-1 constraint.
• The resulting problem is a convex SDP, which can be solved efficiently using interior-point solvers.
• Scalarization: To handle the multi-criteria nature, the authors use weighted sum scalarization and the $\epsilon$-constraint method to navigate the Pareto-front of the relaxed SDP.

3. Dimensionality Reduction (Clustering)

Given the large scale of radiotherapy problems (thousands of voxels), the SDP formulation would be computationally prohibitive. The authors apply a voxel clustering method:

• Similar voxels within a specific structure are grouped into "super-voxels" based on statistical analysis (mean and variance) of the dose-influence matrix rows.
• The k-means algorithm is used to cluster these voxels, and the dose-influence matrix is reduced by averaging columns within clusters.
• This significantly reduces the number of constraints and variables, making the SDP computationally tractable while preserving solution quality.

4. Reconstruction Method

A solution to the SDP ($Z_{SDP}$) is generally not a valid solution to the original QCQP because $Z_{SDP}$ is not rank-1. The authors propose a reconstruction method:

• The linear components of the SDP solution ($x^+_{SDP}, x^-_{SDP}$) are extracted.
• A new robustness parameter $r_{QCQP}$ is computed by solving a simple linear optimization problem (minimizing $-r$) subject to the constraints derived from the SDP solution.
• Theoretical Guarantees: Theorems 3.1 through 3.5 establish conditions under which the projected point is (weakly) efficient for the original QCQP. Specifically, if the projected point is efficient for the LP of a specific robustness level, it is efficient for the QCQP.

5. Pareto-Front Navigation

The authors propose a navigation workflow:

1. Compute the Pareto-front of the convex SDP relaxation.
2. Navigate the SDP front to a desired point $Z_{SDP}$.
3. Project $Z_{SDP}$ onto the feasible set of the QCQP in real-time.
4. Verify optimality using the derived theorems; if necessary, re-optimize within the fixed robustness slice (an LP) to refine the solution.

Key Results

The method was validated using a large-scale liver case from the MatRad open-source software, involving 923 variables and thousands of constraints (reduced via clustering).

• Efficiency of Pareto-Point Computation: The SDP-based approach required calculating only 19 Pareto-points to achieve a specific approximation accuracy ($\delta = 0.04$). In contrast, a traditional iterative approach (incrementing robustness levels $r$) required 163 Pareto-points to achieve the same accuracy. This represents an approximately 8-fold reduction in the number of required computations for the Pareto-front.
• Runtime Trade-off: While the SDP approach is more efficient in terms of the number of points computed, the absolute runtime was higher (46h 44m vs. 2h 31m) due to the immense size of the SDP matrix ($925 \times 925$). The authors attribute this to the current computational cost of solving large SDPs and suggest that further tuning of the clustering method could reduce runtimes.
• Solution Quality: The reconstructed solutions were found to be $\epsilon$-optimal ($\epsilon \approx 0.022$). However, the projection from the SDP to the QCQP resulted in a significant drop in the robustness parameter $r$ for many points, indicating a steep Pareto-front where high robustness comes at a high cost to other objectives.
• DVH Analysis: Dose-Volume Histograms (DVHs) demonstrated that increasing robustness leads to more homogeneous dose distributions in the target, confirming the physical relevance of the solutions.

Significance and Claims

The paper claims the following contributions and significance:

1. Integration of Inverse Robustness: The work successfully integrates the concept of inverse robustness into radiotherapy planning, allowing for the adaptive adjustment of robustness levels rather than fixing them a priori. This enables a more intuitive trade-off analysis for decision-makers.
2. Polynomial Time Solution for NP-Hard Problems: The authors demonstrate that, due to the specific structure of the radiotherapy QCQP, it is possible to find solutions in polynomial time via SDP relaxation and reconstruction, bypassing the general NP-hardness of QCQPs.
3. Interactive Decision Support: The combination of the SDP relaxation, reconstruction method, and Pareto-navigation tools allows non-mathematician decision-makers (clinicians) to interactively explore the trade-offs between tumor dose, OAR dose, and robustness. This facilitates quicker and more confident treatment planning decisions.
4. Scalability via Clustering: The application of voxel clustering is highlighted as a crucial step in making large-scale inverse robust optimization computationally feasible.

The authors remain modest regarding the runtime performance on very large problems, acknowledging that while the method reduces the number of Pareto-points significantly, the absolute computation time is currently higher than iterative methods. They suggest that future improvements in clustering and solver efficiency could bridge this gap.