3
$\begingroup$

I am trying to represent the following inequality:

$$\frac{x}{1-x} \leq y \qquad\mathrm{with}\qquad 0<x<1$$

The function on the left is convex (its second derivative is always positive over the domain $0<x<1$), meaning that the described set is convex. (Without the domain constraint, however, the domain is far from convex…) Drawing it gives the same conclusion:

The set described by this inequality

However, I cannot find a DCP representation of this set (even using nonstandard cones).

I can do it with a slight modification (replacing $x$ with $x^2$, two quad-over-lin constraints do the trick, CVX also accepts the constraint as $y\geq\frac{x^2}{z}$ and $z\leq 1-x^2$), but it is not describing the same set, and the difference is really significant in my case.

$\endgroup$
1
5
$\begingroup$

Here is an alternative answer.

Clearly, the problem is equivalent to $$ \begin{array}{rcl} \frac{1-t}{t} & \leq & y \\ 1-x & = & t \\ \end{array} $$ which in turn is equivalent to $$ \begin{array}{rcl} \frac{1}{t} -1 & \leq & y \\ 1-x & = & t \\ \end{array} $$ This is clearly SOCP representable.

You should end up with $$ \begin{array}{rcl} 2 (1-x) (1+y) & \geq & \sqrt{2}^2 \\ 1-x & \geq & 0 \\ 1+y & \geq & 0 \\ \end{array} $$ which is the same as saying $$ \left [ \begin{array}{c} 1-x \\ 1+y \\ \sqrt{2} \\ \end{array} \right ] \in RQ $$ where RQ is a rotated quadratic cone as defined in the Mosek modelling cook book.

$\endgroup$
1
  • $\begingroup$ Thanks for your detailed answer :)! $\endgroup$
    – dourouc05
    Apr 28 '20 at 17:49
5
$\begingroup$

You can model your constraint with the second order cone constraint $$\sqrt{2^2 + (x+y)^2} \le 2-x+y,$$ and a lower bound on $x$.

I found this by first multiplying both sides by $1-x$ to obtain $(1-x)y - x >= 0$. As we have a quadratic inequality with a convex feasible region, this hints to a quadratic or second order cone.

Rewriting this constraint gives $(1-x)(1+y) \ge 1$. Then I used Equation (7) in this paper to turn the constraint into a second order cone constraint.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your answer :)! $\endgroup$
    – dourouc05
    Apr 28 '20 at 17:49

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.