# Can I replace the objective function $f$ with $g$ if $g \ge f$?

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?

• 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. Jun 29 '20 at 17:02

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$$.
• 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
• Consider $f(x)=x$ and $g(x)=2-x$ on $[0,1]$. 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)
• 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. Jun 30 '20 at 12:52
• 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$. Jun 30 '20 at 15:26