Convergence analysis of a norm minimization-based convex vector optimization algorithm

MaRDI QIDQ6426757zbMATH OpenFDO

Authors Çağın Ararat, Firdevs Ulus, Muhammad Umer

Publication date 17 February 2023

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Approximation by convex sets (52A27) Management decision making, including multiple objectives (90B50) Convex programming (90C25) Multi-objective and goal programming (90C29)

Abstract: In this work, we propose an outer approximation algorithm for solving bounded convex vector optimization problems (CVOPs). The scalarization model solved iteratively within the algorithm is a modification of the norm-minimizing scalarization proposed in Ararat et al. (2022). For a predetermined tolerance $epsilon>0$, we prove that the algorithm terminates after finitely many iterations, and it returns a polyhedral outer approximation to the upper image of the CVOP such that the Hausdorff distance between the two is less than $epsilon$. We show that for an arbitrary norm used in the scalarization models, the approximation error after $k$ iterations decreases by the order of $mathcalO(k^{1/(1-q)})$, where $q$ is the dimension of the objective space. An improved convergence rate of $mathcalO(k^{2/(1-q)})$ is proved for the special case of using the Euclidean norm.

This page was built for publication: Convergence analysis of a norm minimization-based convex vector optimization algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426757)