We study the class of nonsmooth nonconvex problems in which the objective is to minimize the difference between a continuously differentiable function (possibly nonconvex) and a convex (possibly nonsmooth) function over a convex polytope. This general class contains many types of problems, including difference of convex functions (DC) problems, and as such, can be used to model a variety of applications. Our goal is to attain a point satisfying the stationarity necessary 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 similar settings to the one we study. In this paper we prove that stationarity in our model can be characterized by a finite number of directions that positively span the set of feasible directions. We then use the latter to develop two methods, one deterministic and one random, whose accumulation points are proved to be stationary points. Supplementing discussion on positively spanning sets, and corresponding methods to obtain members of such sets, are also presented. Numerical experiments illustrate the appeal of obtaining a stationary point and the advantage of using the random method to do so.