We study various aspects of the basic computational problem of detecting approximate stationary points for continuous piecewise affine (PA) functions, including computational complexity, regularity conditions, and robustness in implementation. Specifically, for a PA function, we show that testing first-order approximate stationarity concepts in terms of commonly used subdifferential constructions is computationally intractable unless P=NP. To facilitate computability, we establish the first simultaneously necessary and sufficient condition for the validity of an equality-type (Clarke) subdifferential sum rule for a certain representation of arbitrary PA functions. Our main tools are nonsmooth analysis and polytope theory. Moreover, to address an important implementation issue, we introduce the first oracle-polynomial-time algorithm to detect near-approximate stationary points for PA functions. We complement our results with extensions to other subdifferentials and applications to a series of structured piecewise smooth functions, including rho-margin-loss SVM, piecewise affine regression, and neural networks with nonsmooth activation functions.

Local superlinear convergence of the semismooth Newton method usually requires the uniform invertibility of the generalized Jacobian matrix, e.g. BD-regularity or CD-regularity. For several types of nonlinear programming and composite-type optimization problems -- for which the generalized Jacobian of the stationary equation can be calculated explicitly -- this is characterized by the strong second-order sufficient condition. However, general characterizations are still not well understood. In this paper, we propose a strong second-order sufficient condition (SSOSC) for composite problems whose nonsmooth part has a generalized conic-quadratic second subderivative. We then discuss the relationship between the SSOSC and another second order-type condition that involves the generalized Jacobians of the normal map. In particular, these two conditions are equivalent under certain structural assumptions on the generalized Jacobian matrix of the proximity operator. Next, we verify these structural assumptions for $C^2$-strictly decomposable functions via analyzing their second-order variational properties under additional geometric assumptions on the support set of the decomposition pair. Finally, we show that the SSOSC is further equivalent to the strong metric regularity condition of the subdifferential, the normal map, and the natural residual. Counterexamples illustrate the necessity of our assumptions.

In this talk, we consider a class of nonconvex-(non)concave minimax optimization problems with a nonsmooth composite structure. We propose a smoothed proximal linear descent ascent (smoothed PLDA) method for tackling this class of problems and develop a novel analysis framework for studying the iteration complexity of the method. Central to this framework is the Kurdyka-Łojasiewicz (KŁ) property of the dual function, which provides insights into the interplay between the primal decrease and the dual increase. Consequently, we are able to obtain or match the best known complexity results for various minimax optimization problems. To further demonstrate the effectiveness of our analysis framework, we show that certain max-structured problem possesses the KŁ property with exponent zero under mild assumptions. We also establish algorithm-independent quantitative relationships among various stationarity concepts.