Manifold Sampling for $\ell_1$ Nonconvex Optimization
提出流形采样算法，用于最小化具有已知结构的非光滑复合函数，通过将非光滑函数定义域的点分类到流形中，在信赖域框架内调整搜索方向，并证明算法产生的迭代点簇点是Clarke平稳点。
We present a new algorithm, called manifold sampling, for the unconstrained minimization of a nonsmooth composite function $h\circ F$ when $h$ has known structure. In particular, by classifying points in the domain of the nonsmooth function $h$ into manifolds, we adapt search directions within a trust-region framework based on knowledge of manifolds intersecting the current trust region. We motivate this idea through a study of $\ell_1$ functions, where it is trivial to classify objective function manifolds using zeroth-order information from the constituent functions $F_i$, and give an explicit statement of a manifold sampling algorithm in this case. We prove that all cluster points of iterates generated by this algorithm are stationary in the Clarke sense. We prove a similar result for a stochastic variant of the algorithm. Additionally, our algorithm can accept iterates that are points where $h$ is nondifferentiable and requires only an approximation of gradients of $F$ at the trust-region center. Numerical results for several variants of the algorithm show that using manifold information from additional points near the current iterate can improve practical performance. The best variants are also shown to be competitive, particularly in terms of robustness, with other nonsmooth, derivative-free solvers.