A linear programming framework and an improved backtracking strategy for multiple-gradient descent

This work introduces a method to compute descent directions common to two or more differentiable functions defined over a shared unconstrained domain. Building on this, an alternative Multiple-Gradient Descent procedure for Multi-Objective Optimization problems is proposed. The core of the approach consists of solving a relatively cheap Linear Programming (LP) problem, where the objective and constraints are constructed from the gradients of the functions involved. In particular, the LP formulation is designed such that, when a common descent direction does not exist, it still yields a direction that is perpendicular to all objectives’ gradients, if such a direction is available. Additionally, a tailored backtracking strategy is presented, enhancing the performance of Multiple-Gradient Descent methods, especially when paired with the proposed LP-based direction computation, by improving the exploration of the Pareto set and front. Theoretical analysis and experiments on standard benchmark problems are provided to evaluate the effectiveness of the proposed techniques.