Search

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]

Abstract: The backward–backward algorithm is a tool for finding minima of a regularization of the sum of two convex functions in Hilbert spaces. We generalize this setting to Hadamard spaces and prove the convergence of an error-tolerant version of the backward–backward method. [Copyright &y& Elsevier]

This paper presents an accelerated variant of the hybrid proximal extragradient (HPE) method for convex optimization, referred to as the accelerated HPE (A-HPE) framework. Iteration-complexity results are established for the A-HPE framework, as well as a special version of it, where a large stepsize condition is imposed. Two specific implementations of the A-HPE framework are described in the context of a structured convex optimization problem whose objective function consists of the sum of a smooth convex function and an extended real-valued nonsmooth convex function. In the first implementation, a generalization of a variant of Nesterov's method is obtained for the case where the smooth component of the objective function has Lipschitz continuous gradient. In the second implementation, an accelerated Newton proximal extragradient (A-NPE) method is obtained for the case where the smooth component of the objective function has Lipschitz continuous Hessian. It is shown that the A-NPE method has a O(1/k7/2) convergence rate, which improves upon the O(1/k³) convergence rate bound for another accelerated Newton-type method presented by Nesterov. Finally, while Nesterov's method is based on exact solutions of subproblems with cubic regularization terms, the A-NPE method is based on inexact solutions of subproblems with quadratic regularization terms and hence is potentially more tractable from a computational point of view. [ABSTRACT FROM AUTHOR]

In this article we study thehybrid extragradient methodcoupled with approximation and penalty schemes for convex minimization problems. Under certain hypotheses, which include, for example, the case of Tikhonov regularization, we prove asymptotic convergence of the method to the solution set of our minimization problem. When we use schemes of penalization or barrier, we can show asymptotic convergence using the well-known fast/slow parameterization techniques and exploiting the existence and finite length of an optimal path. [ABSTRACT FROM AUTHOR]

In this note, an inertial and relaxed version of a diagonal hybrid projection-proximal point algorithm is considered, in order to find the minimum of a function f approximated by a sequence of functions (in general, smoother than f or taking into account some constraints of the problem). Two convergence theorems are proved under different kind of assumptions, which allows to apply the method in various cases. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing nonsmooth convex functions, defined piecewise by a finite number of functions each of which is either convex quadratic or twice continuously differentiable with positive definite Hessian on the set of interest. This is a particular case of functions with primal-dual gradient structure, a notion closely related to the so-called VU space decomposition: At a given point, nonsmoothness is locally restricted to the directions of the subspace V, while along the subspace U the behavior of the function is twice differentiable. Constructive identification of the two subspaces is important, because it opens the way to devising fast algorithms for nonsmooth optimization (by following iteratively the manifold of smoothness on which superlinear U-Newton steps can be computed). In this work we show that, for the class of functions in consideration, the information needed for this identification can be obtained from the output of a standard bundle method for computing proximal points, provided a minimizer satisfies the nondegeneracy and strong transversality conditions. [ABSTRACT FROM AUTHOR]

We study a family of penalty functions for augmented Lagrangian methods, and concentrate on a penalty based on the modified logarithmic barrier function. The convex conjugate of this penalty induces a Bregman distance, and the dual iterates associated with the augmented Lagrangian algorithm correspond to the iterates produced by a proximal point algorithm based on this distance. The global convergence of the dual iterates is then proved. Moreover, the level curves of the quadratic approximation of the dual kernels associated with these penalty functions are the Dikin ellipsoids. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We consider the vector optimization problem of finding weakly efficient points for maps from a Hilbert space X to a Banach space Y with respect to the partial order induced by a closed, convex, and pointed cone $C\subset Y$ with a nonempty interior. We develop for this problem an extension of the proximal point method for scalar-valued convex optimization. In this extension, the subproblems consist of finding weakly efficient points for suitable regularizations of the original map. We present both an exact and an inexact version, in which the subproblems are solved only approximately, within a constant relative tolerance. In both cases, we prove weak convergence of the generated sequence to a weakly efficient point, assuming convexity of the map with respect to C and C-completeness of the initial section. In cases where this last assumption fails, we still establish that the generating sequence is, in a suitable sense, a minimizing one. We also exhibit a particular instance of the algorithm for which, under a mild hypothesis on C, the weak limit of the generated sequence is an efficient, rather than a weakly efficient, point. [ABSTRACT FROM AUTHOR]

In this work, we consider the convex quadratic programming problem arising in support vector machine (SVM), which is a technique designed to solve a variety of learning and pattern recognition problems. Since the Hessian matrix is dense and real applications lead to large-scale problems, several decomposition methods have been proposed, which split the original problem into a sequence of smaller subproblems. SVM light algorithm is a commonly used decomposition method for SVM, and its convergence has been proved only recently under a suitable block-wise convexity assumption on the objective function. In SVM light algorithm, the size q of the working set, i.e. the dimension of the subproblem, can be any even number. In the present paper, we propose a decomposition method on the basis of a proximal point modification of the subproblem and the basis of a working set selection rule that includes, as a particular case, the one used by the SVM light algorithm. We establish the asymptotic convergence of the method, for any size q ≥ 2 of the working set, and without requiring any further block-wise convexity assumption on the objective function. Furthermore, we show that the algorithm satisfies in a finite number of iterations a stopping criterion based on the violation of the optimality conditions. [ABSTRACT FROM AUTHOR]

Under investigation is the problem of finding the best approximation of a function in a Hilbert space subject to convex constraints and prescribed nonlinear transformations. We show that in many instances these prescriptions can be represented using firmly nonexpansive operators, even when the original observation process is discontinuous. The proposed framework thus captures a large body of classical and contemporary best approximation problems arising in areas such as harmonic analysis, statistics, interpolation theory, and signal processing. The resulting problem is recast in terms of a common fixed point problem and solved with a new block-iterative algorithm that features approximate projections onto the individual sets as well as an extrapolated relaxation scheme that exploits the possible presence of affine constraints. A numerical application to signal recovery is demonstrated. [ABSTRACT FROM AUTHOR]