Optimization Online


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

Rasmus Bokrantz(bokrantz***at***kth.se)
Anders Forsgren(andersf***at***kth.se)

Abstract: 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 enumerative techniques, but at a cost that increases exponentially with the number of objectives. The goal of this paper is to present a practical algorithm for solving the Pareto set approximation problem in presence of up to about ten conflicting objectives, motivated by application to radiation therapy optimization. To this end, an enumerative scheme is proposed that is in a sense dual to the algorithms in the literature. The proposed technique retains the quality of output of the best previous algorithm while solving fewer subproblems. A further improvement is provided by a procedure for discarding subproblems based on reusing information from previous solves. The combined effect of the proposed enhancements is empirically demonstrated to reduce the computational expense of solving the Pareto surface approximation problem by orders of magnitude.

Keywords: bokrantz@kth.se

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Applications -- Science and Engineering (Biomedical Applications )

Citation: Technical Report TRITA-MAT-2011-OS3, Department of Mathematics, Royal Institute of Technology, February 2011

Download: [PDF]

Entry Submitted: 02/23/2011
Entry Accepted: 02/23/2011
Entry Last Modified: 02/23/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society