1
$\begingroup$

I have an inequality constrained optimization problem, which I believe to be convex except for a single constraint I am having trouble handling. The objective function looks like this:

$\sum_{i=1}^{n} \frac{c_i}{x_i + y_i}$

Where $x,y \geq 0$ are the optimization variables and $c_i \geq 0$ are constants. For brevity, I'm going to omit some of the other constraints in the problem, which are mostly lower and upper bounds on the variables along with a single convex inequality constraint. However, there is one final set of constraints which I'm not sure how to handle, given by:

$\left(\frac{y_i - 1}{x_i + y_i - 1}\right) a_i - b_i \leq 0$

Here $a_i $ and $b_i$ are positive constants and my other constraints enforce that the fraction is also positive. From what I have read, this looks like a linear fractional function, which is quasilinear. I'm an optimization novice and have had difficulty finding references for handling these kinds of functions in constraints. What I have thought about so far:

  • I found some resources for these functions when they are the objective of the problem, but I don't see how those techniques are applicable here. Maybe there is a change of variable I could consider?
  • I could consider some kind of affine approximation of this function, which would make the overall problem convex. I would then need to quantify the worst case distance between the approximation and the actual function.
  • I could pretty easily relax the fraction to be $\frac{y_i}{x_i + y_i}$ but it's not immediately obvious how that might simplify things.

Looking for guidance or further references for handing this situation.

$\endgroup$
6
  • $\begingroup$ Not sure if it will work but you can try to show that $\nabla^2\frac{y_i}{x_i+y_i}\succeq0$ $\endgroup$
    – convxy
    Jan 11, 2021 at 5:55
  • 1
    $\begingroup$ The constraint you have is actually linear. Just mutliply both sides by the denominator of the fraction to see how the constraint is equivalently expressed in a linear way. Here I am assuming that the variables always satisfy $x_i+y_i-1>0$. Else, if it could be zero, then your constraint is not even defined. $\endgroup$
    – Michael
    Jan 11, 2021 at 8:40
  • $\begingroup$ Thanks for the response Michael; I attempted that earlier but I must have made an arithmetic error... since this seems to work now: $(a_i - b_i)y_i - b_ix_i - a_i + b_i \leq 0$. Happy to accept your answer if you choose to post it. $\endgroup$
    – Joel
    Jan 11, 2021 at 15:36
  • 1
    $\begingroup$ $x_i+y_i > 1$ is also important because otherwise the inequality flips because you multiply with a negative number $\endgroup$
    – LinAlg
    Jan 11, 2021 at 19:24
  • $\begingroup$ Right, the constraint on the domain is important. I already had that constraint in my original problem formulation, although I mistakenly did not have a strict inequality there. So that is fixed now. $\endgroup$
    – Joel
    Jan 11, 2021 at 19:29

1 Answer 1

Reset to default
2
$\begingroup$

You asked me to formalize my comment as an answer: Your constraints are (for some subset of indices $i$): $$ \frac{(y_i-1)a_i}{x_i+y_i-1} \leq b_i$$ There is a potential singularity if the denominator of the fraction is zero. However, if we assume that other constraints ensure that $x_i+y_i-1>0$ always, then we can multiply the inequality by the positive number $x_i+y_i-1$ to equivalently get $$ (y_i-1) a_i \leq b_i(x_i+y_i-1)$$ which is a linear (hence convex) inequality constraint.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .