1
$\begingroup$

Could you please teach me when an optimization model with fractional terms in the objective function can be linearized or solved optimally?

I only know that if the objective function has a single fractional term with a linear numerator and denominators can be linearized. But I wonder if (i) there is a summation of fractional terms or (ii) with a quadratic numerator and/ or denominator are quadratic can be linearized or de-fractioned.

$\endgroup$
5

2 Answers 2

2
$\begingroup$

To supplement the answer by Nikos Kazazakis, I will add that it is always good modeling practice to squeeze as much convexity out of your model as possible, as to reduce degree of nonconvexity. Hence, for a rational objective contribution $\frac{f(x)}{g(x)}$ with polynomial numerator and denominator, $f(x)$ and $g(x)$, I suggest you start by reducing it using long polynomial division.

As example, given $f(x) = ax^2 + bx + c$ and $g(x) = gx + h$, you find that $$ \frac{f(x)}{g(x)} = rx + s + \frac{q}{gx+h}, $$ for some $r$ and $s$. In this simple case, the complexity has reduced from quadratic-over-linear to constant-over-linear, which is trivially representable using second-order cone programming on the convex part of the variable domain; see the modeling cookbook maintained by MOSEK for more details.

$\endgroup$
0
$\begingroup$

There are various ways to formulate this depending on context. For example, in the general case any program of type $\min \frac{f(x)}{g(x)}$ can be reformulated to:

$\min w\\\text{s.t.}\\w=\frac{f(x)}{g(x)}$

This can then be written as:

$\min w \\\text{s.t.}\\g(x)w=f(x)\\|g(x)|\geq \epsilon$

This can then be relaxed and solved with branch and bound. If we have more fractional terms, we simply add more auxiliary $w_i$ variables and constraints to match. In this example, if the range of $g(x)$ initially includes 0 we have to give something up by adding a finite tolerance, so this can not be an exact reformulation.

This is typically good enough because it's bad modelling to allow a model to acquire meaningful values close to singularities in the first place.

Global optimization solvers will do all of this automatically.

If one is feeling cheeky they might even decide the bilinear syntax is fine and not to add the absolute value constraint, if that happens to work out in hindsight, even though that's not mathematically correct. For instance, we can solve without the $\neq 0$ constraint and check whether the result actually evaluates to $g(x)=0$. If it doesn't, sweet, we're done.

$\endgroup$
3
  • $\begingroup$ Thank you so much. When two or more fractional terms are added, can we still use the conversion? $\endgroup$ Commented Feb 22, 2023 at 14:42
  • $\begingroup$ Yes, you get $\min w_1+w_2+w_3$ s.t. $w_1=...,w_2=...,w_3=...$ and so on and so forth. $\endgroup$ Commented Feb 22, 2023 at 14:56
  • $\begingroup$ Thank you so much. This is very informative and useful. It is highly appreciated! $\endgroup$ Commented Apr 7, 2023 at 20:02

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.