Regularization Method for the Clarke’s Generalized Jacobian to Ensure the Formation of Nonsingular Systems for Inexact Newton Methods

摘要

Finding solutions to big data optimization problems requires the using of numerical methods that are resistant to calculation errors. We analyze the impact of the computation errors caused by the use of the Fischer-Burmeister function on the PATH algorithm. We found out that the errors in calculating the gradient of the merit function are the main cause for slowing down and even loosing convergence of the minor iterative cycle when searching for a new decision point along the direction of the gradient descent of the PATH algorithm. To counteract the errors in the evaluation of the merit function gradient, we propose a regularization of the Clarke’s generalized Jacobian of the Fischer-Burmeister merit function. We establish conditions that lead to singularity in Newton’s systems and propose a regularization method for the Clarke’s generalized Jacobian to ensure the formation of nonsingular systems for inexact Newton methods. We compare our regularization method against state-of-the-art benchmarks. Specifically, we solve big data optimization problems that originate from electricity market models for different countries. Based on the preconditioned quasi-Newton method with regularization of the Clarke’s generalized Jacobian our implementation successfully solves problems with up to ten million dimensions. By contrast, PATH solver allows solving similar problems of up to ten thousands dimensions only.