A Hybrid Non-Monotone Cubic Line-Search Method with Subset-Based Armijo Acceptance for Multi-Objective Optimization

Line-search techniques are vital to first-order optimization algorithms because they provide stable and efficient convergence. In multi-objective optimization, designing effective step-length rules is especially difficult because conflicting objectives are involved, and such situations make it often impossible to design a rule that involves strict monotonic decrease of all components, and results in premature stagnation. In this paper a Hybrid Non-Monotone Cubic (HNMC) line-search algorithm for unconstrained multi-objective optimization problems is proposed. The proposed approach integrates cubic interpolation with two non-monotone reference mechanisms, i.e. sliding window maximum and exponential moving average. A subset-based Armijo acceptance rule is used to permit controlled non-monotonic behavior in the context of providing sufficient descent in some prescribed portion of the objectives. When a cubic candidate step fails to satisfy the acceptance criteria, a geometric backtracking technique is used to ensure the robustness. Under standard assumptions of Lipschitz-continuous gradients and bounded level sets, the method is proven to converge globally to Pareto-critical points in terms of a Pareto-stationarity measure. Numerical experiments on standard ZDT and DTLZ benchmark problems show that the proposed method can have better performance in terms of hypervolume improvement whilst having about 20–30% fewer function and gradient evaluations than classical Armijo and strong Wolfe line search strategies. These results confirm the robustness and efficiency of the proposed approach for gradient-based multi-objective optimization.