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.
Related
- A Riemannian Inertial Adaptive Gradient Method with Momentum Restart
- Adaptive Normalized Gradient Method for (L0,L1)-smooth Problems: Estimating Problem Parameters as a Region
- A Parameter-Free Adaptive Reflected Gradient Method for Monotone Variational Inequalities
- The Convergence Rate of Accelerated Proximal Gradient Methods with General Inertia Term for Convex Composite Multiobjective Optimization
- Gaussian-process surrogate indicators for residual-based adaptive GMsFEM
BibTeX
@misc{chen2026tight,
title = {{A Tight Surrogate-Based Adaptive Step Size for the Multiobjective Conditional Gradient Method}},
author = {Wang Chen and Yong Zhao and Liping Tang and Xinmin Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21831},
eprint = {2609.21831},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21831},
}
RIS
TY - UNPB
TI - A Tight Surrogate-Based Adaptive Step Size for the Multiobjective Conditional Gradient Method
AU - Wang Chen
AU - Yong Zhao
AU - Liping Tang
AU - Xinmin Yang
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21831
UR - https://arxiv.org/abs/2609.21831
AB - 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.
ER -