7
$\begingroup$

I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they are created, I know that $0\lt x \lt y \leq U$. Obviously: $x/y \lt 1$.

In my LP objective, how do I maximize the ratio $x/y$?

Things I tried:

  • Maximizing x*cp.inv_pos(y) states my problem is non DCP (also if I try to minimize the inverse)
  • I found various LP formulations for maximizing ratios (e.g. here or here) but these requires rewriting the constraints on all the terms in the expressions for $x$ - I have no idea how to do that with cvxpy.
    If this is the way to go then an example would be very helpful!
Improve this question
$\endgroup$
1
  • $\begingroup$ @Mason the measure I need to maximize needs to be a “unitless” proportion between 0-1 so that it it properly scaled with other measures in the objective. $\endgroup$
    – Adi Shavit
    Oct 15, 2020 at 18:05

1 Answer 1

Reset to default
4
$\begingroup$

CVXPY makes this easy to do, using its disciplined quasiconvex programming (DQCP) capability.

An example is provided at https://www.cvxpy.org/examples/dqcp/concave_fractional_function.html . Fractional Linear programming, as you have, is a simple special case of this.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This works fine for a single ratio, but my objective is, unfortunately, an affine combination (weighted-sum) of such ratios. $\endgroup$
    – Adi Shavit
    Feb 9, 2021 at 9:00
  • $\begingroup$ You neglected to state that in your original question. Your newly state problem is a different problem. Perhaps you can provide the complete problem, with all constraints? $\endgroup$
    – Mark L. Stone
    Feb 9, 2021 at 14:16
  • $\begingroup$ You're right. My original question was about ratios - which as you suggested I can maximize. However, I then realized that my true objective is a weighted-sum of ratios. I can post that as a separate question if you prefer. $\endgroup$
    – Adi Shavit
    Feb 9, 2021 at 14:18
  • $\begingroup$ Yes, that would be better as a new question. $\endgroup$
    – Mark L. Stone
    Feb 9, 2021 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.