A Tight Surrogate-Based Adaptive Step Size for the Multiobjective Conditional Gradient Method

Abstract

The multiobjective conditional gradient (MCondG) method is an effective descent-type algorithm for solving constrained multiobjective optimization problems. In this algorithm, the adaptive step size is derived by minimizing a one-dimensional convex quadratic surrogate function, which guarantees a sufficient decrease in all objective functions at each iteration. However, we observe that this surrogate function is relatively conservative, producing overly small step sizes and consequently slowing the convergence of the algorithm. This conservativeness stems from the fact that the surrogate function is dominated by the largest Lipschitz constant among the gradients of all objective functions. Motivated by this observation, we develop a tighter quadratic surrogate function that exploits the individual gradient Lipschitz constants. Based on this surrogate, we propose a new adaptive step size strategy obtained by evaluating this surrogate over a finite candidate set. We prove that the proposed step size preserves the descent property of the MCondG method, and has an improved worst-case complexity bound compared with the original adaptive step size strategy. Numerical experiments on benchmark and real-world problems demonstrate the effectiveness of the proposed strategy in terms of computational efficiency and solution quality.