6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user3680510 Jun 29 at 17:02
6
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – huig Jun 30 at 7:18
  • 1
    $\begingroup$ Consider $f(x)=x$ and $g(x)=2-x$ on $[0,1]$. $\endgroup$ – RobPratt Jun 30 at 10:56
  • $\begingroup$ 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) $\endgroup$ – huig Jun 30 at 12:36
  • $\begingroup$ 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. $\endgroup$ – RobPratt Jun 30 at 12:52
  • 1
    $\begingroup$ 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$. $\endgroup$ – RobPratt Jun 30 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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