2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Dec 22 '15 at 20:29
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Aurantium Feb 24 '18 at 11:05
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Feb 24 '18 at 20:08
  • $\begingroup$ 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. $\endgroup$ – Aurantium Feb 24 '18 at 22:17
  • $\begingroup$ None of that matters here. We have a one to one correspondence between solutions from one form and solutions to the other. $\endgroup$ – Michael Grant Feb 24 '18 at 22:18
  • $\begingroup$ (If the solution is only obtained asymptotically, that will be the case for both problems.) $\endgroup$ – Michael Grant Feb 24 '18 at 22:23
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.