# Convert any convex optimization problem to a linear objective

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?

• I've edited the title to better reflect the content. It is certainly not the case that any convex problem can be converted to a purely linear problem. That sentence only refers to linearizing the objective function. – Michael Grant Dec 22 '15 at 20:29

Yes. Consider the following problem: $$\begin{array}{ll} \text{minimize}_x & f(x) \\ \text{subject to} & x \in C \end{array} \tag{A}$$ 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{array}{ll} \text{minimize}_{x,y} & y \\ \text{subject to} & x \in C \\ & f(x) \leq y \end{array} \tag{B}$$ 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.

• Sorry to bring up an old post, I was just curious: there are no assumptions about the continuity of $f$ in this proof. Is it sufficient to show the equivalence between optimal solutions for the problems, when the optimal solutions might not exist? – Aurantium Feb 24 '18 at 11:05
• Yes, it is sufficient. Because if a solution does not exist for one, it will not exist for the other. The logic is two-way. – Michael Grant Feb 24 '18 at 20:08
• Sorry, I meant the situation where, for example, the set $C$ is not closed and the optimal value is not reached by any feasible point, but rather as a limit of a sequence of feasible points. It seems that the proof does not consider a situation like this, but your assumption about $C$ was only convexity. – Aurantium Feb 24 '18 at 22:17
• None of that matters here. We have a one to one correspondence between solutions from one form and solutions to the other. – Michael Grant Feb 24 '18 at 22:18
• (If the solution is only obtained asymptotically, that will be the case for both problems.) – Michael Grant Feb 24 '18 at 22:23

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.

• Yes, but this doesn't prove the equivalence of the two problems (though I do believe it is somewhat obvious.) – Michael Grant Dec 22 '15 at 17:09