Title: Norm minimization-based convex vector optimization algorithms by Muhammad Umer, Ph.D in Industrial Engineering
Advisor: Asst. Prof. Firdevs Ulus
Co-Advisor: Asst. Prof. Çağın Ararat
Date: Aug 05, 2022 02:00 PM Istanbul
Meeting ID: 813 8720 4610
This thesis is concerned with convex vector optimization problems (CVOP). We propose an outer approximation algorithm (Algorithm 1) for solving CVOPs. In each iteration, the algorithm solves a norm-minimizing scalarization for a reference point in the objective space. The idea is inspired by some Benson-type algorithms in the literature that are based on Pascoletti-Serafini scalarization. Since this scalarization needs a direction parameter, the efficiency of these algorithms depend on the selection of the direction parameter. In contrast, our algorithm is free of direction biasedness since it solves a scalarization that is based on minimizing a norm. However, the structure of such algorithms, including ours, has some built-in limitation which makes it difficult to perform convergence analysis. To overcome this, we modify the algorithm by introducing a suitable compact subset of the upper image. After the modification, we have Algorithm 2 in which norm-minimizing scalarizations are solved for points in the compact set. To the best of our knowledge, Algorithm 2 is the first algorithm for CVOPs, which is proven to be finite. Finally, we propose a third algorithm for the purposes of convergence analysis (Algorithm 3), where a modified norm-minimizing scalarization is solved in each iteration. This scalarization includes an additional constraint which ensures that the algorithm deals with only a compact subset of the upper image from the beginning. Besides having the finiteness result, Algorithm 3 is the first CVOP algorithm with an estimate of a convergence rate. The experimental results, obtained using some benchmark test problems, show comparable performance of our algorithms with respect to an existing CVOP algorithm based on Pascoletti-Serafini scalarization.