# 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. – user3680510 Jun 29 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 – huig Jun 30 at 7:18
• Consider $f(x)=x$ and $g(x)=2-x$ on $[0,1]$. – RobPratt Jun 30 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 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 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$. – RobPratt Jun 30 at 15:26