Search

Proximal bundle methods are a class of optimisation algorithms that leverage the proximal operator to address nonsmoothness in the objective function efficiently. This study focuses on a derivative-free (DFO) proximal bundle method and one of its applications called the DFO VU -algorithm. These algorithms incorporate approximate proximal points as subprocedures in order to optimise convex nonsmooth functions based on approximated subdifferential information. Interestingly, the classical VU -algorithm, which operates on true subgradient values, achieves superlinear convergence. At each iteration, the algorithm divides the whole space into two: the smooth U -space and the nonsmooth V -space. It takes a Newton-like step on the U -space and a proximal-point step on the V -space, enabling it to handle both smooth and nonsmooth parts effectively and converge faster. In this work, we reveal the worst possible convergence rate for the DFO VU -method by showing the linear convergence of the DFO proximal bundle method. This will be done by presenting a suitable framework and using the subdifferential-based error bound on the distance to critical points. [ABSTRACT FROM AUTHOR]

We introduce a geometrically transparent strict saddle property for nonsmooth functions. This property guarantees that simple proximal algorithms on weakly convex problems converge only to local minimizers, when randomly initialized. We argue that the strict saddle property may be a realistic assumption in applications, since it provably holds for generic semi-algebraic optimization problems. [ABSTRACT FROM AUTHOR]

Supported by the recent contributions in multiple domains, the first-order splitting became algorithms of choice for structured nonsmooth optimization. The large-scale noisy contexts make available stochastic information on the objective function and thus, the extension of proximal gradient schemes to stochastic oracles is heavily based on the tractability of the proximal operator corresponding to nonsmooth component, which has been highly exploited in the literature. However, some questions remained about the complexity of the composite models with proximal untractable terms. In this paper we tackle composite optimization problems, assuming only the access to stochastic information on both smooth and nonsmooth components, with a stochastic proximal first-order scheme with stochastic proximal updates. We provide sublinear O 1 k convergence rates (in expectation of squared distance to the optimal set) under the strong convexity assumption on the objective function. Also, linear convergence is achieved for convex feasibility problems. The empirical behavior is illustrated by numerical tests on parametric sparse representation models. [ABSTRACT FROM AUTHOR]

In this work, we give a tight estimate of the rate of convergence for the Halpern-iteration for approximating a fixed point of a nonexpansive mapping in a Hilbert space. Specifically, using semidefinite programming and duality we prove that the norm of the residuals is upper bounded by the distance of the initial iterate to the closest fixed point divided by the number of iterations plus one. [ABSTRACT FROM AUTHOR]

We consider the problems of minimizing the sum of a continuously differentiable convex function and a nonsmooth convex function in this paper. These problems arise in many applications of practical interest. A class of alternating linearization methods is presented for solving these problems. The global convergence rate is also obtained under certain mild conditions. Numerical experiments validate the theoretical convergence analysis and verify the implementation of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Locating proximal points is a component of numerous minimization algorithms. This work focuses on developing a method to find the proximal point of a convex function at a point, given an inexact oracle. Our method assumes that exact function values are at hand, but exact subgradients are either not available or not useful. We use approximate subgradients to build a model of the objective function, and prove that the method converges to the true prox-point within acceptable tolerance. The subgradient gk used at each step k is such that the distance from gk to the true subdifferential of the objective function at the current iteration point is bounded by some fixed ε > 0. The algorithm includes a novel tilt-correct step applied to the approximate subgradient. [ABSTRACT FROM AUTHOR]

For a class of nonconvex nonsmooth functions, we consider the problem of computing an approximate critical point, in the case when only inexact information about the function and subgradient values is available. We assume that the errors in function and subgradient evaluations are merely bounded, and in principle need not vanish in the limit. We examine the redistributed proximal bundle approach in this setting, and show that reasonable convergence properties are obtained. We further consider a battery of difficult nonsmooth nonconvex problems, made even more difficult by introducing inexactness in the available information. We verify that very satisfactory outcomes are obtained in our computational implementation of the inexact algorithm. [ABSTRACT FROM AUTHOR]

Given a point on the standard simplex, we calculate a proximal point on the regular grid which is closest with respect to any norm in a large class, including all $$\ell ^p$$ -norms for $$p\ge 1$$ . We show that the minimal $$\ell ^p$$ -distance to the regular grid on the standard simplex can exceed one, even for very fine mesh sizes in high dimensions. Furthermore, for $$p=1$$ , the maximum minimal distance approaches the $$\ell ^1$$ -diameter of the standard simplex. We also put our results into perspective with respect to the literature on approximating global optimization problems over the standard simplex by means of the regular grid. [ABSTRACT FROM AUTHOR]

The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with the critical points of the original function. This suggests that the many uses of proximal points, and their corresponding proximal envelopes (Moreau envelopes), will have a natural extension from convex optimization to nonconvex optimization. For example, the inexact proximal point methods for convex optimization might be redesigned to work for nonconvex functions. In order to begin the practical implementation of proximal points in a nonconvex setting, a first crucial step would be to design efficient methods of approximating nonconvex proximal points. This would provide a solid foundation on which future design and analysis for nonconvex proximal point methods could flourish. In this paper we present a methodology based on the computation of proximal points of piecewise affine models of the nonconvex function. These models can be built with only the knowledge obtained from a black box providing, for each point, the function value and one subgradient. Convergence of the method is proved for the class of nonconvex functions that are prox-bounded and lower- $${\mathcal{C}}^2$$ and encouraging preliminary numerical testing is reported. [ABSTRACT FROM AUTHOR]

We propose a class of self-adaptive proximal point methods suitable for degenerate optimization problems where multiple minimizers may exist, or where the Hessian may be singular at a local minimizer. If the proximal regularization parameter has the form µ(x) = β||∇ f (x)||η where η ∈ [0, 2) and β > 0 is a constant, we obtain convergence to the set of minimizers that is linear for ∇ = 0 and β sufficiently small, superlinear for ∇ ∈ (0, 1), and at least quadratic for ∇ ∈ [1, 2). Two different acceptance criteria for an approximate solution to the proximal problem are analyzed. These criteria are expressed in terms of the gradient of the proximal function, the gradient of the original function, and the iteration difference. With either acceptance criterion, the convergence results are analogous to those of the exact iterates. Preliminary numerical results are presented using some ill-conditioned CUTE test problems. [ABSTRACT FROM AUTHOR]

To minimize a convex function, we combine Moreau-Yosida regularizations, quasi-Newton matrices and bundling mechanisms. First we develop conceptual forms using “reversal” quasi-Newton formulae and we state their global and local convergence. Then, to produce implementable versions, we incorporate a bundle strategy together with a “curve-search”. No convergence results are given for the implementable versions; however some numerical illustrations show their good behaviour even for large-scale problems. [ABSTRACT FROM AUTHOR]

We propose a proximal Newton method for solving nondifferentiable convex optimization. This method combines the generalized Newton method with Rockafellar’s proximal point algorithm. At each step, the proximal point is found approximately and the regularization matrix is preconditioned to overcome inexactness of this approximation. We show that such a preconditioning is possible within some accuracy and the second-order differentiability properties of the Moreau-Yosida regularization are invariant with respect to this preconditioning. Based upon these, superlinear convergence is established under a semismoothness condition. [ABSTRACT FROM AUTHOR]

This paper introduces an algorithm for convex minimization which includes quasi-Newton updates within a proximal point algorithm that depends on a preconditioned bundle subalgorithm. The method uses the Hessian of a certain outer function which depends on the Jacobian of a proximal point mapping which, in turn, depends on the preconditioner matrix and on a Lagrangian Hessian relative to a certain tangent space. Convergence is proved under boundedness assumptions on the preconditioner sequence. [ABSTRACT FROM AUTHOR]

We consider conceptual optimization methods combining two ideas: the Moreau-Yosida regularization in convex analysis, and quasi-Newton approximations of smooth functions. We outline several approaches based on this combination, and establish their global convergence. Then we study theoretically the local convergence properties of one of these approaches, which uses quasi-Newton updates of the objective function itself. Also, we obtain a globally and superlinearly convergent BFGS proximal method. At each step of our study, we single out the assumptions that are useful to derive the result concerned. [ABSTRACT FROM AUTHOR]

This paper concerns the notion of a sharp minimum on a set and its relationship to the proximal point algorithm. We give several equivalent definitions of the property and use the notion to prove finite termination of the proximal point algorithm. [ABSTRACT FROM AUTHOR]

We introduce a hybrid proximal point algorithm and establish its strong convergence to a common solution of a proximal point of a lower semi-continuous mapping and a fixed point of a demicontractive mapping in the framework of a CAT(0) space. As applications of our new result, we solve variational inequality problems for these mappings on a Hilbert space. Illustrative example is given to validate theoretical result obtained herein. [ABSTRACT FROM AUTHOR]