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

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.