2026/06/04 by Mohammed Alshahrani
#math.OC #cs.NA #math.NA
paper · pdf · doi:10.1016/j.cam.2026.118013
We develop parallel and batch-cutting variants of the norm-minimization-based outer approximation algorithm for convex vector optimization. The standard algorithm solves Nk independent subproblems at each iteration~k to evaluate all vertices of the current polyhedral approximation, but processes only the single best cut. We propose two improvements. First, we parallelize the \revisesubproblem evaluations across \nw workers, reducing per-iteration wall-clock time. Second, we introduce a batch-cutting strategy that adds up to K supporting halfspaces per iteration, using information from all solved subproblems rather than discarding it. We prove that the batch-cutting variant inherits the convergence rate O(k2/(1-q)) of the standard algorithm, where k is the number of outer iterations and q is the number of objectives. Computational experiments on eight test problems with q ∈ \2,3,4,5\ show that parallelism on 8 cores \reviseincreases the speed by a factor of 1.1 to 4.2, and batch cutting consistently reduces the iteration count by 62--80%. However, the wall-clock benefit of batch cutting is problem-dependent: the additional cuts per iteration accelerate vertex count growth, so batch cutting is most effective when per-vertex subproblem cost dominates.