Outer approximation algorithms for convex vector optimization problems

Abstract

In this study, we present a general framework of outer approximation algorithms to solve convex vector optimization problems, in which the Pascoletti-Serafini (PS) scalarization is solved iteratively. This scalarization finds the minimum ‘distance’ from a reference point, which is usually taken as a vertex of the current outer approximation, to the upper image through a given direction. We propose efficient methods to select the parameters (the reference point and direction vector) of the PS scalarization and analyse the effects of these on the overall performance of the algorithm. Different from the existing vertex selection rules from the literature, the proposed methods do not require solving additional single-objective optimization problems. Using some test problems, we conduct an extensive computational study where three different measures are set as the stopping criteria: the approximation error, the runtime, and the cardinality of the solution set. We observe that the proposed variants have satisfactory results, especially in terms of runtime compared to the existing variants from the literature.

Keywords:

• Multiobjective optimization
• convex vector optimization
• approximation algorithms
• Pascoletti–Serafini scalarization

Mathematics Subject Classifications (2020):

• 90B50
• 90C25
• 90C29

Acknowledgments

The authors thank the anonymous referees for insightful comments that allowed them to correct some inaccuracies appearing in the preceding version and for numerous suggestions that improved the presentation. They also thank Daniel Dörfler for his suggestions to improve the computational results.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 In the proof of [18, Proposition 4.4], the feasible region of (PS(v,d)(PS($v,d$)) $\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}z\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}f\left(x\right){\le }_{C}v+zd,x\in \mathcal{X},z\in \mathbb{R}.$(PS($v,d$)) ) is stated to be compact.

2 See Section 5 for the computer and solver specifications.

3 In addition to the ones from Section 4.2, different direction selection methods that are specifically designed for UB are discussed and tested. The details are provided as an online supplement.

4 avg is the average of ${\hat{u}}_i$ values that are not equal to M, that is $avg=\frac{\sum _{i:{\hat{u}}_i\ne M}{\hat{u}}_i}{|\{i:{\hat{u}}_i\ne M\}|}$. Note that $u^{temp}$ is in $\mathcal{P}$ by construction and it is used only to compute a better upper bound for $\mathrm{d}(v,\mathcal{P})$.

5 The pseudocodes of the corresponding procedures are provided in the online supplement.

6 This example is bounded in the sense that the upper image is included in $y^I+{\mathbb{R}}_{+}^2$ where $y^I=0\in {\mathbb{R}}^2$. In theory, the weighted sum scalarizations for the initialization step, namely, $\left(\underset{x\in {\mathbb{R}}_{+}}{inf}x\right)$ and $\left(\underset{x\in {\mathbb{R}}_{+}}{inf}\frac{1}{x}\right)$ do not have solutions as x = 0 is not in the domain of the problem and $(\underset{x\in {\mathbb{R}}_{+}}{inf}\frac{1}{x}=0)$ is not attained, respectively. For the computational tests, we manually set the initial outer approximation as $P^0=\left\{0\right\}+{\mathbb{R}}_{+}^2$.

7 This set of examples is taken from [6].

8 The results for other a values are similar, hence the corresponding figures are not included here.

9 See the online supplement for the results with $C\ne {\mathbb{R}}_{+}^p$.

Additional information

Notes on contributors

İrem Nur Keskin

İrem Nur Keskin received her bachelor's and master's degrees in Industrial Engineering from Bilkent University in Ankara, Turkey. She is currently pursuing her Ph.D. studies in Decision Sciences at Duke University's Fuqua School of Business.

Firdevs Ulus

Firdevs Ulus is an assistant professor at Industrial Engineering Department in Bilkent University, Ankara. She received her Ph.D. in Operations Research and Financial Engineering from Princeton University, NJ in 2015. She also received a M.S. degree in Mathematics from Sabanc? University, Istanbul in 2010. Her research interests are in vector and set optimization, convex programming, multiobjective (mixed) integer programming, algorithms and applications from finance and economics.