Monotone, Convex and First Order Maps in Optimization of Nonsmooth Lipschitz Functions