Any optimization problem can be expressed as one with a linear objective

Question

For any standard optimization problem(think linear programming, convex, non-convex problem), would it be possible to express the optimization problem as one with a linear objective?

Answer 1

The perhaps surprising answer is YES, and it doesn't involve Taylor expansion or any other approximations.

First, presume we have an unconstrained optimization problem, $$\min_x f(x)$$ for some vector argument $x$. This can be reformulated as a problem with linear objective by moving the original objective function to the constraints and adding an additional optimization (decision) variable, the scalar t. $$\min_{x,t} t$$ $$\text{subject to } f(x) \le t$$ This is known as the epigraph formulation.

This can easily be extended to a constrained optimization problem $$\min_x f(x)$$ $$\text{subject to } x \in \Xi \text{, where } \Xi \text{ is some constraint set.}$$ as follows: $$\min_{x,t} t$$ $$\text{subject to } f(x) \le t, x \in \Xi$$

In fact, this is the basis for certain problems, such as Second Order Cone Problems (SOCP) having a linear objective function as standard form for certain optimization solvers. For instance, the problem $$\min_{x} \|Ax-b\|_2$$ $$\text{subject to } Cx = d$$ can be expressed as $$\min_{x,t} t$$ $$\text{subject to } \|Ax-b\|_2 \le t, Cx = d$$