  This paper proposes low-complexity algorithms for finding approximate
second-order stationary points (SOSPs) of problems with smooth non-convex
objective and linear constraints. While finding (approximate) SOSPs is
computationally intractable, we first show that generic instances of the
problem can be solved efficiently. More specifically, for a generic problem
instance, certain strict complementarity (SC) condition holds for all
Karush-Kuhn-Tucker (KKT) solutions (with probability one). The SC condition is
then used to establish an equivalence relationship between two different
notions of SOSPs, one of which is computationally easy to verify. Based on this
particular notion of SOSP, we design an algorithm named the Successive
Negative-curvature grAdient Projection (SNAP), which successively performs
either conventional gradient projection or some negative curvature based
projection steps to find SOSPs. SNAP and its first-order extension SNAP$^+$,
require $\mathcal{O}(1/\epsilon^{2.5})$ iterations to compute an $(\epsilon,
\sqrt{\epsilon})$-SOSP, and their per-iteration computational complexities are
polynomial in the number of constraints and problem dimension. To our
knowledge, this is the first time that first-order algorithms with polynomial
per-iteration complexity and global sublinear rate have been designed to find
SOSPs of the important class of non-convex problems with linear constraints.
