Convexity of the Marginal (Optimal Value) Function

Convexity of the marginal function. Let $X$ and $Y$ be real vector spaces. Suppose $\varphi:X\times Y\to(-\infty,+\infty]$ is convex and the graph of $F:X\rightrightarrows Y$ is convex. Define the marginal function

\mu(x)=\inf\{\varphi(x,y):y\in F(x)\},

with $\inf\varnothing=+\infty$ . Then $\mu$ is convex on $X$ .

Interpretation

The theorem explains why optimal values in convex optimization vary convexly with parameters: joint convexity of the objective and convexity of the feasible graph survive partial minimization.

Proof idea

For $0<\lambda<1$ , choose feasible points $y_i\in F(x_i)$ with nearly minimal objective values. Convexity of the graph makes $\lambda y_1+(1-\lambda)y_2$ feasible at $\lambda x_1+(1-\lambda)x_2$ , and convexity of $\varphi$ gives the required inequality after the approximation error tends to zero.