Proximal Dogleg Opportunistic Majorization for Nonconvex and Nonsmooth Optimization

Abstract

We consider minimizing a function consisting of a quadratic term and a proximable term which is possibly nonconvex and nonsmooth. This problem is also known as scaled proximal operator. Despite its simple form, existing methods suffer from slow convergence or high implementation complexity or both. To overcome these limitations, we develop a fast and user-friendly second-order proximal algorithm. Key innovation involves building and solving a series of opportunistically majorized problems along a hybrid Newton direction. The approach directly uses the precise Hessian of the quadratic term, and calculates the inverse only once, eliminating the iterative numerical approximation of the Hessian, a common practice in quasi-Newton methods. The algorithm's convergence to a critical point is established, and local convergence rate is derived based on the Kurdyka-Lojasiewicz property of the objective function. Numerical comparisons are conducted on well-known optimization problems. The results demonstrate that the proposed algorithm not only achieves a faster convergence but also tends to converge to a better local optimum compare to benchmark algorithms.

References in corpus (9)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Splitting methods with variable metric for KL functions
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms
• PRIME: Phase Retrieval via Majorization-Minimization
• On the convergence of a linesearch based proximal-gradient method for nonconvex optimization
• Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOC