在 32 岁生日前夜，我最骄傲宝宝诞生了！
——我最 proud 的一篇 paper 终于上线了。

在 32 岁前夜+博士毕业+入职牛津的一周，终于把这篇文章上线

刚开始读博的时候，万万没想到，自己会一路做到优化世界里——Sum of Squares（SoS）问题，在 polynomial optimization 的世界里，始终对一件事抱有执念：如果能把一个多项式整理成 SoS 结构，就意味着它可以被一个 tight 的 SDP relaxation，问题由此变得 tractable，甚至在合适的假设下可以达到 polynomial time 的复杂度。
但显然，Hilbert 在第十七个问题给出：并非所有非负多项式都可以写成 SoS 的形式。过去一年里，我们反复追问的，是一个源自高阶优化方法的具体问题：在这些方法中反复出现的子问题——由对称三次多项式加上四次正则项构成的模型——它们究竟有没有 SoS 结构？在这篇文章中，我们给出了一个清晰而完整的答案：当正则化 (regularization) 所使用的范数（例如 Euclidean norm 或加权的 Euclidean norm）足够大时，这类由三次多项式加四次正则项构成的子问题，确实具有 sum of squares 结构。
这一点对我而言格外有意味。最早的时候，读 Parrilo 的文章时[Minimizing polynomial function, Sec 5.1]，他在数值实验中其实已经观察到了类似现象，也写道，没有相应的理论证明。而我们这一篇，恰好在这一处补齐了理论拼图。
从整体上看，我们刻画了quartically regularized polynomials 的 NP-hardness 边界，将 Hilbert 的经典结论延展到了一个新的多变量多项式子家族。同时，在regularization norm上，我们也发现了一个非常微妙、有趣的区别：当使用 Euclidean norm 或加权范数进行足够强的正则化时，非负性可以推出 SoS；但如果换成可分的四次范数（例如 s_1^4+⋯+s_n^4），即便正则化再强，这一结论依然不成立。

#牛津朱朱# #微博跨域计划# #教育有料# http://t.cn/AXqgW2Nz