4
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

9
$\begingroup$

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$$

$\endgroup$
1
  • $\begingroup$ You have a good point, +1. $\endgroup$ Commented Jun 9, 2018 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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