Nonsmooth convex-concave saddle point problems with cardinality penalties

Abstract

In this paper, we focus on a class of convexly constrained nonsmooth convex–concave saddle point problems with cardinality penalties. Although such nonsmooth nonconvex–nonconcave and discontinuous min–max problems may not have a saddle point, we show that they have a local saddle point and a global minimax point, and some local saddle points have the lower bound properties. We define a class of strong local saddle points based on the lower bound properties for stability of variable selection. Moreover, we give a framework to construct continuous relaxations of the discontinuous min–max problems based on convolution, such that they have the same saddle points with the original problem. We also establish the relations between the continuous relaxation problems and the original problems regarding local saddle points, global minimax points, local minimax points and stationary points. Finally, we illustrate our results with distributionally robust sparse convex regression, sparse robust bond portfolio construction and sparse convex–concave logistic regression saddle point problems.