Many optimization algorithms converge to stationary points. When the underlying problem
is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points.
We propose the Run-and-Inspect Method, which adds an “inspect” phase to existing algorithms that
helps escape from non-global stationary points. The inspection samples a set of points in a radius R
around the current point. When a sample point yields a sufficient decrease in the objective, we resume
an existing algorithm from that point. If no sufficient decrease is found, the current point is called an
approximate R-local minimizer. We show that an R-local minimizer is globally optimal, up to a specific
error depending on R, if the objective function can be implicitly decomposed into a smooth convex
function plus a restricted function that is possibly nonconvex, nonsmooth. Therefore, for such nonconvex
objective functions, verifying global optimality is fundamentally easier. For high-dimensional problems, we
introduce blockwise inspections to overcome the curse of dimensionality while still maintaining optimality
bounds up to a factor equal to the number of blocks. Our method performs well on a set of artificial and
realistic nonconvex problems by coupling with gradient descent, coordinate descent, EM, and prox-linear
Many iterative methods in optimization are fixed-point iterations with averaged operators. As such methods converge at an O(1/k) rate with the constant determined by the averagedness coefficient, establishing small averagedness coefficients for operators is of broad interest. In this paper, we show that the averagedness coefficients of the composition of averaged operators by Ogura and Yamada (Numer Func Anal Opt 32(1–2):113–137, 2002) and the threeoperator splitting by Davis and Yin (Set Valued Var Anal 25(4):829–858, 2017) are tight. The analysis relies on the scaled relative graph, a geometric tool recently proposed by Ryu, Hannah, and Yin (arXiv:1902.09788, 2019).
It is known that operator splitting methods based on forward–backward splitting, Douglas–Rachford splitting, and Davis–Yin splitting decompose difficult optimization problems into simpler subproblems under proper convexity and smoothness assumptions. In this paper, we identify an envelope (an objective function), whose gradient descent iteration under a variable metric coincides with Davis–Yin splitting iteration. This result generalizes the Moreau envelope for proximal-point iteration and the envelopes for forward–backward splitting and Douglas–Rachford splitting iterations identified by Patrinos, Stella, and Themelis. Based on the new envelope and the stable–center manifold theorem, we further show that, when forward–backward splitting or Douglas–Rachford splitting iterations start from random points, they avoid all strict saddle points with probability one. This result extends the similar results by Lee et al. from gradient descent to splitting methods.
In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas–Rachford splitting. When an optimization program is infeasible, unbounded, or pathological, the iterates of Douglas–Rachford splitting diverge. Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for identification. In addition, for strongly infeasible problems the method produces a separating hyperplane and informs the user on how to minimally modify the given problem to achieve strong feasibility. As a first-order method, the proposed algorithm relies on simple subroutines, and therefore is simple to implement and has low per-iteration cost.