A study on two-metric projection methods

2024/09/09 by Wu, Hanju, Xie, Yue
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2409.05321

Abstract

The two-metric projection method is a simple yet elegant algorithm proposed by Bertsekas in 1984 to address bound/box-constrained optimization problems. The algorithm's low per-iteration cost and potential for using Hessian information makes it a favourable computation method for this problem class. However, its global convergence guarantee is not studied in the nonconvex regime. In our work, we first investigate the global complexity of such a method for finding first-order stationary solution. After properly scaling each step, we equip the algorithm with competitive complexity guarantees. Furthermore, we generalize the two-metric projection method for solving ℓ₁-norm minimization and discuss its properties via theoretical statements and numerical experiments.

Related

• On the resolution of ℓ₁-norm minimization via a two-metric adaptive projection method
• A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
• Inexact Newton-type Methods for Optimisation with Nonnegativity Constraints
• L1 Projections with Box Constraints
• First-Order Projected Algorithms With the Same Linear Convergence Rate Bounds as Their Unconstrained Counterparts