凸性保持运算：三类复合函数的凸性判断与证明方法问询

已知$f$、$g$、$q$均为凸函数，以下逐个分析三个衍生函数的凸性：

1. $h(x,y)=(f(x)+g(y))^2$ #

该函数仅当$f(x)+g(y) \geq 0$对所有$x,y$成立时，才是凸函数，证明如下：

• 凸函数的和保持凸性，因此$f(x)+g(y)$是关于$(x,y)$的凸函数。
• 外层函数$k(t)=t^2$是凸函数，但仅在$t \geq 0$时非减。根据复合函数凸性规则：当外层凸函数非减且内层函数凸时，复合函数凸。
• 若$f(x)+g(y)$可取负值，存在反例：令$f(x)=x^{2-2$，$g(y)=y}2-2$（均为凸函数），则$h(x,y)=(x^2+y2-4)^2$。在点$(0,0)$处，其Hessian矩阵为负定矩阵，说明函数在该点附近是凹的，因此整体非凸。

2. $\sqrt{f(x)g(y)}$ #

该函数一般不是凸函数，反例如下：

• 取$f(x)=x^2$，$g(y)=y2$（均为凸函数），则$\sqrt{f(x)g(y)}=|xy|$，当$x,y$同号时为$xy$，这是双线性函数，不满足凸函数定义（例如取$(1,1)$和$(-1,-1)$，中点函数值为0，而两点函数值的平均为1，$0 < 1$，违反凸函数的不等式要求）。

3. $q(f(x))$ #

该函数当且仅当$q$是凸且非减函数时，才是凸函数，证明如下：

• 根据复合函数凸性核心规则：若外层函数$q(t)$凸且非减，内层函数$f(x)$凸，则对任意$\lambda \in [0,1]$，有：
  $$q(f(\lambda x_1 + (1-\lambda)x_2)) \leq q(\lambda f(x_1) + (1-\lambda)f(x_2)) \leq \lambda q(f(x_1)) + (1-\lambda)q(f(x_2))$$
  第一步利用$f$的凸性和$q$的非减性，第二步利用$q$的凸性。
• 若$q$非增，即使$q$是凸函数，复合后可能为凹函数：例如$q(t)=\max(0,2-t)$（凸函数），$f(x)=x$（凸函数），则$q(f(x))=\max(0,2-x)$是凹函数。

复合函数凸性判断核心方法 #

基本运算保持规则 #

• 非负线性组合：凸函数的非负加权和仍为凸函数；
• 逐点最大值/上确界：多个凸函数的逐点最大值，或凸函数族的逐点上确界仍为凸函数。

单变量复合规则 #

设$h(x)=k(t(x))$，则：

• 若$k$凸且非减，$t$凸 → $h$凸；
• 若$k$凸且非增，$t$凹 → $h$凸；
• 若$k$凹且非减，$t$凹 → $h$凹；
• 若$k$凹且非增，$t$凸 → $h$凹。

多变量复合验证 #

对于多元复合函数（如$h(x,y)=k(f(x),g(y))$），可通过以下方式验证：

1. 利用凸函数定义：对任意$\lambda \in [0,1]$，验证$h(\lambda(x_1,y_1)+(1-\lambda)(x_2,y_2)) \leq \lambda h(x_1,y_1)+(1-\lambda)h(x_2,y_2)$；
2. 计算Hessian矩阵，验证其半正定性（适用于二阶可导函数）。

内容的提问来源于stack exchange，提问作者Cloudius