Many convex optimization methods are conceived of and analyzed in a largely separate fashion. In contrast to this traditional separation, this manuscript points out and demonstrates the utility of an important but largely unremarked common thread running through many prominent optimization methods. Specifically, we show that methods such as successive orthogonal projection, gradient descent, projected gradient descent, the proximal point method, forward-backward splitting, the alternating direction method of multipliers, and under- or over-relaxed variants of the preceding all involve updates that are of a common type --- namely, the updates satisfy a property known as pseudocontractivity. Moreover, since the property of pseudocontractivity is preserved under both composition and convex combination, updates constructed via these operations from pseudocontractive updates are themselves pseudocontractive. Having demonstrated that pseudocontractive updates are to be found in many optimization methods, we then provide an initial example of the type of unified analysis that becomes possible in the settings where the property of pseudocontractivity is found to hold. Specifically, we prove a novel bound satisfied by the norm of the difference in iterates of pseudocontractive updates and we then use this bound to establish an @math worst-case convergence rate on the error criterion @math for any method involving pseudocontractive updates (where @math is the number of iterations).
In @cite_16 the discussion covers (projected) gradient descent, the proximal-point method, forward-backward splitting, the alternating direction method of multipliers, and numerous other methods. The coverage does touch on the special case of @math -pseudocontractivity (i.e., firm nonexpansiveness) and on the special case of @math -inverse strong monotonicity; however, without the more general concepts of @math -pseudocontractivity and @math -inverse strong monotonicity (and the relationship between these concepts) there are significant limits to the results that can be obtained. One particularly notable limitation of a focus on firmly nonexpansive operators is that the class of firmly nonexpansive operators is not closed under composition.
@cite_16
2198227614 2163232332 2803240098 2135779729
We develop a new proximal-gradient method for minimizing the sum of a differentiable, possibly nonconvex, function plus a convex, possibly nondifferentiable, function. The key features of the proposed method are the definition of a suitable descent direction, based on the proximal operator associated to the convex part of the objective function, and an Armijo-like rule to determine the stepsize along this direction ensuring the sufficient decrease of the objective function. In this frame, we especially address the possibility of adopting a metric which may change at each iteration and an inexact computation of the proximal point defining the descent direction. For the more general nonconvex case, we prove that all limit points of the iterates sequence are stationary, while for convex objective functions we prove the convergence of the whole sequence to a minimizer, under the assumption that a minimizer exists. In the latter case, assuming also that the gradient of the smooth part of the objective function... We consider the problem of minimizing the sum of a smooth function @math with a bounded Hessian and a nonsmooth function. We assume that the latter function is a composition of a proper closed function @math and a surjective linear map @math , with the proximal mappings of @math , @math , simple to compute. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: the alternating direction method of multipliers and the proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions @math and @math are semialgebraic. Further... In this paper, we present new stochastic methods for solving two important classes of nonconvex optimization problems. We first introduce a randomized accelerated proximal gradient (RapGrad) method for solving a class of nonconvex optimization problems consisting of the sum of @math component functions, and show that it can significantly reduce the number of gradient computations especially when the condition number @math (i.e., the ratio between the Lipschitz constant and negative curvature) is large. More specifically, RapGrad can save up to @math gradient computations than existing deterministic nonconvex accelerated gradient methods. Moreover, the number of gradient computations required by RapGrad can be @math (at least @math ) times smaller than the best-known randomized nonconvex gradient methods when @math . Inspired by RapGrad, we also develop a new randomized accelerated proximal dual (RapDual) method for solving a class of multi-block nonconvex optimization problems coupled with linear constraints. We demonstrate that RapDual can also save up to a factor of @math projection subproblems than its deterministic counterpart, where @math denotes the number of blocks. To the best of our knowledge, all these complexity results associated with RapGrad and RapDual seem to be new in the literature. We also illustrate potential advantages of these algorithms through our preliminary numerical experiments. The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated. Rate-of-convergence results for the “method of multipliers,” of the strong sort already known, are derived in a generalized form relevant also to problems beyond the compass of the standard second-order conditions for oplimality. The new algorithm, the “proximal method of multipliers,” is shown to have much the same convergence properties, but with some potential advantages.