Optimization Online


Approximating Pareto Curves using Semidefinite Relaxations

Victor Magron (victor.magron***at***laas.fr)
Didier Henrion (henrion***at***laas.fr)
Jean-Bernard Lasserer (lasserre***at***laas.fr)

Abstract: We consider the problem of constructing an approximation of the Pareto curve associated with the multiobjective optimization problem $\min_{x \in S} \{(f_1(x),f_2(x))\}$, where $f_1$ and $f_2$ are two conflicting positive polynomial criteria and $S \subset R^n$ is a compact basic semialgebraic set. We provide a systematic numerical scheme to approximate the Pareto curve. We start by reducing the initial problem into a scalarized polynomial optimization problem (POP). Three scalarization methods lead to consider different parametric POPs, namely (a) a weighted convex sum approximation, (b) a weighted Chebyshev approximation, and (c) a parametric sublevel set approximation. For each case, we have to solve a semidefinite programming (SDP) hierarchy parametrized by the number of moments or equivalently the degree of a polynomial sums of squares approximation of the Pareto curve. When the degree of the polynomial approximation tends to infinity, we provide guarantees of convergence to the Pareto curve in $L^2$-norm for methods (a) and (b), and $L^1$-norm for method (c).

Keywords: multiobjective optimization; semidefinite programming

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 04/18/2014
Entry Accepted: 04/18/2014
Entry Last Modified: 06/16/2014

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 Optimization Society