Convert any convex optimization problem to a linear objective

Question

Wikipedia claims that:

Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form.

Is there a simple proof for the above?

Answer 1

Yes. Consider the following problem: \begin{equation} \begin{array}{ll} \text{minimize}_x & f(x) \\ \text{subject to} & x \in C \end{array} \tag{A} \end{equation} where $f$ is a convex function and $C$ is a convex set. The constraint $x\in C$ could be represented by a list of convex inequalities and linear equations. For simplicity, we will assume that $C\subseteq \mathop{\textrm{dom}} f$; that is, the function is defined on all of $C$. If that is not the case, then just replace $C$ with $C\cap\textrm{dom}(f)$.

Now consider: \begin{equation} \begin{array}{ll} \text{minimize}_{x,y} & y \\ \text{subject to} & x \in C \\ & f(x) \leq y \end{array} \tag{B} \end{equation} This problem has a linear objective, and is equivalent to the previous problem. It's probably obvious, but to prove it does require some care (indeed perhaps even more than I am offering here):

1. If $x$ is feasible for (A), then $(x,y)$ is feasible for (B), where $y$ is any value satisfying $f(x) \leq y$.
2. If $(x,y)$ is feasible for (B), then $x$ is feasible for (A), since $x\in C$.
3. If $x$ is optimal for (A), then $(x,y)$ is optimal for (B), where $y=f(x)$. Suppose this is not true; that is, suppose a feasible point $(\bar{x},\bar{y})$ satisfies $\bar{y}<f(x)$. Then we have $f(\bar{x})\leq \bar{y} <f(x)$. But according to (2), $\bar{x}$ is also feasible for (A), and it has a lower objective value, contradicting the claim that $x$ is optimal.
4. Likewise, if $(x,y)$ is optimal for (B), then $x$ is optimal for (A). Suppose this were not the case; that is, suppose a feasible point $\bar{x}$ satisfies $f(\bar{x})<y$. But per (1), $(\bar{x},\bar{y})$ must be feasible for (B), where we choose $\bar{y}=f(\bar{x})$. This point has a lower objective value, contradicting our claim that $(x,y)$ is optimal.

(This last one also provides proof of the evident fact that if $(x,y)$ is an optimal point for (B), it must be the case that $f(x)=y$.)

Therefore, all feasible points for (A) immediately lead to feasible points for (B), and vice versa; and all optimal points for (A) immediately lead to optimal points for (B), and vice versa. Hence the problems are equivalent.

Answer 2

If the original problem is $\min_{x \in K} f(x)$ where $K \subset \mathbb{R}^n$ and $f$ are convex, then letting $K' := K \times \mathbb{R}$, we can rewrite this as $\min_{(x,t) \in K'} t$ subject to $t \ge f(x)$. The objective function $(x,t) \mapsto t$ is linear, and the constraint set $K' \cap \{(x,t):t \ge f(x)\}$ is convex.