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]

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]