The alternating simultaneous Halpern-Lions-Wittmann-Bauschke algorithm for finding the best approximation pair for two disjoint intersections of convex sets.

Given two nonempty and disjoint intersections of closed and convex subsets, we look for a best approximation pair relative to them, i.e., a pair of points, one in each intersection, attaining the minimum distance between the disjoint intersections. We propose an iterative process based on projections onto the subsets which generate the intersections. The process is inspired by the Halpern-Lions-Wittmann-Bauschke algorithm and the classical alternating process of Cheney and Goldstein, and its advantage is that there is no need to project onto the intersections themselves, a task which can be rather demanding. We prove that under certain conditions the two interlaced subsequences converge to a best approximation pair. These conditions hold, in particular, when the space is Euclidean and the subsets which generate the intersections are compact and strictly convex. Our result extends the one of Aharoni, Censor and Jiang ["Finding a best approximation pair of points for two polyhedra", Computational Optimization and Applications 71 (2018), 509-523] which considered the case of finite-dimensional polyhedra.

APPROACHES TO ITERATIVE ALGORITHMS FOR SOLVING NONLINEAR EQUATIONS WITH AN APPLICATION IN TOMOGRAPHIC ABSORPTION SPECTROSCOPY.

In this paper we propose an approach for solving systems of nonlinear equations without computing function derivatives. Motivated by the application area of tomographic absorption spectroscopy, which is a highly-nonlinear problem with variables coupling, we consider a situation where straightforward translation to a fixed point problem is not possible because the operators that represent the relevant systems of nonlinear equations are not self-mappings, i.e., they operate between spaces of different dimensions. To overcome this difficulty we suggest an "alternating common fixed points algorithm" that acts alternatingly on the different vector variables. This approach translates the original problem to a common fixed point problem for which iterative algorithms are abound and exhibits a viable alternative to translation to an optimization problem, which usually requires derivatives information. However, to apply any of these iterative algorithms requires to ascertain the conditions that appear in their convergence theorems. To circumvent the need to verify conditions for convergence, we propose and motivate a derivative-free algorithm that better suits the tomographic absorption spectroscopy problem at hand and is even further improved by applying to it the superiorization approach. This is presented along with experimental results that demonstrate our approach.

Superiorization of projection algorithms for linearly constrained inverse radiotherapy treatment planning.

Objective: We apply the superiorization methodology to the constrained intensity-modulated radiation therapy (IMRT) treatment planning problem. Superiorization combines a feasibility-seeking projection algorithm with objective function reduction: The underlying projection algorithm is perturbed with gradient descent steps to steer the algorithm towards a solution with a lower objective function value compared to one obtained solely through feasibility-seeking. Approach: Within the open-source inverse planning toolkit matRad, we implement a prototypical algorithmic framework for superiorization using the well-established Agmon, Motzkin, and Schoenberg (AMS) feasibility-seeking projection algorithm and common nonlinear dose optimization objective functions. Based on this prototype, we apply superiorization to intensity-modulated radiation therapy treatment planning and compare it with (i) bare feasibility-seeking (i.e., without any objective function) and (ii) nonlinear constrained optimization using first-order derivatives. For these comparisons, we use the TG119 water phantom, the head-and-neck and the prostate patient of the CORT dataset. Main results: Bare feasibility-seeking with AMS confirms previous studies, showing it can find solutions that are nearly equivalent to those found by the established piece-wise least-squares optimization approach. The superiorization prototype solved the linearly constrained planning problem with similar dosimetric performance to that of a general-purpose nonlinear constrained optimizer while showing smooth convergence in both constraint proximity and objective function reduction. Significance: Superiorization is a useful alternative to constrained optimization in radiotherapy inverse treatment planning. Future extensions with other approaches to feasibility-seeking, e.g., with dose-volume constraints and more sophisticated perturbations, may unlock its full potential for high performant inverse treatment planning.

Ionization detail parameters and cluster dose: a mathematical model for selection of nanodosimetric quantities for use in treatment planning in charged particle radiotherapy.

Objective. To propose a mathematical model for applying ionization detail (ID), the detailed spatial distribution of ionization along a particle track, to proton and ion beam radiotherapy treatment planning (RTP).Approach. Our model provides for selection of preferred ID parameters (Ip) for RTP, that associate closest to biological effects. Cluster dose is proposed to bridge the large gap between nanoscopicIpand macroscopic RTP. Selection ofIpis demonstrated using published cell survival measurements for protons through argon, comparing results for nineteenIp:Nk,k= 2, 3, …, 10, the number of ionizations in clusters ofkor more per particle, andFk,k= 1, 2, …, 10, the number of clusters ofkor more per particle. We then describe application of the model to ID-based RTP and propose a path to clinical translation.Main results. The preferredIpwereN4andF5for aerobic cells,N5andF7for hypoxic cells. Significant differences were found in cell survival for beams having the same LET or the preferredNk. Conversely, there was no significant difference forF5for aerobic cells andF7for hypoxic cells, regardless of ion beam atomic number or energy. Further, cells irradiated with the same cluster dose for theseIphad the same cell survival. Based on these preliminary results and other compelling results in nanodosimetry, it is reasonable to assert thatIpexist that are more closely associated with biological effects than current LET-based approaches and microdosimetric RBE-based models used in particle RTP. However, more biological variables such as cell line and cycle phase, as well as ion beam pulse structure and rate still need investigation.Significance. Our model provides a practical means to select preferredIpfrom radiobiological data, and to convertIpto the macroscopic cluster dose for particle RTP.

Dynamic string-averaging CQ-methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning.

We study a feasibility-seeking problem with percentage violation constraints (PVCs). These are additional constraints that are appended to an existing family of constraints, which single out certain subsets of the existing constraints and declare that up to a specified fraction of the number of constraints in each subset is allowed to be violated by up to a specified percentage of the existing bounds. Our motivation to investigate problems with PVCs comes from the field of radiation therapy treatment planning (RTTP) wherein the fully discretized inverse planning problem is formulated as a split feasibility problem and the PVCs give rise to nonconvex constraints. Following the CQ algorithm of Byrne (2002, Inverse Problems, Vol. 18, pp. 441-53), we develop a string-averaging CQ-method that uses only projections onto the individual sets that are half-spaces represented by linear inequalities. The question of extending our theoretical results to the nonconvex sets case is still open. We describe how our results apply to RTTP and provide a numerical example.

An Improved Method of Total Variation Superiorization Applied to Reconstruction in Proton Computed Tomography.

Previous work has shown that total variation superiorization (TVS) improves reconstructed image quality in proton computed tomography (pCT). The structure of the TVS algorithm has evolved since then and this paper investigated if this new algorithmic structure provides additional benefits to pCT image quality. Structural and parametric changes introduced to the original TVS algorithm included: (1) inclusion or exclusion of TV reduction requirement, (2) a variable number, N , of TV perturbation steps per feasibility-seeking iteration, and (3) introduction of a perturbation kernel . The structural change of excluding the TV reduction requirement check tended to have a beneficial effect for 3 ≤ N ≤ 6 and allows full parallelization of the TVS algorithm. Repeated perturbations per feasibility-seeking iterations reduced total variation (TV) and material dependent standard deviations for 3 ≤ N ≤ 6 . The perturbation kernel α , effectively equal to α = 0.5 in the original TVS algorithm, reduced TV and standard deviations as α was increased beyond α = 0.5 , but negatively impacted reconstructed relative stopping power (RSP) values for . The reductions in TV and standard deviations allowed feasibility-seeking with a larger relaxation parameter λ than previously used, without the corresponding increases in standard deviations experienced with the original TVS algorithm. This paper demonstrates that the modifications related to the evolution of the original TVS algorithm provide benefits in terms of both pCT image quality and computational efficiency for appropriately chosen parameter values.

Derivative-free superiorization with component-wise perturbations.

Superiorization reduces, not necessarily minimizes, the value of a target function while seeking constraints compatibility. This is done by taking a solely feasibility-seeking algorithm, analyzing its perturbation resilience, and proactively perturbing its iterates accordingly to steer them toward a feasible point with reduced value of the target function. When the perturbation steps are computationally efficient, this enables generation of a superior result with essentially the same computational cost as that of the original feasibility-seeking algorithm. In this work, we refine previous formulations of the superiorization method to create a more general framework, enabling target function reduction steps that do not require partial derivatives of the target function. In perturbations that use partial derivatives, the step-sizes in the perturbation phase of the superiorization method are chosen independently from the choice of the nonascent directions. This is no longer true when component-wise perturbations are employed. In that case, the step-sizes must be linked to the choice of the nonascent direction in every step. Besides presenting and validating these notions, we give a computational demonstration of superiorization with component-wise perturbations for a problem of computerized tomography image reconstruction.

Sparsity constrained split feasibility for dose-volume constraints in inverse planning of intensity-modulated photon or proton therapy.

A split feasibility formulation for the inverse problem of intensity-modulated radiation therapy treatment planning with dose-volume constraints included in the planning algorithm is presented. It involves a new type of sparsity constraint that enables the inclusion of a percentage-violation constraint in the model problem and its handling by continuous (as opposed to integer) methods. We propose an iterative algorithmic framework for solving such a problem by applying the feasibility-seeking CQ-algorithm of Byrne combined with the automatic relaxation method that uses cyclic projections. Detailed implementation instructions are furnished. Functionality of the algorithm was demonstrated through the creation of an intensity-modulated proton therapy plan for a simple 2D C-shaped geometry and also for a realistic base-of-skull chordoma treatment site. Monte Carlo simulations of proton pencil beams of varying energy were conducted to obtain dose distributions for the 2D test case. A research release of the Pinnacle 3 proton treatment planning system was used to extract pencil beam doses for a clinical base-of-skull chordoma case. In both cases the beamlet doses were calculated to satisfy dose-volume constraints according to our new algorithm. Examination of the dose-volume histograms following inverse planning with our algorithm demonstrated that it performed as intended. The application of our proposed algorithm to dose-volume constraint inverse planning was successfully demonstrated. Comparison with optimized dose distributions from the research release of the Pinnacle 3 treatment planning system showed the algorithm could achieve equivalent or superior results.

Can Linear Superiorization Be Useful for Linear Optimization Problems?

Linear superiorization considers linear programming problems but instead of attempting to solve them with linear optimization methods it employs perturbation resilient feasibility-seeking algorithms and steers them toward reduced (not necessarily minimal) target function values. The two questions that we set out to explore experimentally are (i) Does linear superiorization provide a feasible point whose linear target function value is lower than that obtained by running the same feasibility-seeking algorithm without superiorization under identical conditions? and (ii) How does linear superiorization fare in comparison with the Simplex method for solving linear programming problems? Based on our computational experiments presented here, the answers to these two questions are: "yes" and "very well", respectively.

Superiorization: an optimization heuristic for medical physics.

PURPOSE: To describe and mathematically validate the superiorization methodology, which is a recently developed heuristic approach to optimization, and to discuss its applicability to medical physics problem formulations that specify the desired solution (of physically given or otherwise obtained constraints) by an optimization criterion. METHODS: The superiorization methodology is presented as a heuristic solver for a large class of constrained optimization problems. The constraints come from the desire to produce a solution that is constraints-compatible, in the sense of meeting requirements provided by physically or otherwise obtained constraints. The underlying idea is that many iterative algorithms for finding such a solution are perturbation resilient in the sense that, even if certain kinds of changes are made at the end of each iterative step, the algorithm still produces a constraints-compatible solution. This property is exploited by using permitted changes to steer the algorithm to a solution that is not only constraints-compatible, but is also desirable according to a specified optimization criterion. The approach is very general, it is applicable to many iterative procedures and optimization criteria used in medical physics. RESULTS: The main practical contribution is a procedure for automatically producing from any given iterative algorithm its superiorized version, which will supply solutions that are superior according to a given optimization criterion. It is shown that if the original iterative algorithm satisfies certain mathematical conditions, then the output of its superiorized version is guaranteed to be as constraints-compatible as the output of the original algorithm, but it is superior to the latter according to the optimization criterion. This intuitive description is made precise in the paper and the stated claims are rigorously proved. Superiorization is illustrated on simulated computerized tomography data of a head cross section and, in spite of its generality, superiorization is shown to be competitive to an optimization algorithm that is specifically designed to minimize total variation. CONCLUSIONS: The range of applicability of superiorization to constrained optimization problems is very large. Its major utility is in the automatic nature of producing a superiorization algorithm from an algorithm aimed at only constraints-compatibility; while nonheuristic (exact) approaches need to be redesigned for a new optimization criterion. Thus superiorization provides a quick route to algorithms for the practical solution of constrained optimization problems.

From analytic inversion to contemporary IMRT optimization: radiation therapy planning revisited from a mathematical perspective.

In this paper we look at the development of radiation therapy treatment planning from a mathematical point of view. Historically, planning for Intensity-Modulated Radiation Therapy (IMRT) has been considered as an inverse problem. We discuss first the two fundamental approaches that have been investigated to solve this inverse problem: Continuous analytic inversion techniques on one hand, and fully-discretized algebraic methods on the other hand. In the second part of the paper, we review another fundamental question which has been subject to debate from the beginning of IMRT until the present day: The rotation therapy approach versus fixed angle IMRT. This builds a bridge from historic work on IMRT planning to contemporary research in the context of Intensity-Modulated Arc Therapy (IMAT).

Toward truly optimal IMRT dose distribution: inverse planning with voxel-specific penalty.

PURPOSE: To establish an inverse planning framework with adjustable voxel penalty for more conformal IMRT dose distribution as well as improved interactive controllability over the regional dose distribution of the resultant plan. MATERIALS AND METHOD: In the proposed coarse-to-fine planning scheme, a conventional inverse planning with organ specific parameters is first performed. The voxel penalty scheme is then "switched on" by allowing the prescription dose to change on an individual voxel scale according to the deviation of the actual voxel dose from the ideally desired dose. The rationale here is intuitive: when the dose at a voxel does not meet its ideal dose, it simply implies that this voxel is not competitive enough when compared with the ones that have met their planning goal. In this case, increasing the penalty of the voxel by varying the prescription can boost its competitiveness and thus improve its dose. After the prescription adjustment, the plan is re-optimized. The dose adjustment/re-optimization procedure is repeated until the resultant dose distribution cannot be improved anymore. The prescription adjustment on a finer scale can be accomplished either automatically or manually. In the latter case, the regions/voxels where a dose improvement is needed are selected visually, unlike in the automatic case where the selection is done purely based on the difference of the actual dose at a given voxel and its ideal prescription. The performance of the proposed method is evaluated using a head and neck and a prostate case. RESULTS: An inverse planning framework with the voxel-specific penalty is established. By adjusting voxel prescriptions iteratively to boost the region where large mismatch between the actual calculated and desired doses occurs, substantial improvements can be achieved in the final dose distribution. The proposed method is applied to a head and neck case and a prostate case. For the former case, a significant reduction in the maximum dose to the brainstem is achieved while the PTV dose coverage is greatly improved. The doses to other organs at risk are also reduced, ranging from 10% to 30%. For the prostate case, the use of the voxel penalty scheme also results in vast improvements to the final dose distribution. The PTV experiences improved dose uniformity and the mean dose to the rectum and bladder is reduced by as much as 15%. CONCLUSION: Introduction of the spatially non-uniform and adjustable prescription provides room for further improvements of currently achievable dose distributions and equips the planner with an effective tool to modify IMRT dose distributions interactively. The technique is easily implementable in any existing inverse planning platform, which should facilitate clinical IMRT planning process and, in future, off-line/on-line adaptive IMRT.

The Split Common Fixed Point Problem for Directed Operators.

We propose the split common fixed point problem that requires to find a common fixed point of a family of operators in one space whose image under a linear transformation is a common fixed point of another family of operators in the image space. We formulate and analyze a parallel algorithm for solving this split common fixed point problem for the class of directed operators and note how it unifies and generalizes previously discussed problems and algorithms.

A Note on the Behavior of the Randomized Kaczmarz Algorithm of Strohmer and Vershynin.

In a recent paper by T. Strohmer and R. Vershynin ["A Randomized Kaczmarz Algorithm with Exponential Convergence", Journal of Fourier Analysis and Applications, published online on April 25, 2008] a "randomized Kaczmarz algorithm" is proposed for solving systems of linear equations [Formula: see text] . In that algorithm the next equation to be used in an iterative Kaczmarz process is selected with a probability proportional to ‖a(i)‖ (2). The paper illustrates the superiority of this selection method for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values.In this note we point out that the reported success of the algorithm of Strohmer and Vershynin in their numerical simulation depends on the specific choices that are made in translating the underlying problem, whose geometrical nature is "find a common point of a set of hyperplanes", into a system of algebraic equations. If this translation is carefully done, as in the numerical simulation provided by Strohmer and Vershynin for the reconstruction of a bandlimited function from its nonuniformly spaced sampling values, then indeed good performance may result. However, there will always be legitimate algebraic representations of the underlying problem (so that the set of solutions of the system of algebraic equations is exactly the set of points in the intersection of the hyperplanes), for which the selection method of Strohmer and Vershynin will perform in an inferior manner.

On the String Averaging Method for Sparse Common Fixed Points Problems.

We study the common fixed point problem for the class of directed operators. This class is important because many commonly used nonlinear operators in convex optimization belong to it. We propose a definition of sparseness of a family of operators and investigate a string-averaging algorithmic scheme that favorably handles the common fixed points problem when the family of operators is sparse. The convex feasibility problem is treated as a special case and a new subgradient projections algorithmic scheme is obtained.

General Algorithmic Frameworks for Online Problem.

We study general algorithmic frameworks for online learning tasks. These include binary classification, regression, multiclass problems and cost-sensitive multiclass classification. The theorems that we present give loss bounds on the behavior of our algorithms which depend on general conditions on the iterative step sizes.

On The Behavior of Subgradient Projections Methods for Convex Feasibility Problems in Euclidean Spaces.

We study some methods of subgradient projections for solving a convex feasibility problem with general (not necessarily hyperplanes or half-spaces) convex sets in the inconsistent case and propose a strategy that controls the relaxation parameters in a specific self-adapting manner. This strategy leaves enough user-flexibility but gives a mathematical guarantee for the algorithm's behavior in the inconsistent case. We present numerical results of computational experiments that illustrate the computational advantage of the new method.

Projections Onto Super-Half-Spaces for Monotone Variational Inequality Problems in Finite-Dimensional Space.

The variational inequality problem (VIP) is considered here. We present a general algorithmic scheme which employs projections onto hyperplanes that separate balls from the feasible set of the VIP instead of projections onto the feasible set itself. Our algorithmic scheme includes the classical projection method and Fukushima's subgradient projection method as special cases.

On Linear Infeasibility Arising in Intensity-Modulated Radiation Therapy Inverse Planning.

Intensity-modulated radiation therapy (IMRT) gives rise to systems of linear inequalities, representing the effects of radiation on the irradiated body. These systems are often infeasible, in which case one settles for an approximate solution, such as an {α, ß}-relaxation, meaning that no more than α percent of the inequalities are violated by no more than ß percent. For real-world IMRT problems, there is a feasible {α, ß}-relaxation for sufficiently large α, ß > 0, however large values of these parameters may be unacceptable medically.The {α, ß}-relaxation problem is combinatorial, and for given values of the parameters can be solved exactly by Mixed Integer Programming (MIP), but this may be impractical because of problem size, and the need for repeated solutions as the treatment progresses.As a practical alternative to the MIP approach we present a heuristic non-combinatorial method for finding an approximate relaxation. The method solves a Linear Program (LP) for each pair of values of the parameters {α, ß} and progresses through successively increasing values until an acceptable solution is found, or is determined non-existent. The method is fast and reliable, since it consists of solving a sequence of LP's.

A unified approach for inversion problems in intensity-modulated radiation therapy.

We propose and study a unified model for handling dose constraints (physical dose, equivalent uniform dose (EUD), etc) and radiation source constraints in a single mathematical framework based on the split feasibility problem. The model does not impose on the constraints an exogenous objective (merit) function. The optimization algorithm minimizes a weighted proximity function that measures the sum of the squares of the distances to the constraint sets. This guarantees convergence to a feasible solution point if the split feasibility problem is consistent (i.e., has a solution), or, otherwise, convergence to a solution that minimally violates the physical dose constraints and EUD constraints. We present computational results that demonstrate the validity of the model and the power of the proposed algorithmic scheme.