These lecture notes for a graduate course cover generalized derivative
concepts useful in deriving necessary optimality conditions and numerical
algorithms for nondifferentiable optimization problems in inverse problems,
imaging, and PDE-constrained optimization. Treated are convex functions and
subdifferentials, Fenchel duality, monotone operators and resolvents,
Moreau--Yosida regularization, proximal point and (some) first-order splitting
methods, Clarke subdifferentials, and semismooth Newton methods. The required
background from functional analysis and calculus of variations is also briefly
summarized.

这篇论文讲述了推导逆问题、图像处理和 PDE 约束优化中的非可微优化问题所需的必要最优条件和数值算法，涵盖广义导数概念，凸函数和次微分，Fenchel 对偶，单调算子和解算子，Moreau-Yosida 正则化，极值点和（一些）一阶分裂方法，Clarke 次微分和半光滑牛顿方法，并简要总结了从函数分析和变分法中所需的背景。

非光滑分析与优化

Nonsmooth Analysis and Optimization

We obtain bounds on estimation error rates for regularization procedures of
the form \begin{equation*}
\hat f \in {\rm argmin}_{f\in
F}\left(\frac{1}{N}\sum_{i=1}^N\left(Y_i-f(X_i)\right)^2+\lambda
\Psi(f)\right) \end{equation*} when $\Psi$ is a norm and $F$ is convex.
Our approach gives a common framework that may be used in the analysis of
learning problems and regularization problems alike. In particular, it sheds
some light on the role various notions of sparsity have in regularization and
on their connection with the size of subdifferentials of $\Psi$ in a
neighbourhood of the true minimizer.
As `proof of concept' we extend the known estimates for the LASSO, SLOPE and
trace norm regularization.

本文通过研究规则化问题，得出了估计误差率的界限，并扩展了 LASSO、SLOPE 和迹范数规则化的已知估计，为学习问题和规则化问题的分析提供了一个共同的框架，特别是在规则化中，各种稀疏概念的作用以及它们与真实最小化器附近的 Ψ 的亚微分的大小的联系方面。

正则化与小球方法 I: 稀疏恢复

Regularization and the small-ball method I: sparse recovery

We extend the well-known BFGS quasi-Newton method and its memory-limited
variant LBFGS to the optimization of nonsmooth convex objectives. This is done
in a rigorous fashion by generalizing three components of BFGS to
subdifferentials: the local quadratic model, the identification of a descent
direction, and the Wolfe line search conditions. We prove that under some
technical conditions, the resulting subBFGS algorithm is globally convergent in
objective function value. We apply its memory-limited variant (subLBFGS) to
L_2-regularized risk minimization with the binary hinge loss. To extend our
algorithm to the multiclass and multilabel settings, we develop a new,
efficient, exact line search algorithm. We prove its worst-case time complexity
bounds, and show that our line search can also be used to extend a recently
developed bundle method to the multiclass and multilabel settings. We also
apply the direction-finding component of our algorithm to L_1-regularized risk
minimization with logistic loss. In all these contexts our methods perform
comparable to or better than specialized state-of-the-art solvers on a number
of publicly available datasets. An open source implementation of our algorithms
is freely available.

本研究将众所周知的 BFGS 拟牛顿方法及其内存限制变种 LBFGS 扩展到非平滑凸目标的优化，提出了 subBFGS 算法，其全局收敛，并使用其记忆限制变体（subLBFGS）来最小化 L2 正则化风险并开发了新的多类和多标签设置下的准确搜索算法。