Given the generalized linear-fractional program: $$\text{Minimize}\;\; \max_{i}\Big|\frac{c_i^Tx+d_i}{e_i^Tx+f_i}\Big|$$ $$\hspace{-5mm}\text{Subject to}\;\; e_i^Tx+f_i>0$$

I convert this into the form: $$\text{Minimize}\;\; t$$ $$\hspace{26mm}\text{Subject to}\;\; 0\leq c_i^Ty_i+d_iz_i\leq t$$ $$\hspace{37mm}e_i^Ty+f_iz_i=1$$ $$\hspace{24mm}z_i>0$$ where $y_i=\frac{x}{e_i^Tx+f_i}$ and $z_i=\frac{1}{e_i^Tx+f_i}$.

All this is for $i=1,...,k$.

Yet when I put this into my solver (SCSSolver with the modeling tool Convex.jl), using actual data given to me in the problem, I get warnings thrown at me about the problem being likely degenerate and something about column pointers not being strictly increasing, none of which I understand. I can probably go to a different forum to find out what these warnings mean, but is my mathematical approach to the problem correct?

  • $\begingroup$ The right place to ask this question is with the authors or a forum for SCSSolver. $\endgroup$ – Wolfgang Bangerth Feb 1 '15 at 17:11
  • $\begingroup$ yes ok but is my conversion correct? $\endgroup$ – Thoth Feb 1 '15 at 19:40
  • $\begingroup$ The error message about "column pointers not being strictly increasing" almost certainly implies an error in your code and the way that you setup data structures before solving the problem. $\endgroup$ – Brian Borchers Feb 1 '15 at 20:49
  • $\begingroup$ @BrianBorchers so you're saying that it's not my formulation of the problem but the way I coded it? $\endgroup$ – Thoth Feb 1 '15 at 21:08
  • $\begingroup$ I haven't checked the formulation of the problem, but the error message points to an issue with the way in which you've setup the data structure. $\endgroup$ – Brian Borchers Feb 1 '15 at 21:13

To answer your question, yes, the mathematical approach you've taken is correct, and standard. You've combined two transformations:

About the only thing I would change would be to change the $z_{i} > 0$ constraint to $z_{i} \geq 0$. Although the former is pedantically correct, no LP solver will actually implement such a constraint, so the closest realizable constraint is the latter. In the unlikely event that you obtain an optimal solution for which a $z_{i} = 0$, you could probably insert a cut that would exclude it.


Not the answer you're looking for? Browse other questions tagged or ask your own question.