Decision Optimization

 View Only
Expand all | Collapse all

Transformation into 2nd order cone

  • 1.  Transformation into 2nd order cone

    Posted Mon November 29, 2021 07:37 AM
    Dear all,

    I am struggling with quadratic optimization right now. I have a problem with a linear objective and several linear constraints. However, one set of constraints takes the form $c \geq a / (a+b)$ which obviously is a quadratic constraint. Here, $a,b$ are non-negative real numbers, while $c$ takes any value between $0$ and $1$. On the selected domain, the quadratic matrix is positive semi-definite, but not on the entire area (so if $a,b,c$ take negative values). 

    Is it possible to still work with this constraint in CPLEX?
    If push comes to shove, I will replace this with a few piece-wise linear functions, but I was hoping that there was a solution without any binary/integer variables. 

    Thank you!


  • 2.  RE: Transformation into 2nd order cone

    Posted Mon November 29, 2021 03:19 PM
    Edited by Paul Rubin Mon November 29, 2021 03:29 PM
    Presumably your first step is to convert the inequality to $ac + bc - a \ge 0$, which is quadratic. I'm not sure what you mean by the quadratic matrix being positive semidefinite "on the selected domain", since the Hessian matrix is a constant (and is not psd). In any case, the feasible region is clearly not convex. For instance, (a, b, c) = (0, 0.1, 0) and (a, b, c) = (10, 0, 1) both satisfy the constraint but their midpoint (5, 0.05, 0.5) does not. CPLEX can solve nonconvex QPs and MIQPs (I think), but as far as I know it cannot solve nonconvex MIQCPs (i.e., where the feasible region is nonconvex). So I think you are going to have to do a PWL approximation or perhaps switch to a nonconvex solver.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------