复合凸优化问题的最优值函数凸性咨询

嘿，这个问题问得很到位！咱们来仔细拆解分析：

首先先明确你给出的问题背景：
你有两个单约束的优化问题：
$$
\begin{align*}
F_1(a)=&\min_x f(x)\
&\text{s.t.}~ g_1(x)\leq a,
\end{align*}
$$
$$
\begin{align*}
F_2(b)=&\min_x f(x)\
&\text{s.t.}~ g_2(x)\leq b.
\end{align*}
$$
且已知 $F_1(a)$ 和 $F_2(b)$ 都是关于各自参数的凸函数。现在你想知道，同时加入两个约束后的最优值函数 $F(a,b)$：
$$
\begin{align*}
F(a,b)=\min_x &f(x)\
\text{s.t.}~ &g_1(x)\leq a,\
&g_2(x)\leq b.
\end{align*}
$$
是否也是关于 $(a,b)$ 的凸函数？

结论先行：是的，$F(a,b)$ 是关于 $(a,b)$ 的凸函数 #

具体解释： #

要验证这一点，我们可以从凸函数的核心定义出发推导：
对于任意的 $(a_1,b_1), (a_2,b_2)$ 属于 $F(a,b)$ 的定义域，以及任意的 $\lambda \in [0,1]$，我们需要证明：
$$F(\lambda a_1 + (1-\lambda)a_2, \lambda b_1 + (1-\lambda)b_2) \leq \lambda F(a_1,b_1) + (1-\lambda)F(a_2,b_2)$$

假设 $x_1$ 是 $F(a_1,b_1)$ 的最优解（即 $f(x_1)=F(a_1,b_1)$，且满足 $g_1(x_1)\leq a_1, g_2(x_1)\leq b_1$），$x_2$ 是 $F(a_2,b_2)$ 的最优解（同理满足对应约束）。
既然 $F_1$ 和 $F_2$ 是凸函数，这隐含了原问题中的 $f(x)$ 是凸函数，$g_1(x),g_2(x)$ 也是凸函数——这正是单约束最优值函数为凸的核心前提。

那么对于凸函数 $f,g_1,g_2$，我们有：

• $f(\lambda x_1 + (1-\lambda)x_2) \leq \lambda f(x_1) + (1-\lambda)f(x_2) = \lambda F(a_1,b_1) + (1-\lambda)F(a_2,b_2)$
• $g_1(\lambda x_1 + (1-\lambda)x_2) \leq \lambda g_1(x_1) + (1-\lambda)g_1(x_2) \leq \lambda a_1 + (1-\lambda)a_2$
• $g_2(\lambda x_1 + (1-\lambda)x_2) \leq \lambda g_2(x_1) + (1-\lambda)g_2(x_2) \leq \lambda b_1 + (1-\lambda)b_2$

这说明点 $\lambda x_1 + (1-\lambda)x_2$ 是 $F(\lambda a_1 + (1-\lambda)a_2, \lambda b_1 + (1-\lambda)b_2)$ 问题的可行解，且对应的目标函数值不超过 $\lambda F(a_1,b_1) + (1-\lambda)F(a_2,b_2)$。而 $F(\cdot,\cdot)$ 是该问题的最小值，因此上述不等式成立，完全满足凸函数的定义。

简单来说，当单个约束的最优值函数是凸的，意味着原问题的目标和约束都是凸的，那么多个凸约束组合后的最优值函数自然也是凸的——这是凸优化中最优值函数的一个经典性质。

备注：内容来源于stack exchange，提问作者Harry556