[proofplan]
We verify the definition of convexity directly. Given two right-hand sides $b_1, b_2$ with finite value-function values and a convex combination weight $\delta \in [0,1]$, we form $b = \delta b_1 + (1-\delta)b_2$ and show $\phi(b) \leq \delta \phi(b_1) + (1-\delta)\phi(b_2)$. The key construction is to take any pair of feasible points $x_1 \in X(b_1)$ and $x_2 \in X(b_2)$, form their convex combination $x = \delta x_1 + (1-\delta)x_2$, and use convexity of $X$, $h$, and $f$ to show that $x$ is feasible for $X(b)$ and its objective value is bounded by the convex combination of $f(x_1)$ and $f(x_2)$. Passing to infima over $x_1$ and $x_2$ completes the argument.
[/proofplan]
[step:Construct a feasible point for $X(b)$ via a convex combination]
Let $b_1, b_2 \in \mathbb{R}^m$ with $\phi(b_1)$ and $\phi(b_2)$ finite, and let $\delta \in [0,1]$. Set $b := \delta b_1 + (1-\delta)b_2$. Take any $x_1 \in X(b_1)$ and $x_2 \in X(b_2)$, and define
\begin{align*}
x := \delta x_1 + (1-\delta)x_2.
\end{align*}
Since $X$ is convex and $x_1, x_2 \in X$, we have $x \in X$. We verify that $x \in X(b)$, i.e., $h(x) \leq b$. Since each component $h_j$ is convex for $j = 1, \ldots, m$:
\begin{align*}
h_j(x) = h_j\bigl(\delta x_1 + (1-\delta)x_2\bigr) \leq \delta h_j(x_1) + (1-\delta)h_j(x_2) \leq \delta (b_1)_j + (1-\delta)(b_2)_j = b_j,
\end{align*}
where the first inequality is convexity of $h_j$ and the second uses $h(x_1) \leq b_1$ and $h(x_2) \leq b_2$ (primal feasibility of $x_1$ and $x_2$). This holds for all $j$, so $h(x) \leq b$ and $x \in X(b)$.
[guided]
The idea is to inherit feasibility for the combined constraint $b$ from feasibility for $b_1$ and $b_2$. Given $x_1 \in X(b_1)$ (so $x_1 \in X$ and $h(x_1) \leq b_1$) and $x_2 \in X(b_2)$ (so $x_2 \in X$ and $h(x_2) \leq b_2$), we form
\begin{align*}
x := \delta x_1 + (1-\delta)x_2.
\end{align*}
Since $X$ is convex by hypothesis and $x_1, x_2 \in X$, the convex combination $x$ belongs to $X$.
Now we must check the constraint $h(x) \leq b$. We need convexity of $h$ here: each component function $h_j: \mathbb{R}^n \to \mathbb{R}$ is convex, so
\begin{align*}
h_j(x) = h_j\bigl(\delta x_1 + (1-\delta)x_2\bigr) \leq \delta h_j(x_1) + (1-\delta)h_j(x_2).
\end{align*}
Since $x_1 \in X(b_1)$, we have $h_j(x_1) \leq (b_1)_j$. Since $x_2 \in X(b_2)$, we have $h_j(x_2) \leq (b_2)_j$. Using $\delta \geq 0$ and $1 - \delta \geq 0$:
\begin{align*}
\delta h_j(x_1) + (1-\delta)h_j(x_2) \leq \delta (b_1)_j + (1-\delta)(b_2)_j = b_j.
\end{align*}
This holds for every component $j = 1, \ldots, m$, so $h(x) \leq b$ componentwise and $x \in X(b)$. Without convexity of $h$, this step would fail — $h$ could bulge above the linear interpolation, making $x$ infeasible even though $x_1$ and $x_2$ are feasible.
[/guided]
[/step]
[step:Bound $\phi(b)$ using convexity of $f$]
Since $x \in X(b)$:
\begin{align*}
\phi(b) = \inf_{x' \in X(b)} f(x') \leq f(x).
\end{align*}
By convexity of $f$:
\begin{align*}
f(x) = f\bigl(\delta x_1 + (1-\delta)x_2\bigr) \leq \delta f(x_1) + (1-\delta)f(x_2).
\end{align*}
Combining:
\begin{align*}
\phi(b) \leq \delta f(x_1) + (1-\delta)f(x_2).
\end{align*}
[guided]
Since $x \in X(b)$, the value $f(x)$ is an upper bound on $\phi(b) = \inf_{x' \in X(b)} f(x')$. Now we exploit convexity of the objective $f$:
\begin{align*}
f(x) = f\bigl(\delta x_1 + (1-\delta)x_2\bigr) \leq \delta f(x_1) + (1-\delta)f(x_2).
\end{align*}
This is the definition of convexity applied to $f$ at the points $x_1, x_2 \in X$ with weight $\delta$. Chaining:
\begin{align*}
\phi(b) \leq f(x) \leq \delta f(x_1) + (1-\delta)f(x_2).
\end{align*}
At this stage the bound depends on the particular choices of $x_1 \in X(b_1)$ and $x_2 \in X(b_2)$. The next step removes this dependence.
[/guided]
[/step]
[step:Pass to infima over $x_1$ and $x_2$ to conclude convexity of $\phi$]
The inequality $\phi(b) \leq \delta f(x_1) + (1-\delta)f(x_2)$ holds for every $x_1 \in X(b_1)$ and every $x_2 \in X(b_2)$. Taking the infimum over $x_1 \in X(b_1)$ with $x_2$ fixed:
\begin{align*}
\phi(b) \leq \delta \inf_{x_1 \in X(b_1)} f(x_1) + (1-\delta) f(x_2) = \delta \phi(b_1) + (1-\delta)f(x_2).
\end{align*}
Now taking the infimum over $x_2 \in X(b_2)$:
\begin{align*}
\phi(b) \leq \delta \phi(b_1) + (1-\delta) \inf_{x_2 \in X(b_2)} f(x_2) = \delta \phi(b_1) + (1-\delta)\phi(b_2).
\end{align*}
Since $b_1, b_2 \in \mathbb{R}^m$ and $\delta \in [0,1]$ were arbitrary, $\phi$ is convex.
[guided]
The inequality $\phi(b) \leq \delta f(x_1) + (1-\delta)f(x_2)$ holds for all $x_1 \in X(b_1)$ and all $x_2 \in X(b_2)$. To extract $\phi(b_1)$ and $\phi(b_2)$, we pass to infima one variable at a time.
Fix $x_2 \in X(b_2)$. The left-hand side $\phi(b)$ does not depend on $x_1$, and the term $(1-\delta)f(x_2)$ is constant in $x_1$. So:
\begin{align*}
\phi(b) \leq \inf_{x_1 \in X(b_1)} \bigl[\delta f(x_1) + (1-\delta)f(x_2)\bigr] = \delta \inf_{x_1 \in X(b_1)} f(x_1) + (1-\delta)f(x_2) = \delta \phi(b_1) + (1-\delta)f(x_2),
\end{align*}
where we used $\delta \geq 0$ to pull the constant $\delta$ out of the infimum. Now the right-hand side depends only on $x_2$, and we repeat:
\begin{align*}
\phi(b) \leq \inf_{x_2 \in X(b_2)} \bigl[\delta \phi(b_1) + (1-\delta)f(x_2)\bigr] = \delta \phi(b_1) + (1-\delta)\phi(b_2).
\end{align*}
This is the convexity inequality for $\phi$. Since $b_1, b_2$ with finite values and $\delta \in [0,1]$ were arbitrary, $\phi$ is convex on its effective domain. The proof uses three ingredients — convexity of $X$, convexity of $h$ (to preserve feasibility), and convexity of $f$ (to bound the objective) — and nothing more.
[/guided]
[/step]
