凸函数的判断（中）： 凸函数复合与CVX中的凸函数辨识

前言

在上一篇我们总结了凸函数的一些基本性质和重要的一阶二阶条件， 在这一节，我们结合 CVX 工具包的一些使用定义来深入理解 如何快速判断函数是否为凸。 这有两点意义： 1. 学会正确地使用CVX工具包， 防止报错。 2. 学会判断哪些函数是凸函数 —— 既然 CVX可以判断你输入的问题是否为凸问题， 那么我们只需要学习其逻辑即可。

CVX 语法

我们直接从CVX的语法中对凸函数的辨别进行学习。 （最基本的凸函数，我们可以通过上篇所讲的 定义、一阶二阶条件得到， 本篇主要聚焦于 如同从基本的凸函数组合衍生出其他凸函数。 以及 如何快速判断某个函数是否可以写为凸函数的衍生）

CVX 定义标准的 凸函数表达形式为：

• 常数 或 仿射函数
• 标量的 p p p 次方 ( p ≥ 1 p\ge 1 p≥1 且为偶数)
• 多个凸函数的和
• 凸函数与凹函数的差
• 凸函数乘以一个正常数
• 凹函数乘以一个负常数

这是最基本的一些衍生。 但这显然远远不够， 事实上， 更大的一部分函数是通过复合函数得到的。 在CVX中， 每个函数都有两个属性， 分别是 凸性 和 单调性。

凸性分为： 凸， 凹， 仿射， 和 常数 四种 （并不完全互斥， 如仿射 显然既凸且凹） 单调性分为： 单调非增， 单调非减， 不单调。

如CVX中常用的几个函数， 对应的两个性质分别为： 将函数如此分类， 就是为了后续可以极为快捷地判断 复合函数的凸性。

假设函数 f ( x ) = h ( g ( x ) ) f(x) = h(g(x)) f(x)=h(g(x)), 当 h ( x ) h(x) h(x)为凸时， 需要满足：

• 如果 h h h 非减， 那么 g g g 必须为凸
• 如果 h h h 非增， 那么 g g g 必须为凹
• 如果 h h h 无单调性， 那么 g g g 必须为仿射

此时 f ( x ) f(x) f(x) 为凸。

反之， 如果 h ( x ) h(x) h(x) 为 凹时， 需要满足：

• 如果 h h h 非减， 那么 g g g 必须为凹
• 如果 h h h 非增， 那么 g g g 必须为凸
• 如果 h h h 无单调性， 那么 g g g 必须为仿射

和之前类似， 我们可以直接从一维情况论证： 由于 f ′ ′ ( x ) = h ′ ′ ( g ( x ) ) g ′ ( x ) 2 + h ′ ( g ( x ) ) g ′ ′ ( x ) f^{\prime \prime}(x)=h^{\prime \prime}(g(x)) g^{\prime}(x)^{2}+h^{\prime}(g(x)) g^{\prime \prime}(x) f′′(x)=h′′(g(x))g′(x)2+h′(g(x))g′′(x)

凹凸性决定了 h ′ ′ h^{\prime\prime} h′′的正负， 而单调性决定了 h ′ h^\prime h′的正负。

简单的记忆方式： 若 h ( x ) h(x) h(x) 非减， 那么 当 g g g 和 h h h 的凸性相同时， f f f 也有相同的凸性。若 h h h 非增， 当 g g g 与 h h h 凸性相反时， f f f 与 h h h 有相同的凸性。

简单来说： f f f与 h h h的凸性一致， 当 h h h 非减时 g g g 和 h h h 同凸性。

当 h h h 的变量为向量时， 则要求 h h h 在其每维分量都非减/非增。 具体而言， 此时的 x x x 仍是标量， g ： R → R n g：R\rightarrow R^n g：R→Rn, f : R n → R f:R^n\rightarrow R f:Rn→R。 此时， g ( x ) g(x) g(x) 可看作 g ( x ) = [ g 1 ( x ) ⋯ g n ( x ) ] g(x)=[g_1(x) \cdots g_n(x)] g(x)=[g1​(x)⋯gn​(x)]， 需要 g i ( x ) g_i(x) gi​(x) 均为凸函数/凹函数。 当 x x x 也为向量时， 将更加复杂。

CVX 实例

1. max ⁡ ( ∣ x ∣ ) \max(|x|) max(∣x∣) max( abs( x ) ): 这是一个凸函数， 因为 max ⁡ \max max是一个凸函数且非减， 而 ∣ x ∣ |x| ∣x∣为凸函数。
2. sum( square( x ) )： 求和函数是一个仿射函数且在每一维上非减。 而 x 2 x^2 x2 是在每一维上 ( g i ( x ) g_i(x) gi​(x)) 是一个凸函数， 因此该函数也为凸函数。
3. sum( sqrt( x ) )： 相对的， 由于 x \sqrt{x} x ​ 是凹函数， 因此此函数也为凹。 可以看到， 若 h h h 为 仿射函数， 则当其非减时， 复合函数凸性和 g g g一致。
4. sqrt(f'*x) + min(4,1.3-norm(A*x-b))： CVX可以直接认出这是凹函数。
5. sqrt( sum( square( x ) ) )： 这个函数其实就是 norm(x)， 但如果以一开始这个形式写 CVX将会报错。 因为 x \sqrt{x} x ​ 是凹函数且非减， 因此只有在内部函数也为凹时，可以直接判定复合函数的凸性。 然而此时内部函数为凸。
6. square( square( x ) + 1 )： 这个函数显然是凸的，因为他可以写为： ( x 2 + 1 ) 2 = x 4 + 2 x 2 + 1 \left(x^{2}+1\right)^{2}=x^{4}+2 x^{2}+1 (x2+1)2=x4+2x2+1, 然而， 这个语法也无法被CVX识别， 这是因为 外层的 square()并不满足非减的要求。 当x 从 -1 到 0 时， 函数值却减小了。