A Dual Algorithm For Approximating Pareto Sets in Convex Multi-Criteria Optimization

We consider the problem of approximating the Pareto set of convex multi-criteria optimization problems by a discrete set of points and their convex combinations. Finding the scalarization parameters that maximize the improvement in bound on the approximation error when generating a single Pareto optimal solution is a nonconvex optimization problem. This problem is solvable by … Read more

Minimax optimization for handling range and setup uncertainties in proton therapy

Purpose: Intensity modulated proton therapy (IMPT) is sensitive to errors, mainly due to high stopping power dependency and steep beam dose gradients. Conventional margins are often insufficient to ensure robustness of treatment plans. In this article, a method is developed that takes the uncertainties into account during the plan optimization. Methods: Dose contributions for a … Read more

A sufficiently exact inexact Newton step based on reusing matrix information

Newton’s method is a classical method for solving a nonlinear equation $F(z)=0$. We derive inexact Newton steps that lead to an inexact Newton method, applicable near a solution. The method is based on solving for a particular $F'(z_{k’})$ during $p$ consecutive iterations $k=k’,k’+1,\dots,k’+p-1$. One such $p$-cycle requires $2^p-1$ solves with the matrix $F'(z_{k’})$. If matrix … Read more

An elementary proof of optimality conditions for linear programming

We give an elementary proof of optimality conditions for linear programming. The proof is direct, built on a straightforward classical perturbation of the constraints, and does not require either the use of Farkas’ lemma or the use of the simplex method. Citation Technical Report TRITA-MAT-2008-OS6, Department of Mathematics, Royal Institute of Technology (KTH), SE-100 44 … Read more

A conjugate-gradient based approach for approximate solutions of quadratic programs

This paper deals with numerical behaviour and convergence properties of a recently presented column generation approach for optimization of so called step-and-shoot radiotherapy treatment plans. The approach and variants of it have been reported to be efficient in practice, finding near-optimal solutions by generating only a low number of columns. The impact of different restrictions … Read more

On the behavior of the conjugate-gradient method on ill-conditioned problems

We study the behavior of the conjugate-gradient method for solving a set of linear equations, where the matrix is symmetric and positive definite with one set of eigenvalues that are large and the remaining are small. We characterize the behavior of the residuals associated with the large eigenvalues throughout the iterations, and also characterize the … Read more

On warm starts for interior methods

An appealing feature of interior methods for linear programming is that the number of iterations required to solve a problem tends to be relatively insensitive to the choice of initial point. This feature has the drawback that it is difficult to design interior methods that efficiently utilize information from an optimal solution to a “nearby” … Read more

Iterative Solution of Augmented Systems Arising in Interior Methods

Iterative methods are proposed for certain augmented systems of linear equations that arise in interior methods for general nonlinear optimization. Interior methods define a sequence of KKT equations that represent the symmetrized (but indefinite) equations associated with Newton’s method for a point satisfying the perturbed optimality conditions. These equations involve both the primal and dual … Read more

Characterization of the limit point of the central path in semidefinite programming

In linear programming, the central path is known to converge to the analytic center of the set of optimal solutions. Recently, it has been shown that this is not necessarily true for linear semidefinite programming in the absence of strict complementarity. The present paper deals with the formulation of a convex problem whose solution defines … Read more