Optimization Online


Optimization over the Pareto Outcome set associated with a Convex Bi-Objective Optimization Problem: Theoretical Results, Deterministic Algorithm and Application to the Stochastic case

Henri Bonnel (henri.bonnel***at***univ-nc.nc)
Julien Collonge (julien.collonge***at***univ-nc.nc)

Abstract: Our paper consists of two main parts. In the first one, we deal with the deterministic problem of minimizing a real valued function $f$ over the Pareto set associated with a deterministic convex bi-objective optimization problem (BOP), in the particular case where $f$ depends on the objectives of (BOP), i.e. we optimize over the Pareto set in the Outcome space. In general, the optimal value $U$ of such a kind of problem cannot be computed directly, so we propose an outcome deterministic algorithm whose principle is to give at every step a range (lower bound, upper bound) that contains $U$. Then we show that for any given error bound, the algorithm terminates in a finite number of steps. In the second part of our paper, in order to handle also the Stochastic case, we consider the situation where the two objectives of (BOP) are given by expectations of random functions, and we deal with the stochastic problem $(S)$ of minimizing a real valued function $f$ over the Pareto outcome set associated with this Stochastic Bi-Objective Optimization Problem (SBOP). Because of the presence of random functions, the Pareto set associated with this type of problem cannot be explicitly given, and so the optimal value $V$ of problem $(S)$. That is why we consider a sequence of Sample Average Approximation problems (SAA-$N$, where $N$ is the sample size) whose optimal values converge almost surely to $V$ as the sample size $N$ goes to infinity. Assuming $f$ nondecreasing, we show first that the convergence rate is exponential. Moreover, for any given $\eps>0$ and $p_0\in]0,1[$, we propose a rank $N^0=N^0(\eps,p_0)$ (which explicitly depends on data) such that the SAA-$N^0$ optimal value is an $\eps$-approximation of $V$ with probability greater than $p_0$. Thus we obtain a confidence interval that contains $V$. Finally, some computational results are given to illustrate the paper.

Keywords: Optimization over the Pareto image set · Multi-objective Stochastic optimization · Multi-objective Deterministic optimization · Multi-Objective convex optimization · Sample average approximation method

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Stochastic Programming

Citation: J. Global Optim., DOI: 10.1007/s10898-014-0257-0


Entry Submitted: 02/01/2014
Entry Accepted: 02/01/2014
Entry Last Modified: 11/21/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