On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient
Xingyu Zhou Department of ECE The Ohio State University
Abstract
We provide a simple proof for the Fenchel duality between strong convexity and Lipschitz continuous gradient. To this end, we first establish equivalent conditions of convexity for a general function that may not be differentiable. By utilizing these equivalent conditions, we can directly obtain equivalent conditions for strong convexity and Lipschitz continuous gradient. Based on these results, we can easily prove Fenchel duality. Beside this main result, we also identify several conditions that are implied by strong convexity or Lipschitz continuous gradient, but are not necessarily equivalent to them. This means that these conditions are more general than strong convexity or Lipschitz continuous gradient themselves.
中文速览
强凸性（strong convexity）与Lipschitz连续梯度之间存在一种对偶关系——Fenchel对偶，即一个函数的强凸性与其共轭函数的梯度Lipschitz连续性可以相互转化，但原有证明篇幅冗长、难以看清核心思路。本文的做法是：先把光滑函数凸性的经典等价条件推广到不可微函数（用次梯度替换梯度），再以此为基础系统整理出强凸性和Lipschitz连续梯度各自的等价条件及若干更弱的蕴含条件，最后借助Fenchel共轭的基本性质，用极为简洁的几步推导完成对偶定理的证明。最终结果与已知结论一致：若$f$以参数$\mu$强凸，则其共轭$f^*$的梯度以$1/\mu$为Lipschitz常数；反之亦然。这一工作的价值在于，它不仅让经典结论的来龙去脉一目了然，还顺带揭示了Polyak-Łojasiewicz不等式等比强凸性更一般的条件，为优化领域的后续研究提供了清晰可复用的分析框架。
原文 arXiv:1803.06573;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1803.06573v1