# 优化 | 非光滑优化的光滑化

#### 导读：

Nesterov一生对优化界贡献无数，而其最为出名的工作都是在当时对很多优化研究者反直觉的结果，最出名的Nesterov加速算法（Nesterov's accelerated method）先不提（几十年来人们都在试图从各种方式理解为何这个简单的算法就能“加速”了），这边我们要讲的Nesterov's smoothing也是很神奇，是说 对于广泛的非光滑函数，我们可以将之光滑化并近似得到一个快得多的光滑优化里的算法求解。

## 四、更多的应用（其一）：Packing LP

Nesterov's smoothing看起来抽象：需要找一个 d 函数算共轭似乎不太容易，但实际上它的应用非常非常广泛。Nesterov的原始paper（[3]）就讨论了matrix game和location problem的smoothing做法。之后自然是带起了一波热潮在数不尽的非光滑优化问题里产生了非常有效的新算法。这里作为结尾，我提供一个个人非常喜欢的应用，即用Nesterov's smoothing解packing和covering LP（linear program，线性规划）。

## 五、更多的应用（其二）：Dual Decompositio

1 对偶函数可微定理(Dual Function Differentiability Theorem)

#### 1.3 什么条件下对偶函数可微？

2. 改进版的对偶分解： Nesterov's Smoothing + Accelerated Method

#### 2.2 Apply Nesterov's Accelerated Method

2.3 Efficiency： smoothing parameter的选取

[1] A. Nemirovski and D. Yudin, Information-based Complexity of Mathematical Programming, Izvestia AN SSSR, Ser. Tekhnicheskaya Kibernetika (the journal is translated to English as Engineering Cybernetics. Soviet J. Computer & Systems Sci.), 1, 1983.

[2] Y. Chen, Lecture Notes (ELE522 Large-scale Optimization for Data Sience): Smoothing for Nonsmooth Optimization, Princeton University, 2019

[3] Y. Nesterov, Smooth Minimization of Non-smooth Functions, Mathematical Programming, 103(1):127-152, 2005.

[4] Z. Allen-Zhu and L. Orecchia, Nearly Linear-time Packing and Covering LP Solvers, Mathematical Programming, 175(1-2):307-353, 2019.

[5] Y. Nesterov, Lectures on Convex Optimization, 137, Springer, 2018.

[6] 王奇超，文再文，蓝光辉，袁亚湘，《优化算法复杂度分析简介》，2018.

[7] Y. Nesterov, A Method of Solving A Convex Programming Problem with Convergence Rate O(1/k^2), Doklady ANSSR (translated as Soviet Math. Docl.) 269, 543-547, 1983.

[8] I. Necoara and J. A. K. Suykens, Application of a Smoothing Technique to Decomposition in Convex Optimization, IEEE Transactions on Automatic Control, 53(11):2674-2679, 2008.

[9] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Englewood Cliffs, NJ: Prentice-Hall, 1989.

-End-

*延伸阅读

CV细分方向交流群

△长按添加极市小助手

△长按关注极市平台