Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization

Nonconvex minimization algorithms often benefit from the use of second-order information as represented by the Hessian matrix. When the Hessian at a critical point possesses negative eigenvalues, the corresponding eigenvectors can be used to search for further improvement in the objective function value. Computing such eigenpairs can be computationally challenging, particularly if the Hessian matrix … Read more

”Active-set complexity” of proximal gradient: How long does it take to find the sparsity pattern?

Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or L1-regularization. Under suitable nondegeneracy conditions, it is known that these algorithms identify the optimal sparsity pattern for these types of problems in a finite number of iterations. However, it is not known how many iterations this may … Read more

Fairer Benchmarking of Optimization Algorithms via Derivative Free Optimization

Research in optimization algorithm design is often accompanied by benchmarking a new al- gorithm. Some benchmarking is done as a proof-of-concept, by demonstrating the new algorithm works on a small number of dicult test problems. Alternately, some benchmarking is done in order to demonstrate that the new algorithm in someway out-performs previous methods. In this … Read more

Identifying Active Manifolds in Regularization Problems

In this work we consider the problem $\min_x \{ f(x) + P(x) \}$, where $f$ is $\mathcal{C}^2$ and $P$ is nonsmooth, but contains an underlying smooth substructure. Specifically, we assume the function $P$ is prox-regular partly smooth with respect to a active manifold $\M$. Recent work by Tseng and Yun \cite{tseng-yun-2009}, showed that such a … Read more

A Redistributed Proximal Bundle Method for Nonconvex Optimization

Proximal bundle methods have been shown to be highly successful optimization methods for unconstrained convex problems with discontinuous first derivatives. This naturally leads to the question of whether proximal variants of bundle methods can be extended to a nonconvex setting. This work proposes an approach based on generating cutting-planes models, not of the objective function … Read more

A Proximal Method for Identifying Active Manifolds

The minimization of an objective function over a constraint set can often be simplified if the “active manifold” of the constraints set can be correctly identified. In this work we present a simple subproblem, which can be used inside of any (convergent) optimization algorithm, that will identify the active manifold of a “prox-regular partly smooth” … Read more

Benchmark of Some Nonsmooth Optimization Solvers for Computing Nonconvex Proximal Points

The major focus of this work is to compare several methods for computing the proximal point of a nonconvex function via numerical testing. To do this, we introduce two techniques for randomly generating challenging nonconvex test functions, as well as two very specific test functions which should be of future interest to Nonconvex Optimization Benchmarking. … Read more

Prox-Regularity and Stability of the Proximal Mapping

Fundamental insights into the properties of a function come from the study of its Moreau envelopes and Proximal point mappings. In this paper we examine the stability of these two objects under several types of perturbations. In the simplest case, we consider tilt-perturbations, i.e. perturbations which correspond to adding a linear term to the objective … Read more

Computing Proximal Points on Nonconvex Functions

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 … Read more