Canonical: https://knowlpedia.com/convex-analysis/convexity-of-the-marginal-optimal-value-function/

# Convexity of the Marginal (Optimal Value) Function

A jointly convex objective minimized over a convex feasible graph has a convex marginal value function.

**Convexity of the marginal function.** Let \(X\) and \(Y\) be real [vector spaces](https://knowlpedia.com/linear-algebra/vector-space/). Suppose \(\varphi:X\times Y\to(-\infty,+\infty]\) is [convex](https://knowlpedia.com/convex-analysis/convex-function-via-epigraph/) and the graph of \(F:X\rightrightarrows Y\) is convex. Define the [marginal function](https://knowlpedia.com/convex-analysis/marginal-optimal-value-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.
