Global $o(1/k^2)$ Merit Complexity of Regularized Newton Methods for Convex Multiobjective Optimization

Abstract

We investigate a regularized Newton method for unconstrained convex multi-objective optimization with twice continuously differentiable objectives whose Hessians are Lipschitz continuous. At each iteration, the method minimizes the quadratically regularized max-envelope of the local quadratic models. Using a Tanabe-type merit function, we prove that this merit decays at the global asymptotic rate $o(1/k^2)$ under the compactness assumption on the initial component-wise lower level set. This result also covers the single-objective case as a special case. Finally, we construct an explicit one-dimensional convex bi-objective family showing that no uniform merit estimate of order $\mathcal{O}(k^{-(2+\delta )})$ can hold for any fixed $\delta >0$. Thus the exponent $2$ is essentially sharp in the uniform polynomial sense, despite the $o(1/k^2)$ decay on each fixed trajectory.