我们为什么要关心一个函数的凸凹性呢？——理解凸函数与非凸函数( 二 ) _函数

在复杂的理论中，解决问题所需的“时间”是根据计算机完成任务所需的步骤数来衡量的。这取决于问题有多少个部分展开。例如，要找到一列数字中的最大项，您需要查看每个单独的数字，并将其与您迄今为止找到的最大数字进行比较。在算法中有 n 步，所以我们说它的执行时间是与 n 成正比的。其他问题可能与执行时间 n2，n3，或 n^k (k 是正数) 。
这当然意味着执行时间的增长随着 n 的增长而增长相当快，初始问题的规模会变大。但与以 n 的指数倍增长的执行时间相比，这根本算不了什么。例如，一个正比于 2^n 的问题。
执行时间与某个多项式中的 n 成正比的算法称为多项式时间算法。它们被认为是相对较快的。这种算法可以解决的一类称为P问题。

文章插图

▲ 知道函数是否为凸函数可以帮助解决最小化问题，比如最小化汽车的燃料使用量。
但还有一类问题用 NP 表示(代表不确定时间多项式) 。它的性质是如果有人给你这个问题的答案，你可以检查多项式时间是否正确。但是你能在多项式时间内从头开始解决这些问题吗？没有人确切知道。这是著名的 P=NP 问题的主题，这是数学中最大的开放问题之一。尽管还没有人能证明，一般的直觉是你不能： NP 问题的解可以被验证，但不能在多项式时间内找到。换句话说，P 不等于 NP 。
现在我们回到凸性的问题。问题是一个算法的执行时间如何随着多项式中项数的增加而增长，该算法检查任意多项式的凸性。研究人员在他们的论文中表明，这个问题是 NP-困难的。这意味着，粗略地说，它至少和 NP 类中的任何问题一样难。所以除非有人证明了 P=NP，否则我们可以假设"它是凸的吗"这个问题不能用一种有效的时间方法来回答一个任意多项式。随着多项式中变量数量的增加，回答这个问题所需的时间也会激增。
但幸运的是，有一个漏洞。还有另一个性质，称为平方和凸性(sum of squared convexity)，它可以在多项式时间内检验。任何平方和为凸的多项式也是凸的。对于你在现实生活中可能遇到的大部分多项式来说，反过来也成立的：如果它们是凸的，它们也是平方和也为凸函数。所以在这些例子中，检验平方和凸性就足够了。这给了我们乐观的理由：也许凸性问题的困难在于一些非常棘手的多项式例子，但通常它们不会出现在实际应用中。