6

I am working on a project where the customer requested to change the current objective function $f$ to another function $g$ (both linear). It is easy to prove that $f \le g$ and as both are linear funcions my guess is that the hyperplane each define are parallel so there is no need to replace the current objective function to $g$ as the solution to the problem should be the same. Is this right?

EhsanK
  • 5,864
  • 3
  • 17
  • 54
huig
  • 83
  • 6
  • Note that even if both lead in theory to the same optimal solution, it can still happen that one is much easier to solve (especially if this is not a pure linear program). If both are parallel the solver will probably rescale it to similar sizes, but if they are not parallel then it might be worth benchmarking. – user3680510 Jun 29 '20 at 17:02

1 Answers1

6

If $g=f+c$ for some constant $c \ge 0$, then the optimal solutions will be the same, and this does not depend on linearity of either function. But if $f \le g$ just in the feasible region and maybe not elsewhere, optimizing $g$ is not necessarily equivalent to optimizing $f$.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Could you please develop that further? Suppose $x\in S$ is the optimal solution, i.e. $f(x) \geq f(y)$ $\forall y\in S, y \neq x$. Assume $x$ is not the optimal solution for $g$ then $\exists y_0\in S$ such that $g(y_0)>g(x)$. We know that $f(x) - f(y_0) \geq 0$ which is equivalent to (linearity) $f(x-y_0) \geq 0$, and as $g \geq f$ we have $g(x-y_0)\geq f(x-y_0)\geq 0$, which using linearity again gives us $g(x)-g(y_0)\geq 0$, which contradicts the assumption – huig Jun 30 '20 at 07:18
  • 1
    Consider $f(x)=x$ and $g(x)=2-x$ on $[0,1]$. – RobPratt Jun 30 '20 at 10:56
  • What if $f \leq g$ in all the domain? Problem with my comment above is that I used a property for linear functions in subspaces ($f(0)=0$ which obviouly is not guaranteed in this context) – huig Jun 30 '20 at 12:36
  • If $f \le g$ everywhere and both are linear, then $g=f+c$. Your argument did not use $f(0)=0$ but did use $x-y_0 \in S$. Notice that $f(0)=0$ in my example. – RobPratt Jun 30 '20 at 12:52
  • $x-y_0\in S$ holds because the solution space is convex. What I meant by $f(0)=0$ is that I used that $g(x+y)=g(x)+g(y)$ which doesn't hold if $g(0) \neq 0$. Could you provide a prove for $g=f+c$ for some constant $c$? – huig Jun 30 '20 at 14:19
  • 1
    OK, yes, you used $g(0)=0$. For a proof of $g=f+c$, contradiction seems like a good approach. Assume $f$ and $g$ are linear with $g-f$ not constant, and show $g \not \ge f$. – RobPratt Jun 30 '20 at 15:26