This paper studies the class of nonsmooth nonconvex problems in which the difference between a continuously differentiable function and a convex nonsmooth function is minimized over linear constraints. Our goal is to attain a point satisfying the stationarity necessary optimality condition, defined as the lack of feasible descent directions. Although elementary in smooth optimization, this condition is nontrivial when the objective function is nonsmooth, and correspondingly, there are very few methods that obtain stationary points in such settings. We prove that stationarity in our model can be characterized by a finite number of directions, and develop two methods, one deterministic and one random, that use these directions to obtain stationary points. Numerical experiments illustrate the benefit of obtaining a stationary point and the advantage of using the random method to do so.