The indefinite proximal point algorithms for maximal monotone operators

The proximal point algorithm (PPA) has been widely used in convex optimization. Many algorithms fall into the framework of PPA. To guarantee the convergence of PPA, however, existing results conventionally need to ensure the positive definiteness of the corresponding proximal measure. In some senses, this essentially results in tiny step sizes (or over regularization) for the subproblems and thus inevitably decelerates the overall convergence speed of PPA. In this paper, we investigate the possibility of relaxing the positive definiteness requirement of the proximal measure in PPA. An indefinite PPA for finding a zero of maximal monotone operator is thus proposed via choosing an indefinite proximal regularization term, resulting in larger step sizes. Under some suitable conditions, we prove the global convergence of the proposed algorithm and its extension. To make our method more practical, we suggest to solve the subproblem in an approximate manner and propose two flexible inexact criteria. We show that the condition which guarantees the convergence of the proposed indefinite PPA is tight by a simple example. In addition, we show how to apply the indefinite PPA to some convex models. We report some preliminary numerical results, which show the efficiencies of the proposed algorithms.