保留凸性的一种方式：在一个凸集上最小化一个联合凸函数形成的函数仍是凸函数

该定理表述如下X XX是一个凸集Y ( x ) Y(x)Y(x)是定义在X XX上的非空集合集合C { ( x , y ) ∣ x ∈ X , y ∈ Y ( x ) } C\{(x,y)\mid x\in X, y\in Y(x)\}C{(x,y)∣x∈X,y∈Y(x)}是一个凸集g ( x , y ) g(x, y)g(x,y)是定义在C CC上的一个凸函数那么下面函数f ( x ) inf ⁡ y ∈ Y ( x ) g ( x , y ) f(x)\inf_{y\in Y(x)}g(x,y)f(x)y∈Y(x)inf​g(x,y)也是一个凸函数。证明方法利用ϵ \epsilonϵ逼近证明根据f ( x ) f(x)f(x)的定义对于任意x 1 ∈ X x_1\in Xx1​∈X设inf ⁡ y ∈ Y ( x 1 ) g ( x 1 , y ) g ( x 1 , y 1 ∗ ) \inf_{y\in Y(x_1)}g(x_1,y)g(x_1,y_1^\ast)y∈Y(x1​)inf​g(x1​,y)g(x1​,y1∗​)则f ( x 1 ) g ( x 1 , y 1 ∗ ) f(x_1)g(x_1,y_1^\ast)f(x1​)g(x1​,y1∗​)根据 infinum 的定义对任意一个正数ϵ \epsilonϵ总存在一个y 1 ∈ Y ( x 1 ) y_1 \in Y(x_1)y1​∈Y(x1​)使得f ( x 1 ) ϵ g ( x 1 , y ∗ ) ϵ ≥ g ( x 1 , y 1 ) f(x_1)\epsilong(x_1,y^\ast)\epsilon\geq g(x_1,y_1)f(x1​)ϵg(x1​,y∗)ϵ≥g(x1​,y1​)即f ( x 1 ) ϵ ≥ g ( x 1 , y 1 ) (1) f(x_1)\epsilon\geq g(x_1,y_1)\tag{1}f(x1​)ϵ≥g(x1​,y1​)(1)同理对于任意x 2 ∈ X x_2\in Xx2​∈X以及任意一个正数ϵ \epsilonϵ总存在一个y 2 y_2y2​使得f ( x 2 ) ϵ ≥ g ( x 2 , y 2 ) (2) f(x_2)\epsilon\geq g(x_2,y_2)\tag{2}f(x2​)ϵ≥g(x2​,y2​)(2)因此θ f ( x 1 ) ( 1 − θ ) f ( x 2 ) ≥ θ g ( x 1 , y 1 ) ( 1 − θ ) g ( x 2 , y 2 ) − ϵ ≥ g ( θ 1 x 1 ( 1 − θ ) x 2 , θ 1 y 1 ( 1 − θ ) y 2 ) − ϵ ≥ f ( θ 1 x 1 ( 1 − θ ) x 2 ) − ϵ \begin{aligned} \theta f(x_1)(1-\theta)f(x_2)\geq \theta g(x_1,y_1)(1-\theta) g(x_2,y_2)-\epsilon\\ \geq g(\theta_1 x_1(1-\theta)x_2,\theta_1y_1(1-\theta)y_2)-\epsilon\\ \geq f(\theta_1 x_1(1-\theta)x_2)-\epsilon \end{aligned}θf(x1​)(1−θ)f(x2​)​≥θg(x1​,y1​)(1−θ)g(x2​,y2​)−ϵ≥g(θ1​x1​(1−θ)x2​,θ1​y1​(1−θ)y2​)−ϵ≥f(θ1​x1​(1−θ)x2​)−ϵ​因为上式对任意ϵ 0 \epsilon0ϵ0都成立必然对ϵ 0 \epsilon0ϵ0也成立(从极限的角度理解: 不等式集合是闭集极限点也必须满足不等式这一点没那么容易理解)得证。这其实就是利用了如果a ≥ b n ∀ n a≥b_n\quad \forall na≥bn​∀n​且b n → b , b_n\rightarrow b,bn​→b,那么a ≥ b . a≥b.a≥b.也可以在此处用反证法证令A θ f ( x 1 ) ( 1 − θ ) f ( x 2 ) A\theta f(x_1)(1-\theta)f(x_2)Aθf(x1​)(1−θ)f(x2​),B f ( θ 1 x 1 ( 1 − θ ) x 2 ) B f(\theta_1 x_1(1-\theta)x_2)Bf(θ1​x1​(1−θ)x2​), 假设A B ABAB,ϵ ( B − A ) / 2 \epsilon(B-A)/2ϵ(B−A)/2,A ≥ B − ϵ B − ( B − A ) / 2 ( A B ) / 2 A A\geq B-\epsilonB-(B-A)/2(AB)/2AA≥B−ϵB−(B−A)/2(AB)/2A推出矛盾的A A AAAA. 所以A ≥ B A\geq BA≥B.□ \Box□若函数g gg是拟凸函数时也能同样推导出f ff是拟凸函数。参考资料12Boyd, S., Boyd, S. P., Vandenberghe, L. (2004). Convex optimization. Cambridge university press (pp 87-88). ↩︎Porteus, E. L. (2002). Foundations of stochastic inventory theory. Stanford University Press (pp 227-228). ↩︎