An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.

• Publication year

  2011

• Venue

  Journal of Global Optimization

• Publication date

  2011-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10898-010-9588-7
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming

  2012influential reference
• A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming

  2011influential reference
• Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning

  2008influential reference
• Improved ε-Constraint Method for Multiobjective Programming

  2008cited by this paper
• Nonlinear Programming Theory and Algorithms

  2007cited by this paper
• A survey of recent developments in multiobjective optimization

  2007cited by this paper
• for multiobjective

  2007cited by this paper
• Experiments with classification-based scalarizing functions in interactive multiobjective optimization

  2006cited by this paper
• Approximation Methods in Multiobjective Programming

  2005cited by this paper
• On the approximability of trade-offs and optimal access of Web sources

  2000cited by this paper
• Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space

  1998cited by this paper
• Nonlinear multiobjective optimization

  1998cited by this paper
• An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem

  1998cited by this paper
• On-line and off-line vertex enumeration by adjacency lists

  1990cited by this paper
• Proper efficiency and the theory of vector maximization

  1968cited by this paper

• Pareto optimization of two-agent scheduling on parallel batch machines

  2026cites this paper
• Solving convex multi-objective optimization problems using a projection neural network framework

  2025influential citation
• A Novel Neural Network Model and Two New Algorithms for Solving Multiobjective Linear Optimization Problems

  2025cites this paper
• Efficient Approximation Quality Computation for Sandwiching Algorithms for Convex Multicriteria Optimization

  2025cites this paper
• MOCVXPY: a CVXPY extension for multiobjective optimization

  2025cites this paper
• Multiobjective Mixed-Integer Quadratic Models: A Study on Mathematical Programming and Evolutionary Computation

  2025cites this paper
• An approximation algorithm for multiobjective mixed-integer convex optimization

  2024cites this paper
• A deterministic optimization algorithm for nonconvex and combinatorial bi-objective programming

  2024cites this paper
• Solving Convex Multi-Objective Optimization Problems via a Capable Neural Network Scheme

  2024cites this paper
• An outer approximation algorithm for generating the Edgeworth–Pareto hull of multi-objective mixed-integer linear programming problems

  2024cites this paper
• Computing the recession cone of a convex upper image via convex projection

  2023cites this paper
• Advancements in the computation of enclosures for multi-objective optimization problems

  2023cites this paper
• Efficient Computation of the Approximation Quality in Sandwiching Algorithms

  2023cites this paper
• Convergence Analysis of a Norm Minimization-Based Convex Vector Optimization Algorithm

  2023cites this paper
• Solving general convex quadratic multi-objective optimization problems via a projection neurodynamic model

  2023cites this paper
• Polyhedral Approximation of Spectrahedral Shadows via Homogenization

  2023cites this paper
• Utilizing a projection neural network to convex quadratic multi‐objective programming problems

  2023cites this paper
• Reference-point-based branch and bound algorithm for multiobjective optimization

  2023cites this paper
• Algorithms to Solve Unbounded Convex Vector Optimization Problems

  2022cites this paper
• New decision-making methods for ranking of non-dominated points for multi-objective optimization problems

  2022cites this paper
• A modified version of a Benson-type algorithm proposed for obtaining solutions with better dispersion on the non-dominated set of a non-convex multi-objective programming problem

  2022cites this paper
• The Hybridization of Branch and Bound with Metaheuristics for Nonconvex Multiobjective Optimization

  2022cites this paper
• On the Approximation of Unbounded Convex Sets by Polyhedra

  2022cites this paper
• Multiple-Criteria Decision Making

  2022cites this paper
• A polyhedral approximation algorithm for recession cones of spectrahedral shadows

  2022cites this paper
• Deep learning the efficient frontier of convex vector optimization problems

  2022cites this paper
• On the Approximation of Unbounded Convex Sets by Polyhedra

  2022cites this paper
• Finding non dominated points for multiobjective integer convex programs with linear constraints

  2022cites this paper
• An outer approximation algorithm for multi-objective mixed-integer linear and non-linear programming

  2021cites this paper
• Convex Projection and Convex Vector Optimization

  2021cites this paper
• An approximation algorithm for multi-objective optimization problems using a box-coverage

  2021cites this paper
• Interactive navigation of multiple convex patches

  2021cites this paper
• Convex projection and convex multi-objective optimization

  2021cites this paper
• Outer approximation algorithms for convex vector optimization problems

  2021influential citation
• A new geometric duality and approximation algorithms for convex vector optimization problems

  2021cites this paper
• A Comparison of Benson's Outer Approximation Algorithm with an Extended Version of Multiobjective Simplex Algorithm

  2021influential citation
• Geometric Duality Results and Approximation Algorithms for Convex Vector Optimization Problems

  2021cites this paper
• Twenty years of continuous multiobjective optimization in the twenty-first century

  2021cites this paper
• An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives

  2021cites this paper
• A Norm Minimization-Based Convex Vector Optimization Algorithm

  2021influential citation
• On the approximation error for approximating convex bodies using multiobjective optimization

  2021cites this paper
• Approximation Algorithm Variants for Convex Multiobjective Optimization Problems

  2020cites this paper
• Solving Multiobjective Mixed Integer Convex Optimization Problems

  2020cites this paper
• Nonconvex constrained optimization by a filtering branch and bound

  2020cites this paper
• A monotonic optimization approach for solving strictly quasiconvex multiobjective programming problems

  2020influential citation
• Nonconvex and mixed integer multiobjective optimization with an application to decision uncertainty

  2020cites this paper
• A Benson-type algorithm for bounded convex vector optimization problems with vertex selection

  2020cites this paper
• An iterative vertex enumeration method for objective space based vector optimization algorithms

  2020cites this paper
• Solving biobjective network flow problem associated with minimum cost-time loading

  2020cites this paper
• Certainty equivalent and utility indifference pricing for incomplete preferences via convex vector optimization

  2020cites this paper
• An algorithmic approach to multiobjective optimization with decision uncertainty

  2019cites this paper
• No . M 19 / 06 Solving multiobjective mixed integer convex optimization problems

  2019cites this paper
• An Iterative Vertex Enumeration Method for Objective Space Based Multiobjective Optimization Algorithms

  2019cites this paper
• Certainty equivalent and utility indifference pricing for incomplete preferences via convex vector optimization

  2019influential citation
• A numerical method for the approximation of reachable sets of linear control systems

  2019cites this paper
• A Branch-and-Bound-Based Algorithm for Nonconvex Multiobjective Optimization

  2019cites this paper
• Approximation of convex bodies by multiple objective optimization and an application in reachable sets

  2018cites this paper
• Interactive Portfolio Optimization Using Mean-Gini Criteria

  2018cites this paper
• A multi-objective constraint-based approach for modeling genome-scale microbial ecosystems

  2017cites this paper
• An algorithm for approximating nondominated points of convex multiobjective optimization problems

  2017influential citation
• A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs

  2017cites this paper
• Multi-objective risk-averse two-stage stochastic programming problems

  2017cites this paper
• Tractability of convex vector optimization problems in the sense of polyhedral approximations

  2017influential citation
• Modeling Metabolic Networks and their Environment Interaction

  2017cites this paper
• Algorithms for on-line vertex enumeration problem

  2017cites this paper
• Benson's algorithm for nonconvex multiobjective problems via nonsmooth Wolfe duality

  2017influential citation
• Discrete representation of the non-dominated set for multi-objective optimization problems using kernels

  2017cites this paper
• An extension of the non-inferior set estimation algorithm for many objectives

  2017cites this paper
• Optimisation over the non-dominated set of a multi-objective optimisation problem

  2016influential citation
• A Benson type algorithm for nonconvex multiobjective programming problems

  2016cites this paper
• Solving generalized convex multiobjective programming problems by a normal direction method

  2016influential citation
• Continuous Multiobjective Programming

  2016cites this paper
• A recursive algorithm for multivariate risk measures and a set-valued Bellman’s principle

  2016cites this paper
• A Branch-and-Bound Algorithm for Bi-Objective Problems

  2016influential citation
• Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

  2016cites this paper
• Algorithms for Vector Optimization Problems

  2015influential citation
• Sensitivity and Stability Analysis for Inverse Optimization with Applications in Intensity-modulated Radiation Therapy

  2015cites this paper
• A parametric simplex algorithm for linear vector optimization problems

  2015cites this paper
• A deterministic method for constrained multicriteria optimization

  2015cites this paper
• Representative Systems and Decision Support for Multicriteria Optimization Problems

  2015cites this paper
• A recursive algorithm for multivariate risk measures and a set-valued Bellman’s principle

  2015cites this paper
• Generalized Inverse Optimization with Application to Cancer Therapy

  2015cites this paper
• Scheduling Problems with Variable Job Processing Times

  2014cites this paper
• Parallel Machine Scheduling Problems

  2014cites this paper
• Batching Scheduling Problems

  2014cites this paper
• Multiagent Scheduling Fundamentals

  2014cites this paper
• Problems, Algorithms and Complexity

  2014cites this paper
• Single Machine Problems

  2014cites this paper
• Generalized Inverse Multiobjective Optimization with Application to Cancer Therapy

  2014cites this paper
• Finding the pareto curve in bimatrix games is easy

  2014cites this paper
• A deterministic algorithm for global multi-objective optimization

  2014cites this paper
• Primal and dual approximation algorithms for convex vector optimization problems

  2013influential citation
• An Algorithm for Approximating Convex Pareto Surfaces Based on Dual Techniques

  2013cites this paper
• Benson type algorithms for linear vector optimization and applications

  2013cites this paper
• Multicriteria optimization for managing tradeoffs in radiation therapy treatment planning

  2013cites this paper
• Distributed approximation of Pareto surfaces in multicriteria radiation therapy treatment planning

  2013cites this paper
• An objective space cut and bound algorithm for convex multiplicative programmes

  2013influential citation
• Approximation method for computationally expensive nonconvex multiobjective optimization problems

  2012cites this paper
• An approximation algorithm for convex multiplicative programming problems

  2011influential citation
• Generating Efficient Outcome Points for Convex Multiobjective Programming Problems and Its Application to Convex Multiplicative Programming

  2011cites this paper